6 ms·

I don't have a strong mathematics background, but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary st

I don't have a strong mathematics background, but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary string of digits is "almost sure" rather than "sure"? Or can it actually be proven mathematically that it contains such a string?

notatoad 14y ago
It's not proven, it's the definition. If there is a subsequence that isn't contained in a non-repeating infintely long sequence, then it isn't a non-repeating infinitely long sequence.
- ColinWright 14y ago
  You're conflating two things. The technical definition of "normal" is that it contains every finite string as a substring. That will imply that it's infinite and non-repeating. However, you can have a string that is infinit and non-repeating but not normal. Pi is infinite and non-repeating, but it is not known to be normal.
- deleted 14y ago
  [deleted]
- xyzzyz 14y ago
  This is not true. For instance, sequence 00 does not occur in sequence 010110111011110111110111111... which can hardly be described as "repeating" (or periodic) sequence. The point here is normality. Fix alphabet A having b letters. We say that a sequence S of elements of A is normal if, for every word w, we have lim n->inf C(S, w, n)/n = b^(-k) where C(S, w, n) is the number of occurrences of w in first n letters of S, and k is length of w. More intuitively, S is normal if every word occurs in S with the same asymptotic frequency. So, if a sequence does not contain some word as a substring, it cannot be normal by above definition.
lutusp 14y ago
> ... but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary string of digits is "almost sure" rather than "sure"? No. Given the assumptions (a normal number, therefore infinite in extent), the probability that a given finite sequence appears somewhere in it is 1.0. > Or can it actually be proven mathematically that it contains such a string? Here's one way to think about it. Let's say that you flip a perfectly fair, random coin, heads counts as 1 and tails 0, and each flip adds a bit to a sequence. Let's further say that some finite bit sequence is chosen as a finite-subsequence target, let's say the text of "War and Peace" by Leo Tolstoy (a famously big book, 1,225 pages). We can agree that, as the normal bit sequence increases in length, the probability of encountering "War and Peace" within the sequence increases as a strict function of the number of bits in the sequence. Now the clincher -- what is true for a finite sequence (that the probability of encountering a given subsequence increases but never becomes certain) is not true for an infinite sequence. For an infinite sequence, the probability for the appearance of a given subsequence becomes certain, i.e 1.0. The only requirement is that the subsequence be finite.
- dagw 14y ago
  "almost sure", in probability, means an event with probability 1.0. I realize this is somewhat counter-intuitive from an English point of view, but it makes sense from a Math point of view.
  - lutusp 14y ago
    I just looked into this, and to me it represents philosophy masquerading as logic. Reasonable people may differ. http://en.wikipedia.org/wiki/Almost_surely http://en.wikipedia.org/wiki/Almost_surely A quote: "In probability theory, one says that an event happens almost surely (sometimes abbreviated as a.s.) if it happens with probability one." This is like saying a dollar is approximately 100 pennies, or every woman is approximately pregnant (or the reverse). Another quote: "Equivalently, we can say an event E happens almost surely if the probability of E not occurring is zero." With probability theory being guided by notions like this, no wonder insurance is so expensive. To me, it is to probability theory what post-modernism is to literature -- it reduces everything to a matter of opinion. In analysis, we have the notion of a limit, the idea that we can say something about a quantity that is only approached, never reached. Example: lim x -> 0, 1/x = ∞ Technically this says "as x approaches zero, 1/x approaches infinity." But I can't tell you how many times I have heard this stated as "as x approaches zero, 1/x equals zero." But that's not so -- division by zero is undefined, so the problem as stated can never be described as anything but a limit, an approach. The reverse logic applies to a probability of 1.0 -- 1.0 is not approximately anything, it's 1.0. It's not "almost one", it's "one". And if you subtract one from it, the result is not almost zero, it's zero. > but it makes sense from a Math point of view. Only if probability theory transcends the axioms of logic, and with the assumption that logic is the foundation on which mathematics is built.

notatoad 14y ago

It's not proven, it's the definition. If there is a subsequence that isn't contained in a non-repeating infintely long sequence, then it isn't a non-repeating infinitely long sequence.

ColinWright 14y ago
You're conflating two things. The technical definition of "normal" is that it contains every finite string as a substring. That will imply that it's infinite and non-repeating. However, you can have a string that is infinit and non-repeating but not normal. Pi is infinite and non-repeating, but it is not known to be normal.
deleted 14y ago
[deleted]
xyzzyz 14y ago
This is not true. For instance, sequence 00 does not occur in sequence 010110111011110111110111111... which can hardly be described as "repeating" (or periodic) sequence. The point here is normality. Fix alphabet A having b letters. We say that a sequence S of elements of A is normal if, for every word w, we have lim n->inf C(S, w, n)/n = b^(-k) where C(S, w, n) is the number of occurrences of w in first n letters of S, and k is length of w. More intuitively, S is normal if every word occurs in S with the same asymptotic frequency. So, if a sequence does not contain some word as a substring, it cannot be normal by above definition.

lutusp 14y ago

> ... but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary string of digits is "almost sure" rather than "sure"? No. Given the assumptions (a normal number, therefore infinite in extent), the probability that a given finite sequence appears somewhere in it is 1.0. > Or can it actually be proven mathematically that it contains such a string? Here's one way to think about it. Let's say that you flip a perfectly fair, random coin, heads counts as 1 and tails 0, and each flip adds a bit to a sequence. Let's further say that some finite bit sequence is chosen as a finite-subsequence target, let's say the text of "War and Peace" by Leo Tolstoy (a famously big book, 1,225 pages). We can agree that, as the normal bit sequence increases in length, the probability of encountering "War and Peace" within the sequence increases as a strict function of the number of bits in the sequence. Now the clincher -- what is true for a finite sequence (that the probability of encountering a given subsequence increases but never becomes certain) is not true for an infinite sequence. For an infinite sequence, the probability for the appearance of a given subsequence becomes certain, i.e 1.0. The only requirement is that the subsequence be finite.

dagw 14y ago
"almost sure", in probability, means an event with probability 1.0. I realize this is somewhat counter-intuitive from an English point of view, but it makes sense from a Math point of view.
- lutusp 14y ago
  I just looked into this, and to me it represents philosophy masquerading as logic. Reasonable people may differ. http://en.wikipedia.org/wiki/Almost_surely http://en.wikipedia.org/wiki/Almost_surely A quote: "In probability theory, one says that an event happens almost surely (sometimes abbreviated as a.s.) if it happens with probability one." This is like saying a dollar is approximately 100 pennies, or every woman is approximately pregnant (or the reverse). Another quote: "Equivalently, we can say an event E happens almost surely if the probability of E not occurring is zero." With probability theory being guided by notions like this, no wonder insurance is so expensive. To me, it is to probability theory what post-modernism is to literature -- it reduces everything to a matter of opinion. In analysis, we have the notion of a limit, the idea that we can say something about a quantity that is only approached, never reached. Example: lim x -> 0, 1/x = ∞ Technically this says "as x approaches zero, 1/x approaches infinity." But I can't tell you how many times I have heard this stated as "as x approaches zero, 1/x equals zero." But that's not so -- division by zero is undefined, so the problem as stated can never be described as anything but a limit, an approach. The reverse logic applies to a probability of 1.0 -- 1.0 is not approximately anything, it's 1.0. It's not "almost one", it's "one". And if you subtract one from it, the result is not almost zero, it's zero. > but it makes sense from a Math point of view. Only if probability theory transcends the axioms of logic, and with the assumption that logic is the foundation on which mathematics is built.