0

proof of only iid sequences on a discrete probability space are constant sequences

I am having trouble with the proof linked in the image above. In particular, my questions are:

  1. Is $\Omega$ (the discrete probability space mentioned in the theorem statement) supposed to be the probability space of outcomes of a single trial? OR is it the space of all paths? (e.g., for coin flips, is $\Omega = \{H, T\}$ OR is it $\Omega = \{\textrm{all infinite sequences of } H, T\}$?)

I ask because a part of the proof (which I have highlighted) doesn't seem to make sense if it is the probability space of outcomes of a single trial. Also, I can't seem to make an intuitive sense of what the theorem is saying in that case. (My question about this highlighted part is next.)

  1. If $\omega^*$ is a particular outcome of a single trial (e.g., flipping a coin and getting heads), then if we say $x_1^* = X_1(\omega^*)$, can't I say that the outcome $\omega^*$ is equivalent to $X_1 = x_1^*$? Then isn't the end of the proof here: end of the proof calculating the probability that every single trial results in $\omega^*$ occurring (e.g., in the coin flip example, every single flip results in heads)?

My intuitive understanding is that any particular path in the stochastic process has probability zero. (e.g., if I specify the outcome of each of an infinite sequence of coin flips, the probability of that particular path is zero). However, I feel like the way this theorem is stated, it seems to be saying in the case of coin flips that each trial will result in the same outcome, e.g., all heads. What am I missing?

  1. Also, how does $\omega^* \in \{X_1 = x_1^*, X_2 = x_2^*, \cdots\}$ imply that $P(\omega^*) = P(X_1 = x_1^*, X_2 = x_2^*, \cdots)$? (can't I say $\omega^* \in \{X_1 = x_1^*\}$ as well, meaning $P(\omega^*) = P(X = x_1^*)$?) Or should it actually say $\omega^* = \{X_1 = x_1^*, X_2 = x_2^*, \cdots\}$? The latter would suggest that $\omega^*$ is actually a path; the probability of said path is what appears to be calculated.

  2. Also, if $\omega^*$ is specifying a path, then doesn't the result follow from any set of infinite sequences must be uncountable? (So we can't have a countable space of paths, the only way for this to be possible is that there is exactly one path consisting of the same outcome each time in the stochastic process.)

My apologies if anything is unclear, this is my first time posting.

curiousconfused
  • 21

1 Answers1

1

Some partial answers to your questions:

The important thing is that each $X_i$ is a function $\Omega \to \mathbb{R}$. In particular, this means each single $\omega \in \Omega$ can be associated with a path $(X_1(\omega), X_2(\omega), X_3(\omega), \ldots )$, although technically it is possible that two different values $\omega \ne \omega'$ give rise to the same paths $(X_1(\omega), X_2(\omega), \ldots) = (X_1(\omega'), X_2(\omega'), \ldots)$. I think this answers your first question; your second question is now irrelevant.

Regarding your intuition: the process you describe (infinite sequence of coin flips) cannot be formulated on a [countable] discrete probability space. (Note for instance that the space of all infinite binary sequences $\{0, 1\}^{\mathbb{N}}$ is uncountable.) While any single coin flip (or finitely many coin flips) can be formulated on a finite discrete probability space $\{0,1\}^n$, infinite sequences cannot.

For your third question, you're correct that $\omega \in A$ does not imply $P(\{\omega\}) = P(A)$ in general; we only have $P(\{\omega\}) \le P(A)$. However, if $P(A)=0$, we do have $P(\{\omega\}) = 0$ due to the sandwich $0 \le P(\{\omega\}) \le P(A) = 0$. This is what the end of the proof is doing.

For your fourth question, note that the $\omega$ in $\Omega$ only need to represent paths with nonzero probability. It might be possible a priori for there to be at most countably many paths with nonzero probability. But then again, independence of the $X_i$ implies that every possible sequence of single-trial outcomes is possible. Perhaps you are right that this is a valid proof approach; I will let someone more knowledgeable confirm whether this is true or if I've missed something.

Response to comments:

Note that one can define a discrete probability space $\Omega$ in the absence of any random variables. There, each $\omega$ (even if you do call it an outcome) doesn't carry any meaning or significance except for the probability assigned to it.

Random variables map each $\omega$ to a real number. So if you have several random variables $X$, $Y$, $Z$ on this common probability space $\Omega$, then each "outcome" $\omega$ tells you exactly what happens to the three random variables simultaneously (i.e. "AND" in your words) via $X(\omega)$, $Y(\omega)$, and $Z(\omega)$. Similarly in your sequence example, a single $\omega^*$ manifests in the path $(X_1(\omega^*), X_2(\omega^*), \ldots)$, but I don't think it is necessary to say "$\omega^*$ represents a path," since one could on the side define a host of more random variables $U$ and $V$ on the same probability space $\Omega$.

Yes: the theorem does imply that a sequence of i.i.d. coin flips cannot be formulated on a countable discrete probability space.

angryavian
  • 89,882
  • Thank you for your answer! It helps clarify some of my confusion which I think has to do with what is meant by the outcome $\omega \in \Omega$ when talking about the stochastic process. I had a few follow-up questions. When referring to an outcome $\omega \in \Omega$, is it understood that (since each such outcome is associated with a path) in terms of the stochastic process, we are referring to the path? So the outcome $\omega^$ (as above) in the stochastic process means $X_1 = x_1^$ AND $X_2 = x_2^$ AND $X_3 = x_3^$, ... (I had thought it should be OR instead of AND). – curiousconfused Jan 18 '22 at 00:21
  • Also, I understand that the space of all infinite binary sequences is uncountable. So by "the process you describe (infinite sequence of coin flips) cannot be formulated on a [countable] discrete probability space" do you mean that the space of all paths must be uncountable? (Is this what the theorem says?) – curiousconfused Jan 18 '22 at 00:24
  • @curiousconfused Added some comments to the end of my answer. – angryavian Jan 18 '22 at 01:15
  • Thanks again for the clarifying comments! "...but I don't think it is necessary to say "∗ represents a path," since one could on the side define a host of more random variables and on the same probability space Ω." -- if we are dealing with a specific stochastic process though, in that case, do we think of each $\omega^*$ representing a path (implicitly we are referring to the random variables in our indexed sequence)? – curiousconfused Jan 18 '22 at 14:33
  • "Yes: the theorem does imply that a sequence of i.i.d. coin flips cannot be formulated on a countable discrete probability space." -- The discrete probability space we are talking about here is the space of all paths; is this correct? (So the comments before the theorem statement saying "the only iid sequences on a discrete probability space are constant sequences" -- the discrete probability space being referred to here is the space of paths. I just want to make sure I am understanding correctly now. – curiousconfused Jan 18 '22 at 14:34
  • @curiousconfused Each path $(x_1, x_2, \ldots)$ is a subset of $\Omega$, namely ${\omega \in \Omega : X_1(\omega)=x_1, X_2(\omega) = x_2, \ldots}$. It's possible this subset is a singleton set ${\omega}$, but it is possible it a set of several $\omega$, or even the empty set. So $\Omega$ must have larger cardinality than the cardinality of paths with nonzero probability, but it may not be a bijective correspondence. This is why I am encouraging you not to necessarily think of $\Omega$ as paths, but just fall back on the abstract definition of $\Omega$ and RVs $\Omega \to \mathbb{R}$. – angryavian Jan 18 '22 at 15:31
  • Does each of the RVs in the sequence have to be evaluated at the same $\omega \in \Omega$ for it to be considered a path? So, for example, if we can enumerate elements of $\Omega$ as $\omega_i$, then $X_1(\omega_1), X_2(\omega_2), \cdots$ is not considered a path? – curiousconfused Jan 18 '22 at 16:31
  • @curiousconfused That is not how RVs on a common probability spaces work: you must evaluate on the same $\omega$. (However, $\Omega$ itself might be a product space e.g. $\Omega = \Omega_1 \times \Omega_2$ where each $\omega$ is a pair $(\omega_1, \omega_2)$.) – angryavian Jan 18 '22 at 17:19
  • This was my main misunderstanding. Then how about the example with the (infinite) sequence of coin flips, where $X_i$ is the result of flip $i$, e.g., let's say $X_i(H) = 1$ and $X_i(T) = 0$ for every $i$? Is $\Omega$ not equal to ${H, T}$ in this case? (Is it instead the infinite Cartesian product ${H, T} \times {H, T} \times \cdots$?) – curiousconfused Jan 18 '22 at 20:21
  • @curiousconfused If the coin flips in the infinite sequence are independent, you would need ${H, T}^{\mathbb{N}}$ (infinite Cartesian product); I alluded to this when I mentioned ${0, 1}^{\mathbb{N}}$ in my answer. – angryavian Jan 18 '22 at 20:43
  • Sorry, there is still a part of this I don't understand. In this case, isn't each single $X_i$ a function ${H, T} \rightarrow \mathbb{R}$? But in this case, the sequence $X_1, X_2, \cdots$ is defined on $\Omega = {H, T}^{\mathbb{N}}$? This intuitively seems to makes sense, but I'm not seeing how this lines up with our earlier discussion where each path $(x_1, x_2, \cdots)$ is a subset of $\Omega$, namely ${ \omega \in \Omega \mid X_1(\omega) = x_1, X_2(\omega) = x_2, \cdots }$. Maybe I'm still having confusion about the domain of a single RV versus the sequence of RVs. – curiousconfused Jan 18 '22 at 20:58
  • @curiousconfused Sorry for not being clear. When $\omega \in {H, T}^{\mathbb{N}}$, then we can define $X_i(\omega)$ to only depend on the $i$th component of $\omega$ and ignore all the other components. This is how you achieve something like "$X_1(\omega_1), X_2(\omega_2),\ldots$" on a common probability space, even though they are really receiving a common $\omega$ via $X_1(\omega), X_2(\omega),\ldots$. – angryavian Jan 18 '22 at 21:03
  • 1
    Ah, the coordinate map! Thanks for all your guidance in helping me get to the bottom of my misunderstanding. This helped a lot! – curiousconfused Jan 19 '22 at 15:04