Maximal number of independent random variables

[fishy_1980]

Hi all,

assume we have a sample space with 2^n points. (it size is 2^n for some natural n)
I need to prove that the maximal number of independent binary (indicator) random variables (which are not trivial, i.e. constant) is n...



Thnks,
Pitter

 

[mathman]

Have you tried mathematical inuction on n. It seems pretty straightforward.

 

[EnumaElish]

I am not sure that I understand.

Say I have 4 obs with 3 independent variables:

y x1 x2 x3
10 1 0 1
11 1 0 0
12 0 1 0
20 0 1 1

I can estimate the model y = b1 x1+ b2 x2 + b3 x3 + u with the following results:
b1 = 8.75
b2 = 14.25
b3 = 3.5

 

[fishy_1980]

I've tried induction,

but I still don't get it...

I don't really know how to algebraically define
dependent random variables (dependent by their random variable function)

 

[EnumaElish]

I am not convinced that the statement is true. Did you see my example?

n = 3
2^n = 8

Since I can uniquely and independently estimate a 3-variable model with 4 observations, I can surely estimate, say, a 4-variable model with 8 observations. Yet the statement implies that with 8 observations the maximal number of variables is 3.

Another example with 2^3 = 8 observations and 4 independent binary variables:
x1 x2 x3 x4
1 0 1 0
1 0 0 1
0 1 0 1
0 1 1 1
1 0 1 1
1 0 0 1
0 1 0 1
0 1 1 0

 

[EnumaElish]

I don't really know how to algebraically define
dependent random variables (dependent by their random variable function)

Random variables X and Y are dependent if Prob{X = x and Y = y} $\ne$ Prob{X=x}Prob{Y=y}, or equivalently, Prob{X < x and Y < y} $\ne$ Prob{X<x}Prob{Y<y}.

Alternatively, variables x1, x2, x3 and x4 are linearly dependent if there exists a1, a2, a3 such that x4 = a1 x1 + a2 x2 + a3 x3. Equivalently, they are lin. dep. if there exists a1, a2, a3 and a4, not all equal to zero, such that a1 x1 + a2 x2 + a3 x3 + a4 x4 = 0.

Neither of my examples above is a case of linear dependence.

 

[fishy_1980]

thanks EnumaElish,

I think you're right,
and if looking at it that way (as vector space) the maximum number of independent binary random variables above 2^n points in the sample space, is 2^n...and not n.