Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm revisiting the coupon collector's problem and I'm not sure how to prove that my variables are independent. Here's what I have:

Let $X$ denote the number of tries required to collect all the coupons, and $X_i$ denote the number of tries required to collect a new coupon, after having collected $i-1$ coupons. Then $X_i \sim Geom(p_i)$ with $p_i= \frac{n-i+1}{n}$.

Intuitively they should be independent but how would one go about proving this? Would calculating $E[X_i X_j]$ and showing it equal to $E[X_i]E[X_j]$ be enough? Is this the right way to proceed?

share|cite|improve this question
up vote 2 down vote accepted

It's certainly not enough to prove that $E[X_iX_j] = E[X_i]E[X_j]$ It's quite easy to construct dependent random variables that satisfy the above. Suppose $D$ is the result when I through I throw a single die and set $$\begin{array}{r|cccccc}D&1&2&3&4&5&6 \\ \hline X & -5&-4&-3&3&4&5 \\Y & 5&-4&-3&3&4&-5 \end{array}$$

Clearly not independent but $E[XY] = E[X]E[Y]$ because that's how I chose my random variables, $X$ and $Y$ are independent if and only if for every pair $x,y$ we have $P\{X=x,Y=y\} = P\{X=x\}P\{Y=y\}$.

To show independence of an infinite list of random variables you need to do a bit more work.

We need to show that finite $n$ and any sequence $x_1,\dots,x_n$ we have $$P\{X_1=x_1,\dots X_n = x_n\} = P\{X_1=x_1\}\times\dots\times P\{ X_n = x_n\} $$

This is obviously true for $n=1$.

Now assume inductively that the above is true for $n=j$ and set $s_j =\sum_{i=1}^j x_i$ and pick an arbirtary test value of $x_{j+1}$

The event $\{X_1=x_1,\dots X_j = x_j\}$ occurs in the first $s_j$ draws Given that this does occur the event $\{X_{j+1}= x_{j+1}\}$ only involves the results of draws after $S_j$ so these two events are independent.

Therefore $$\begin{array}{rcl} P\{X_1=x_1,\dots X_{j+1} = x_{j+1}\} &=& P\{X_1=x_1,\dots X_{j} = x_{j}\}P\{X_{j+1}=x_{j+1}\} \\ &=& P\{X_1=x_1\}\times\dots\times P\{ X_{j+1} = x_{j+1}\}\end{array}$$

Therefore by induction the statement holds for every $n$ and the sequence of random variables $X_1,X_2,\dots$ is independent.

share|cite|improve this answer
What would be the base of the inductive argument here? – Spine Feast May 15 '13 at 20:38
I can't remember what that means. Did the edit help? – Tim May 15 '13 at 20:47
Yes, that's what I meant. Thanks for your answer. – Spine Feast May 15 '13 at 20:51

From Mood, Graybill and Boes, Introduction to the theory of statistics, Pp. 150, Third Ed., 1974:

``...supose $X$ and $Y$ are two independent random variables, then $f_{X,Y}(x,y)=f_{x}(x)f_{y}(y)$ by definition of independence; however $f_{X,Y}(x,y)=f_{Y|X}(y|x)f_{X}(X)$ by definition of conditional density, which implies that $f_{Y|X}(y|x)=f_{Y}(y)$; that is, the conditional density of $Y$ given $x$ is the conditional density of $Y$''.

In your example, find the conditional density function for $p_i$ and $p_j$. If conditional density of $p_i$ given $p_j$ equals marginal density of $p_i$, then they are stochastically independent.

If you have the conditional density $f_{X,Y}(x,y)$, another way to show $X$ and $Y$ are independet is to rewrite $f_{X,Y}(x,y)=g(x)h(y)$, if you can find both g(x) and h(y), then $X$ and $Y$ are independent.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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