Infinite sequences containing every possible subsequence

[pob1212]

Hi,

True or False: Every infinite sequence of natural numbers, who's terms are randomly ordered, must contain every possible subsequence of any length, including infinity.

For example, does the infinite and random sequence $\small M$ of natural numbers require that the subsequence {59,1,6} exist within it? Or the ordered set $\small N$ of natural numbers for that matter?

My intuition is no. We could construct a sequence $\small M$, as described above, then extract every sequence {59,1,6} from $\small M$, and still have an infinite sequence. What about the idea that since M is infinite it has infinitely many chances for any unique set (even infinite sets like $\small N$) to occur within it?

Thanks,
pob

 

[jbunniii]

Every infinite sequence of natural numbers, who's terms are randomly ordered

Can you be more specific about what this means? I am guessing you mean a sequence $(x_n)$, where $n \in \mathbb{N}$ and each $x_n$ is a "random" natural number. Are duplicates allowed? Are the sequence elements assumed to be statistically independent? And what probability distribution is assumed? There's no way to select a random natural number with a uniform distribution (i.e. each number being equally likely).

 

[h6ss]

Given an infinite sequence of natural numbers who's terms are randomly ordered, if some natural number occurs infinitely often in this sequence, then we clearly have at least one infinitely long sub-sequence.

But suppose that every natural number occurs a finite amount of time, then any given finite sequence almost surely occurs as a sub-sequence, at some position:

Suppose you are looking for a sequence of a particular length in your infinitely long sequence of natural numbers:

Let $A_{k}$ be the event that the kth sequence is the one you're looking for. (We know by supposition that $A_{k}$ has a fixed nonzero probability ρ to occur)

Since the $A_{k}$ are independent, therefore the infinite sum of k $\sum P(A_{k})$ = $\sum ρ$ = ∞ diverges.

So the probability that infinitely many $A_{k}$ occur is 1, regardless of the length of the sequence defined above.

 

[Mute]

My intuition is no. We could construct a sequence $\small M$, as described above, then extract every sequence {59,1,6} from $\small M$, and still have an infinite sequence.

Is your edited sequence still "random"?

 

[HallsofIvy]

You will first have to give a specific definition of "randomly ordered".

 

[pob1212]

You will first have to give a specific definition of "randomly ordered".

Instead of allowing the sequence to be constructed from the set of all natural numbers, let's restrict the available terms to 0, 1, ..., 9. Each with a probability of 1/10 of being the next term in the sequence. Is it required that an infinite sequence constructed randomly from these numbers must contain every possibly subsequence? For example, the subsequence consisting of 100,000 ones, or two's, or any sequence (even of infinite length) that one could construct using the natural numbers less than 10.

 

[jbunniii]

Instead of allowing the sequence to be constructed from the set of all natural numbers, let's restrict the available terms to 0, 1, ..., 9. Each with a probability of 1/10 of being the next term in the sequence. Is it required that an infinite sequence constructed randomly from these numbers must contain every possibly subsequence? For example, the subsequence consisting of 100,000 ones, or two's, or any sequence (even of infinite length) that one could construct using the natural numbers less than 10.

It is not required. Indeed, it is possible that the infinite sequence consists only of 0's. This outcome has probability 0, but so does any other specific outcome.

However, it's not too hard to see that every finite pattern will occur somewhere in the sequence with probability 1. (Not quite as strong as saying that it is guaranteed to occur!) To see this, let's assume the pattern we are looking for has length N. Break the infinite sequence into chunks of length N:
chunk 1 = {$x_1, x_2, \ldots, x_N$}
chunk 2 = {$x_{N+1}, x_{N+2}, \ldots, x_{2N}$}
and so forth. The probability of an exact match at a given chunk is greater than zero. (In fact, it is $(1/10)^N$.) Therefore the probability that there is NOT a match is less than 1. (It is $1 - (1/10)^N$ - let's call this $p$ for short.)

If the chunks are independent, then if we look at multiple chunks, say M chunks, then the probability that we don't find a match in any of them is $p^M$. As $p < 1$, it follows that the probability that there is never a match is $\lim_{M \rightarrow \infty} p^M = 0$. Thus the probability that there is eventually a match is 1.

Note that we have proved something rather stronger. Not only is the probability of a match equal to 1, the probability of a match that is aligned with the chunk boundaries is also equal to 1.

It's not hard to see that the probability of infinitely many matches (i.e. the pattern occurs infinitely many times) is also 1. Just imagine that we restart the experiment every time a match is found.

 

[pob1212]

First off, thanks for the thorough response. I have some follow up questions

It is not required. Indeed, it is possible that the infinite sequence consists only of 0's. This outcome has probability 0, but so does any other specific outcome.

However, it's not too hard to see that every finite pattern will occur somewhere in the sequence with probability 1. (Not quite as strong as saying that it is guaranteed to occur!)

How do we reconcile the statement that an event has the possibility of occurring but its probability is 0? Or an event has a probability 1 of occurring but is not guaranteed to occur? I know I was taught to believe this but I can't recall why a probability of 0 does not mean the event will NOT occur.


Could we also discuss the initial question in terms of countably infinite sequences? We know that the infinite random sequence from above is countable, and all infinite sequences consisting of the numbers 0,1,...,9 are countable. Could we say that it's impossible to "fit" infinitely many countably infinite sequences inside a countable infinite sequence? Not to mention the infinite number of finite sequences that must also fit within this countably infinite sequence.

Can we say something along these line?

Thanks

 

[jbunniii]

How do we reconcile the statement that an event has the possibility of occurring but its probability is 0? Or an event has a probability 1 of occurring but is not guaranteed to occur? I know I was taught to believe this but I can't recall why a probability of 0 does not mean the event will NOT occur.

There are many situations in probability theory where an outcome has probability zero but is not impossible. For example, if X is a continuous random variable, such as a Gaussian or uniform distribution, then the probability that X equals any particular value is zero. For another example similar to the one we are discussing, if you toss a coin an infinite number of times, then any particular result sequence has probability zero. (This is actually equivalent to choosing a number from a continuous uniform distribution on [0,1], if you think of each coin flip as representing a digit in the binary expansion, e.g. 0.1001010100101011... equals some real number between 0 and 1.)

Could we also discuss the initial question in terms of countably infinite sequences? We know that the infinite random sequence from above is countable, and all infinite sequences consisting of the numbers 0,1,...,9 are countable. Could we say that it's impossible to "fit" infinitely many countably infinite sequences inside a countable infinite sequence? Not to mention the infinite number of finite sequences that must also fit within this countably infinite sequence.

The number of possible infinite sequences consisting of the numbers 0,1,..,9 is actually uncountable. (Standard diagonalization argument.) Therefore a single countably infinite sequence cannot contain every possible countably infinite subsequence.

 

[pob1212]

The number of possible infinite sequences consisting of the numbers 0,1,..,9 is actually uncountable. (Standard diagonalization argument.) Therefore a single countably infinite sequence cannot contain every possible countably infinite subsequence.

This makes sense. Each sequence can be paired with the decimal expansion of an irrational number. The set of irrational numbers is uncountable. Therefore the set of all possible sequences (including infinite sequences), consisting of 0,1,...,9 cannot be contained in an infinite and random sequence consisting of 0,1,...,9. I'm just confirming what you said above if I understand correctly

 

[jbunniii]

This makes sense. Each sequence can be paired with the decimal expansion of an irrational number. The set of irrational numbers is uncountable. Therefore the set of all possible sequences (including infinite sequences), consisting of 0,1,...,9 cannot be contained in an infinite and random sequence consisting of 0,1,...,9. I'm just confirming what you said above if I understand correctly

Yes, that's correct.