6 ms·

Assuming the digits of pi are randomly distributed, any finite digit sequence can be found in pi. The probability any sequence of length d is found in N digits

by omra 14y ago

Assuming the digits of pi are randomly distributed, any finite digit sequence can be found in pi. The probability any sequence of length d is found in N digits of pi is 1 - 1/exp(N*0.1^d) (Poisson distribution for approximating the binomial). Then the limit as N approaches infinity is 1 for any finite d.

Someone 14y ago
Amusing fact: the probability that a sequence can be found is not equal for all sequences. A simple example: 2 binary digits in binary sequences of length 3. There are eight binary sequences of length 3: 000 001 010 011 100 101 110 111 3 of those contain '00' but 4 of them '01'. Reason for the discrepancy is that one of those with '00' has 2 overlapping occurrences, but is counted only once. You get this as soon as overlap can occur, i.e. when the sequence to be found starts with x digits that it also ends with. Of course, none of this matters, especially not when d << N, which it will be if N goes to infinity. Also, the mathematical term is 'normal number' (http://mathworld.wolfram.com/NormalNumber.html http://mathworld.wolfram.com/NormalNumber.html), and we do not know whether pi is normal.
philh 14y ago
(The digits of pi are definitely not randomly distributed, since they can be generated by a deterministic algorithm; and a randomly distributed infinite digit sequence need not have that specific probability of finding a d-length sequence in the first N digits, unless the random distribution is specifically uniform. Someone is correct that the relevant term here is 'normal'.)
hypersoar 14y ago
The probability of an event being 1 is _not_ the same thing as that event being completely certain. For example, if you pick a random real number between 0 and 1, the probability of getting something rational is zero. It's clearly not impossible, though.
- gizmo686 14y ago
  Do you know of any proof for that? My math intuition is telling me that randomly picking a real number is guarenteed to be irrational, based on the fact that there is an uncountable infinity real numbers, but only a countable infinity of rational numbers. But, without assuming a probability of 0 means impossible, I do not know how to go about proving/disproving this.
  - hypersoar 14y ago
    We can't really pick "random real numbers" in any practical sense, so this is pretty much a theoretical distinction. It's essentially a matter of definition. The rational numbers have probability zero of being drawn, but they still lie in the sample space. One way to see it is this: The probability of picking any particular point in the interval is 0. But that doesn't mean that picking that point is impossible. _Some_ point has to show up when you pick one at random.

by omra 14y ago

Someone 14y ago

Amusing fact: the probability that a sequence can be found is not equal for all sequences. A simple example: 2 binary digits in binary sequences of length 3. There are eight binary sequences of length 3: 000 001 010 011 100 101 110 111 3 of those contain '00' but 4 of them '01'. Reason for the discrepancy is that one of those with '00' has 2 overlapping occurrences, but is counted only once. You get this as soon as overlap can occur, i.e. when the sequence to be found starts with x digits that it also ends with. Of course, none of this matters, especially not when d << N, which it will be if N goes to infinity. Also, the mathematical term is 'normal number' (http://mathworld.wolfram.com/NormalNumber.html http://mathworld.wolfram.com/NormalNumber.html), and we do not know whether pi is normal.

philh 14y ago

(The digits of pi are definitely not randomly distributed, since they can be generated by a deterministic algorithm; and a randomly distributed infinite digit sequence need not have that specific probability of finding a d-length sequence in the first N digits, unless the random distribution is specifically uniform. Someone is correct that the relevant term here is 'normal'.)

hypersoar 14y ago

The probability of an event being 1 is _not_ the same thing as that event being completely certain. For example, if you pick a random real number between 0 and 1, the probability of getting something rational is zero. It's clearly not impossible, though.

gizmo686 14y ago
Do you know of any proof for that? My math intuition is telling me that randomly picking a real number is guarenteed to be irrational, based on the fact that there is an uncountable infinity real numbers, but only a countable infinity of rational numbers. But, without assuming a probability of 0 means impossible, I do not know how to go about proving/disproving this.
- hypersoar 14y ago
  We can't really pick "random real numbers" in any practical sense, so this is pretty much a theoretical distinction. It's essentially a matter of definition. The rational numbers have probability zero of being drawn, but they still lie in the sample space. One way to see it is this: The probability of picking any particular point in the interval is 0. But that doesn't mean that picking that point is impossible. _Some_ point has to show up when you pick one at random.