6
$\begingroup$

Consider the following set, $S$, of infinite sequences:

$$S = (a_n)_{n \in \mathbb{N}} \\\text{where } a_n \in \mathbb{N} \text{ and } a_n \leq nk+1 \text{ with }k\text{ a positive integer}$$

in which all sequences have equal measure.

These sequences are equivalent to rolling a dice infinitely often, where the size of the dice is increasing each step according to $kn+1$ in the n-th step.


My interest is in the fraction of sequences with infinitely many 1-s.

I have two conflicting ideas about this, and therefore I am not so sure about my formalism and whether I made errors:

T1: set theory tells us that the fraction of sequences with infinitely many 1-s must be zero, since for every infinite sequence $(a_n)$ with infinitely many 1-s we can construct infinitely many other sets of sequences by shifting the sequence values one up like $a_{n+1}=a_n+1$, resulting in a finite number of 1-s

on the other hand

T2: If we calculate the expected value of 1s in the sequences of $S$ then we get to $\sum_{x=1}^{\infty}{\frac{1}{x}}$ (in the simple case of $k=1$) which is infinite. Does this mean that we can say that most sequences have infinitely many 1s?


Now the question here is about gaining more understanding of such infinite sampling space. A wrong application of this sample space results in paradoxical results and erroneous statements. How do we handle this correctly, and what are (correct) intuitive ways to view this space?

  1. While I understand this question becomes rather vague at the moment. My aim is to gain more insight into the infinite size of the sampling space and what it's effect is on theorems and axioms that are more particular suitable for finite sampling spaces.

  2. To make the question more specific: Let's say we want to find out the probability that a random point in $S$, is within the subset $S_{RL} \in S$, which contains all the sequences with infinitely many 1s.

    What is the probability and how do we do get to this?

$\endgroup$
  • $\begingroup$ In addition to the message with the bounty. The set $\cup_{n=1}^\infty \cap_{k=n}^\infty A_k$ is a countable union, yet uncountably large. Possibly there are examples of analogous constructions/problems where countable unions are used to show that an uncountable subset of some space has almost zero measure/probability. $\endgroup$ – Sextus Empiricus Dec 22 '17 at 21:57
  • $\begingroup$ My point in T1 was flawed. The one-to-one relationship is not sufficient to have the same measure. For instance $ x \mapsto x^2$ and $x^2 \mapsto x$ but the density of squares in $\mathbb{N}$ is almost zero. $\endgroup$ – Sextus Empiricus Dec 22 '17 at 22:03
  • $\begingroup$ The measure of a countable union of sets of measure zero always has measure zero. This is true of any measure and is a consequence of the axioms of measure theory: math.stackexchange.com/questions/132267/… $\endgroup$ – Flounderer Dec 27 '17 at 17:04
  • $\begingroup$ @Flounderer, such axiom is clear. But it becomes a bit more exciting when we construct the countably large union of countably large pieces, such that it becomes together an uncountably large piece. Other analogous examples of such constructions would be interesting and instructive to read about. $\endgroup$ – Sextus Empiricus Dec 27 '17 at 22:53
  • $\begingroup$ The concept of measure is unrelated to cardinality. For example, you could have a set of measure zero which is itself uncountably infinite, for example, the Cantor set. $\endgroup$ – Flounderer Dec 27 '17 at 23:12
6
+150
$\begingroup$

[Note: I think this answer is correct. If it's wrong, then hopefully at least it will be a starting point for further discussions.]

It's not possible to talk about the "fraction of sequences with infinitely many 1s" unless you have some way of defining "fraction". This can't be done consistently without using measure theory.

In measure theory terms, there is no way of defining a measure on this space such that every subset is measurable. In everyday terms, if you can talk about "the fraction of sequences with property $P$" for every choice of $P$, then you will reach a contradiction.

Measure theory issues cannot be avoided by saying "all sequences have equal measure" as this would restrict you to using either the zero measure or the counting measure. In either case, you wouldn't have a probability space because there is no way that the measure of the entire space could be equal to $1$.

Fortunately, there is only one way to define a sensible measure on this space, and under this measure, the probability that a sequence contains infinitely many 1s is $1$. This is reasonable, because certainly everyone would agree that the probability of getting infinitely many heads when flipping a coin infinitely many times is $1$, and this is a very similar situation.

How is the measure defined? To define a measure, you need to specify a sigma-algebra of measurable subsets and a measure on them. Fortunately, in this case it is possible to take a short cut since we are exactly in the situation of Theorem 7.16 in this pdf. (A finite space is a metric space under the discrete metric in which the Borel sets are all the subsets of the space.) [Edit: I have just noticed that the theorem in that pdf is for infinite copies of a single space rather than different spaces. But I think it is still true, for example, see the Kolmogorov Extension Theorem article on Wikipedia, under 'General Form'.]

The resulting product measure is defined as follows: For a finite list $b=(b_1, b_2, \ldots, b_n)$ of numbers, define

$$S_b = \{ s \in S: s_i = b_i, 1\le i \le n\}.$$

Then define the measure of $S_b$ by

$$\mu(S_b) = \prod_{i=1}^n P(a_i = b_i) = \prod_{i=1}^n \frac{1}{ik+1}$$

and the theorem tells us that this magically extends to a probability measure on all measurable subsets of $S$.

Now we have to use the fact that $\mu$ is a measure to get $\mu(S_{RL})=1$. The complement of $S_{RL}$ is

$$\cup_{n=1}^\infty \cap_{k=n}^\infty A_k$$

where $A_k$ is the subset of $S$ consisting of those sequences for which $a_k \neq 1$. This shows that $S_{RL}$ is a measurable set because its complement can be expressed in terms of $A_k$, which are measurable because they can be expressed in terms of $S_b$'s using countable unions, intersections and complements. Now,

$$\mu(\cap_{k=n}^\infty A_k)=0$$

because $\mu(\cap_{k=n}^N A_k) \rightarrow 0$ as $N \rightarrow \infty$. (Edit: coveniently, I think this is actually the calculation given in the other answer.) Therefore, the measure of the complement of $S_{RL}$ is $$\mu(S_{RL}^C)= \mu(\cup_{n=1}^\infty \cap_{k=n}^\infty A_k) = 0$$ because the measure of a countable union of sets of zero measure is zero, by properties of measure, and so $\mu(S_{RL})=1$ because $\mu$ is a probability measure by construction.

$\endgroup$
  • 1
    $\begingroup$ thank you for this nice answer. I will have to read a few time again trough your last part from 'Now we have to use...'. Up to before that point it reads very nice and easy. I have two quick questions for now. 1) the measure that you define is symmetric, thus every finite list has equal measure? (which would be close to the statement that every infinite sequence has equal measure) 2) I still have to settle the union stuff (so maybe it is right) but you use $a_k \neq 1$, you are not aiming for the set without zero's are you? $\endgroup$ – Sextus Empiricus Dec 1 '17 at 20:15
  • $\begingroup$ also, don't we have $\mu(S_b) \to 0$ as $n \to \infty$ such that any of our compostions of $S_b$, even the enitre sample space, will be zero when we make unions? $\endgroup$ – Sextus Empiricus Dec 1 '17 at 20:20
  • 1
    $\begingroup$ For (1) Yes, that is correct if by "finite list" you mean "the set of sequences which start with a particular finite list". (2) not sure what you mean exactly? (3) yes, it's an analogous to the situation with points in an interval. The measure of any singleton set (set containing a single point of $S$) is indeed zero. Therefore, the measure of any countable subset of $S$ is also zero. But this is not a contradiction because the set $S$ is uncountable! $\endgroup$ – Flounderer Dec 2 '17 at 17:44
  • $\begingroup$ I get the construction with the unions now. (I had missed the subscript $k=n$, thinking it was $k=1$ I thought that this was the set of sequences without 1s). So we sort of say that the measure of the set of sequences with no 1s after $n$, the $\mu(\cap_{k=n}^N A_k)$, is zero and then we make a countable union of those sets. Can we deal with both the lower and upper index, $k=n$ and $N$, in $\mu(\cap_{k=n}^N A_k)$ going to infinity? $\endgroup$ – Sextus Empiricus Dec 22 '17 at 21:26
0
$\begingroup$

I would say that to ask this question, we must ask the probability that any sequence has finite ones. I think it's sufficient to show that the probability of generating a sequence, as you described, that has finite ones, by rolling a dice at each step, is zero. If that's true then drawing any element of $S$ should guarantee to give you an element in $S_{R L}.$ $$ \prod_{j=1}^\infty \left( 1 - \frac{1}{k j + 1} \right) = \prod_{j=1}^\infty \frac{k j}{k j +1} = 0. $$

It's not obvious that the above product is zero, but it is shown (and I'm borrowing this result from) Chapter 2 Example 6a of this book, which was brought up to ask (and answer) the question in this recent thread.

Now it's easy to show that the above product, with a finite upper bound is nonzero, simply by the fact that none of the factors are individually zero. So it follows that, $$ \prod_{j=m}^\infty \frac{k j} {k j + 1} = 0 $$ for any positive integer $m.$

Now let's calculate the probability of a sequence in $S$ having exactly $n$ zeros. To do this, we define $W_n$ to be the set of all subsets of $\mathbb{N}$ of size $n$. (For example, elements of $W_3$ can be $\{1,4,9 \}, \{2, 888, 1.5 \times 10^{55} \},$ etc.) Then the probability of having exactly $n$ ones is,

$$ P(\text{n ones}) = \sum_{s \in W_n} \left( \prod_{j \in s} \frac{1}{k j + 1} \prod_{j \notin s} \frac{k j }{k j + 1} \right). $$

We can decompose the second product in the summand to look like this, $$ \prod_{j \notin s} \frac{k j}{k j + 1} = \prod_{j \notin s; j < \max(s)} \frac{k j}{k j +1} \prod_{j = \max(s)+1}^\infty \frac{k j} {k j + 1}, $$ where $\max(s)$ is the highest integer in the set $s.$ Remember, we're summing over all subsets of $\mathbb{N}$ of size $n,$ so $s$ is a sequence of $n$ positive integers. It follows that $\max(s)$ is finite for all sets $s$ in the sum. Thus $P(\text{n ones})$ is a sum of terms, each of which are zero.

Therefore $P(\text{n ones}) = 0.$ This is true for all positive integers $n.$ It follows that all sequences must have infinite ones.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer @Bridgeburners. I have no time at the moment to study it in detail. But wonder what you have to say about your $\prod_{j=m}^\infty$, for any (finite?) positive integer $m$, when we apply a limit $m \to \infty$. You might be interrested to answer this in another question math.stackexchange.com/questions/2544690/… . This particular question is about the space (which I believe you may have some interesting views on that I did not study yet, but the particular product is a different issue). $\endgroup$ – Sextus Empiricus Dec 1 '17 at 17:27
  • $\begingroup$ I also wonder how you frame your result in relation to the point T1 (theorem if you like) that I made in my question. There seems to be a contradiction. $\endgroup$ – Sextus Empiricus Dec 1 '17 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.