Probability of Repeating DigitsFrom: Heyo Rust Subject: probability of 987987987 in any real Date: Tue, 8 Nov 94 9:48:02 MET Hi, Dr. Math, I just saw the announcement of your service in rec.puzzles and one question that has boggled me for years came to my mind. First I'd like to say that I'm German and I'm not a math student, so please forgive me for my bad English and especially for using false mathematic terminology. The puzzle was published in a book named 'Mensa, Raetsel fuer Hochbegabte' (puzzle for high intelligence). I don't have that book handy so I phrase it as I remember it: There was an indroduction about random numbers and pseudo-random numbers. The decimal representation of a real can be viewed as pseudo-random because it's not ending and not repeating. Now to the question: if you take any real, what is the probability of finding 987987987 in the decimals ? The book delivered the answer that it must be 1 because in any random number there must be any string to find. This is, of course, false. Reals are pseudo-random not random so the explanation doesn't apply here. The term sum from i=1 to infinity of ( 1 / ( 10 ^ ( 2 ^ i ) ) ) will produce a real where the given digits will never occur. The problem with reals is that there are so many of them, uncountable infinit. so even if I give a counter example, even if I give a (countable) infinite number of them the probability will still be 1. This is where I'm stuck. Does it help if i say that i could convert any real having 987987987 in it to its binary presentation (this would still be a real and I wouldn't get duplicates) and then say that these can be viewed as an uncountable infinite number of counter-examples? (I just say they are in decimal representation.) This is legal since, viewed as such they are still reals, the conversion trick was only done to show that they where already there and, since I can find such a binary to any real with 987987987 in it, there must be the same amount of them.) If this trick is legal, I can do it also with a conversion to numbers base 3 to 9. Then the answer to the original question would be 1/9. Can this be the solution ? Patiently awaiting your wise comments, No, it can't (as I just saw, rereading what I just wrote). The probability could be even less. Not any number having a 9 in it must also have 987987987 in it. It's pseudo-random, not random. Is there any way to prove for a given number that a specific pattern will never occur ? Patiently awaiting your wise comments, bye, heyo From: Dr. Ethan Date: Tue, 8 Nov 1994 21:08:16 -0500 (EST) Great I am glad that you sent it to us--that is why we are here. I do want you to know that we are specifically designed to serve students in high school and elementary school. Therefore it may take some time for us to get to your problem. However I happen to find it fascinating so I know that at least this math doctor will be working on it. First some comments on the binary thing. I'm not sure that I completely understood your approach but I think that it was something like, if every real number can be represented as a decimal expansion in binary, then they obviously don't have 987987987 in their expansion and that gives us the whole real line as counter examples. If that wasn't your idea then please feel free to write back and correct me. If that was it, then I don't think that you can use that logic. If you want to look at the real numbers as binary numbers then you have to change 987987987 into a binary number and look for that pattern. There may be some help found in looking at other bases although I'm not sure. My first thought would be to consider the rational numbers separately from the irrationals. I don't know exactly where this will go but that is where I would look first. Mainly I am writing to let you know that we are here and thinking about your quesion but it make take some time for a real answer because we are really busy with the questions from younger students. Ethan, Doctor On Call From: Dr. Ken Date: Tue, 8 Nov 1994 21:40:12 -0500 (EST) Hello there in Germany! Your issue with the problem lies not in your counter-example, but in your understanding of Probability. Just because you find a number that doesn't have 987987987 in its decimal expansion, you haven't proven that the probability of finding it in any given number is less than one. Let me elaborate. What is the probability that, if Wilhelm chooses a random number, it will be 2.07948756? I claim that it's zero: there are an uncountably infinite number of numbers (a set in the real line with infinite measure) that aren't 2.07948756, and only one number that is (a point in the real line, with measure zero). So the probability is Zero/Infinity (pardon my abuse of notation), which is zero. What if you only got to choose from numbers between 2 and 5? Still, the answer would be zero. What's going on in your example is that there are SO many numbers whose decimal expansion is, for all our purposes, infinite. In fact, all the irrational numbers and all the transcendental numbers are like that. It can be proven that the set of irrational numbers are very dense (MUCH more dense that the rational numbers, i.e. there are WAY more irrational numbers than rational) in the real line. So if you choose a random number from the real line, the probability of choosing an irrational number is 1. Now, that doesn't mean choosing a rational number is impossible, but it just means it's VERY unlikely if you're truly choosing at random. So since almost all of these irrational numbers have 987987987 in their expansion, the probability is 1. I hope this helps, and write back if it doesn't. -Ken "Dr." Math From: Dr. Ken Date: Wed, 9 Nov 1994 11:10:23 -0500 (EST) Hello there! I thought of a slightly different way to think about your problem. My first point is that I firmly believe that the probability of finding 987987987 in the decimal expansion of a random number IS 1. See, picking a random number is the same as just picking from the digits 1 through 9 at random, right? So what's the probability that if you just start listing random digits forever, you won't ever list the digits 987 three times in a row? I say it's zero. In a truly random listing, no sequence is any more likely to appear than any other. So the probability that we choose a number with 987987987 in its decimal expansion is therefore 1. That's why it's so hard to prove that it's less than 1. -Ken "Dr." Math Date: Tue, 15 Nov 1994 12:25:00 -0500 (EST) From: Dr. Ken Subject: Re: probability of 987987987 in any real Hey there! I thought I'd send you some more thoughts on this problem. I have become more and more convinced that the probability in question IS 1, so I thought I'd warn you that you'll have a hard time proving that it's not. Here's my reasoning: When you say "choose a random real number", what you're really doing (except for the integral part; ignore that for now) is putting down a decimal point, and then choosing randomly from the digits 0 through 9. So the question becomes "What is the probability of listing random numbers and never listing the block 98787987?" If the sequence is really random, you will expect this block to appear, on the average, as often (infinitely often, in fact) as any other sequence of six digits. So it is more clear now that the probability of listing 987987987 is one; eventually you're going to hit it, if you're really just listing off random digits from 0 to 9. As far as your binary expansion goes, I think that it won't help, because having the sequence 987987987 in the decimal expansion would simply correspond to having some other particular sequence of 1's and 0's in the binary expansion. I'd be very worried if changing the notation of the number changed anything essential (like the probability of having a certain sequence in its expansion) about the number, since they are really just two labels for the same item. So I think the main issue is "How do we choose a random number?" I believe that the only logical way to truly choose a random number has to be the same thing as I have described above; listing random digits in whatever base you're working in. So if we've found that the probability of finding 987987987 to the _right_ of the decimal point (or hexidecimal point, or octal point, or whatever) is 1, tacking on digits to the _left_ of the decimal point won't decrease that. So the probability is 1, as stated in the book. I hope this helps. As Heyo Rust wrote, : :Hi Ethan, Hi Ken: : :since you both replied to my mail I address this to both of you. :also, since I don't know how many heads dr. math has and how good :your administration works, I've set Cc: to both of you. Please :state, if you like to get further mail personally or as dr. math. : :>[...] Therefore it may take some time for us :>to get to your problem. :I haven't solved this in more than five years, nor could i find someone :of real help. I don't mind if another five go around. : :>However I happen to find it fascinating so I know :>that at least this math doctor will be working on it. :i don't want to urge you to spend :any time you haven't in this but i really appriciate your help. Some :day I'd like to prove that that smartass Seribriakov was false on this. :(you can see from the above sentence that i'm a smartass, too :-) : :> First some comments on the binary thing. I'm not sure that I :>completely understood your approach but I think that it was something like, :>if every real number can be represented as a decimal expansion in binary, :>then they obviuously don't have 987987987 in their expansion and that gives :>us the whole real line as counter examples. :That's not quite right. As I proved with sum(i=1 to inf.) ( 1 / 10 ^ (2^i)) :there is one counter example. but that's not enough. I have to find an :uncountable infinite number of them. :As the given example shows, there are reals that have only "1"s and "0"s :in their decimal expansion. :I wanted to show that the number of those reals with only 1 and 0 is :equal to (or greater than) the number of those that have 987987987 in them. : :So, if you take all those 987s and write down their decimal expansion in :binary there are the same number of them. (If you agree that from :different 987s can't derive duplicates in binary and that through the :conversion they don't turn into non-irrational) :Now I have a 1:1 relationship, which proves that they are equal in :number. :But the 987s are decimal the other are binary so I can't compare them. :Next step: there are reals in decimal notation that have only 1s and :0s. And for every binary number I can find a decimal number that looks :exactly the same. Their numbers are equal. That proves that the :number of (decimal) reals without 987987987 in the decimal expansion :is equal to or greater than those with. : :I hope that sound logical to you? For me, it does. :The problem is that building up relationships isn't an allowed :operation on irrational numbers. Or at least not in any case. I just :don't know if it is in this case. :Counter example: the number of reals in any interval is uncountable :infinit. The number of all reals is also uncountable infinit. How big :is the probability to draw a number in [0;1] out of all reals? :How big is the possibilty to draw a negative number out of all reals? :Get what I mean ? : :> My first thought would be to consider the rational numbers separately :>from the irrationals. I don't know exactly where this will go but that is :>where I would look first. :> :i didn't say that but i thought it was obvious that only irrational :numbers were meant. (I always used "real"; that was imprecise). Rational :numbers don't make good pseudo-random numbers in their decimal expansion. : :> Mainly I am writing to let you know that we are here and thinking :>about your question but it make take some time for a real answer because we :>are really busy with the questions from younger students. :> Ethan Doctor On Call :> :Again, I don't mind how long it takes. I just hope that you can relax :and don't have this one running as a "background task" all the time. : :bye, : heyo -Ken "Dr." Math Date: Wed, 16 Nov 94 22:54:18 MET From: Heyo Rust Subject: Re: probability of 987987987 in any real >Hey there! Hi Ken, >I thought I'd send you some more thoughts on this problem. I have become >more and more convinced that the probability in question IS 1, so I thought >I'd warn you that you'll have a hard time proving that it's not. Here's my >reasoning: You convinced me. >When you say "choose a random real number", what you're really doing (except >for the integral part; ignore that for now) is putting down a decimal point, >and then choosing randomly from the digits 0 through 9. So the question >becomes "What is the probability of listing random numbers and never listing >the block 98787987?" If the sequence is really random, you will expect this >block to appear, on the average, as often (infinitely often, in fact) as any >other sequence of six digits. So it is more clear now that the probability >of listing 987987987 is one; eventually you're going to hit it, if you're >really just listing off random digits from 0 to 9. It's always a good thing to see things from another point of view. But if this is true, there must be an error in my reasoning. There is and I found it. It's exactly the thing I wasn't sure of in the first place. The method of building up a relationship to show that the number of both sets is equal is no legal reason. I lack the knowledge of the proper terms to explain this, but I think it's something like that the interval and the density of both sets must be taken into acount. The interval of the rational numbers is infinite but the density is less then those of the irrational, so the probability of picking a rational is 0. The number of and the density of the irrationals between 0 and 1 are equal to the number of all irrationals. But the interval of the first is not infinite. In my example I think the density of those numbers w/o the pattern in it is (now what, I don't how how to measure it, but it's just too small compared to the density of all irrational numbers). >As far as your binary expansion goes, I think that it won't help, because >having the sequence 987987987 in the decimal expansion would simply >correspond to having some other particular sequence of 1's and 0's in the >binary expansion. I'd be very worried if changing the notation of the >number changed anything essential (like the probability of having a certain >sequence in its expansion) about the number, since they are really >just two labels for the same item. I think You didn't really understood what I wanted with the binary expansion. I'll try once again. There are irrational numbers that have a certain pattern in the decimal expansion. (e.g. 987987987) There are also irrational numbers that don't have the pattern. Especially those that have only 1s and 0s. Whenever you show me a number with 987987987 in the expansion, I can show you a number that has only 1s and 0s. I can find one counterexample for every number you bring. My numbers will always be irrationals (as long as you bring an irrational). I will never have to resort to a number I used before (as long as you bring only new once). How can I do this ? I transform your number to its binary representation but I wouldn't tell you. I just write the number down and say "Look, this is a number with only 1s and 0s in its DECIMAL expansion." I know that You can bring up an uncountable infinite number of examples but that doesn't bother me since I have the same number of counterexamples up my sleeve. I have a transformation-rule to compile counterexamples out of your examples. I don't need to tell you that I use a translation to binary. My counterexamples are DECIMAL for you. >So I think the main issue is "How do we choose a random number?" I believe >that the only logical way to truly choose a random number has to be the same >thing as I have described above; listing random digits in whatever base >you're working in. So if we've found that the probability of finding >987987987 to the _right_ of the decimal point (or hexidecimal point, or >octal point, or whatever) is 1, tacking on digits to the _left_ of the >decimal point won't decrease that. So the probability is 1, as stated in >the book. > >I hope this helps. >-Ken "Dr." Math Yes it helped. It is still not easy to accept that an uncountable infinite number of counterexamples is just not enough, but I agree that the answer in the book was right. Thank you for wasting your time with a problem that had no value short of satisfying my curiosity. bye, heyo |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/