Bounds for the number of independent variables on a finite probability space

41 Views Asked by At

The following question looks somehow academic but I didn't find much information on the Internet.

Consider a finite probability space $\Omega=\{\omega_1, \dots, \omega_n\}$ with a probability $\mathbb{P}$ such that $\mathbb{P}(\omega_i)>0$ for every $i$. We consider a set of non constant real random variables $X_1, \dots, X_k$ and assume that the variables $\{X_j\}_{1 \leq j \leq k}$ are mutually independent.

Prove that $k$ is finite, and find a function $f$ such that $k\leq f(n)$.

Each variable being not constant, for every $j$ we have the existence of at least two distinct values $x_j^1 \neq x_j^2$ taken by $X_j$. Next we consider the sets $\bigcap_{j=1}^k \{X_j=x_j^{\ell}\}$ for $\ell =1,2$. By independence these sets are distinct and of number $2^k$ thus $2^k\leq 2^n$ thus $k\leq n$.

Is there a better bound?

1

There are 1 best solutions below

0
On

Claim: If $ \Omega = \{ \omega_1,\ldots,\omega_n \}$ is a finite probability space with $\Pr(\omega_i) > 0$ for all $i$, and $E_1, \ldots, E_k$ are mutually independent events all different from $\Omega$ and $\emptyset$, then $k \leq \lfloor\log_2 n\rfloor$.

Suppose $n < 2^{m+1}$ and suppose there are $m+1$ events $E_1, \ldots, E_{m+1}$. Then at least one of the $2^{m+1}$ intersections $\bigcap_{1 \leq i \leq m+1} E_i^* $ is empty, where $E_i^*$ is either $E_i$ or its complement. Disjoint events, however, are not independent.