21

I'm reading the book "Large Networks and Graph Limits" by László Lovász. On the page 18 he said the following:

One cannot construct more than countably many independent random variables (in a nontrivial way, neither of them concentrated on a single value).

But I can not understand why it is impossible, I'm asking for your help.

SBF
  • 35,163
  • 4
  • 77
  • 154
kerzol
  • 600
  • 2
  • 13
  • Can you provide context? – zarathustra Jul 25 '14 at 08:01
  • Well, continous random graphs form the context. In particular, we say that any symmetric function $g : [0,1]^2 \to \{0,1\}$ is a continous graph. Then, we try to define a random continous graph... and we fail. I cannot understand how and why we fail. See also this screenshot of book's page: http://i.imgur.com/pdA4u6h.png – kerzol Jul 25 '14 at 08:13
  • 5
    Interesting. By Kolmogorov extension theorem you can construct a family of independent random variables $(\xi_i)_{i\in I}$ for any set $I$, in particular for uncountable ones. These variables even do not have to be identically distributed. The only requirement is that the range of each $\xi_i$ is nice topological space, e.g. $\Bbb R^n$. – SBF Jul 25 '14 at 08:57
  • 2
    In fact, the range of $\xi$ is the only thing that matters - you can define any dependence structure between $\xi_i$'s. Only in case you'd like them to take values from arbitrary measurable spaces and yet have an arbitrary dependence structure, you need to work with a countable $I$ and apply Ionescu Tulcea theorem. – SBF Jul 25 '14 at 10:11
  • Classically, a set of random variables is independent iff every finite subset is independent. But, if one takes a countable set. There are indefinitely many infinite subsets that are note participate in this definition. In the case of uncountable set, the situation is even worse. So, may be there is another definition of independence? – kerzol Jul 28 '14 at 06:49
  • 1
    Have you read the statement of KET? I think it specifies, which independence is meant, and it's pretty likely that it is the same the author of your book meant. If you saw any other definition for uncountable sets, please tell me. – SBF Nov 18 '14 at 16:34
  • 1
    Could it be that the author meant the following result (given in one dimension here): It is impossible to construct a family of i.i.d. nondegenerate random variables $\{\xi_t,t\in[0,1]\}$ *on the probability space* $([0,1],\mathcal{B}([0,1]),\lambda)$, where $\mathcal{B}([0,1])$ denotes the Borel sigma algebra in $[0,1]$ and $\lambda$ is the Lebesgue measure restricted to $[0,1]$. [This is not in contradiction to Kolmogorov's Existence Theorem.] – binkyhorse Dec 22 '14 at 23:45
  • @binkyhorse That seems likely, since in the next sentence the author goes on to say "This is the reason why we cannot define a random graph on an uncountable set like [0,1], only on finite and countable subsets of it". – Chill2Macht Apr 30 '16 at 01:39
  • @binkyhorse could you please provide a referecne to this result ? – kerzol Apr 30 '16 at 21:04

2 Answers2

12

"Theory of Stochastic Processes", Gusak et al., Springer, 2010:

Problem 1.10:

Prove that it is impossible to construct on the probability space $\Omega = [0, 1]$, $\mathcal{F}=\mathcal{B}([0,1])$, $\mathsf{P}=\lambda$ a family of independent identically distributed random variables $\{\xi_t, t\in[0,1]\}$ with a nondegenerate distribution.

($\lambda$ denotes one-dimensional Lebesgue measure restricted to $[0,1]$.)

Solution (also from that book):

The proof strategy is to derive a contradiction to the separability of $L^2(\Omega,\mathcal{F},\mathsf{P})$.

Assume such a family exists. Because the distribution of $\xi_t$ is nondegenerate for each $t\in[0,1]$, there exists a set $A\subset\mathcal{B}(\mathbb{R})$ such that for some (and, because of the identical distribution assumption, for each) $t\in[0,1]$ we have $\mathsf{P}(\xi_t\in A)\in(0,1)$.

For any $[0,1]\ni s\neq t$, the distance in $L^2(\Omega,\mathcal{F},\mathsf{P})$ between $\mathbf{1}\{\xi_t\in A\}$ and $\mathbf{1}\{\xi_s\in A\}$ is equal to some constant $c_A>0$; therefore, the space $L^2(\Omega,\mathcal{F},\mathsf{P})$ is not separable.

binkyhorse
  • 844
  • 1
  • 8
  • 12
  • Thanks for the refrence. Do you have an idea why $c_A > 0$? If $\xi_{s,t}$ are i.d.d. variables, then we should have (if I understand correctly) $\mathsf{P}(\xi_t \in A) = \mathsf{P}(\xi_s \in A)$ and the distance between $\mathbf{1}\{\xi_t\in A\}$ and $\mathbf{1}\{\xi_s\in A\}$ will be zero. – kerzol May 02 '16 at 22:36
  • 2
    Using the $L^2$-norm, we get $||\mathbf{1}\{\xi_t\in A\}-\mathbf{1}\{\xi_s\in A\}||_2^2 = \int_{[0,1]}|\mathbf{1}\{\xi_t\in A\}-\mathbf{1}\{\xi_s\in A\}|^2 \mathrm{d}\mathsf{P}$. This is equal to $\int_{[0,1]}\mathbf{1}\{\{\xi_t\in A, \xi_s\not\in A\}\cup \{\xi_t\not\in A, \xi_s\in A\}\} \mathrm{d}\mathsf{P}=\mathsf{P}(\{\xi_t\in A, \xi_s\not\in A\}\cup \{\xi_t\not\in A, \xi_s\in A\})$. – binkyhorse May 04 '16 at 07:56
  • Thanks. Do you think that the identity of distributions is really necessary ? – kerzol May 18 '16 at 12:53
  • 1
    In the proof, identical distributions are required to establish the existence of a Borel set $A$ with the property that for each $t\in[0,1]$ we have that $\mathsf{P}(\xi_t\in A)\in(0,1)$. It is also possible to obtain this without identical distributions. For example, start with each $\xi_t$ uniform on $[0,1]$. Now modify the density function of $\xi_t$, but only on $[1/2,1]$ in a different way for each $\xi_t$ (this is possible), such that it is still a density function. Now each variable has its own distribution and $A=[0,1/2)$. – binkyhorse May 18 '16 at 21:14
  • I don't know if the above proof can be saved if you only want independent random variables without any other condition. – binkyhorse May 18 '16 at 21:19
  • The above proof seems to hold more generally for pairwise independence, rather than mutual independence. – Michael Jan 02 '20 at 18:13
5

I e-mailed Professor Lovasz about this question, and here is the summary of his response:

We only want to consider collections of independent random variables with a regular conditional distribution.

This necessitates the more restrictive Ionescu-Tulcea Extension theorem, which only goes through for countably many random variables, unlike the Kolmogorov Extension Theorem, which allows one to construct uncountably many independent random variables on any measurable space with a Hausdorff topology.

As (almost) everywhere in the book we assume that the underlying probability space is standard (i.e. has a regular conditional distribution). On nonstandard probability spaces, one can construct "quasirandom" graphs, where the neighborhoods of nodes are independent events. This is a special case of the construction in Section 11.3.2.

Community
  • 1
Chill2Macht
  • 20,290
  • 10
  • 51
  • 144