# Prove independence of events given random variables are iid and have continuous cdf

Let $Y_1, Y_2, \ldots$ be independent and identically distributed random variables in $(\Omega, \mathscr{F}, \mathbb{P})$ s.t. their distributions are continuous and $$F_Y(y) := F_{Y_1}(y) = F_{Y_2}(y) = \cdots$$

For $m = 1, 2, \ldots$ and $i \le m$, define $$A_{i,m} := (\max\{Y_1, Y_2, \ldots, Y_m\} = Y_i), B_m := A_{m,m}$$

It can be shown that $$P(B_m) = P(A_{m-1,m}) = \cdots = P(A_{2,m}) = P(A_{1,m}) = 1/m$$

How do we rigorously establish independence of the $B_m$'s?

I get it intuitively: Given $\omega \in \Omega$

If $\forall i \le m, \omega \in B_i$, then $\forall i \le m, (\max\{Y_1, Y_2, \ldots , Y_i\} = Y_i)$, that is, $Y_i$ is the max among $Y_1, Y_2, \ldots , Y_i$

Now whether or not $\omega \in B_{m+1}$ ($Y_{m+1}$ is the max among $Y_1, Y_2, \ldots , Y_{m+1}$) seems to be independent of whether or not $Y_i$ is the max among $Y_1, Y_2, \ldots , Y_i$ or even which among the $Y_1, Y_2, \ldots , Y_i$ is the maximum because the $Y_n$'s are independent.

But how does one prove this rigorously?

If I show that $\forall m \in \mathbb N$,

$$P(B_m\mid\sigma(B_1, \ldots, B_{m-1})) = P(B_m)$$

then we will have independence of the $B_m$'s.

I tried induction: Given $P(B_k\mid\sigma(B_1, \ldots, B_{k-1})) = 1/k$, prove

$$P(B_{k+1}\mid\sigma(B_1, \ldots, B_k))$$

I deduced that that is equivalent to:

Given $P(B_k \cap C_k) = P(C_k)(1/k)$, prove

$$P(B_{k+1} \cap C_{k+1}) = P(C_{k+1}) (1/(k+1))$$

where $C_k \in \sigma(B_1, \ldots, B_{k-1})$ and $C_{k+1} \in \sigma(B_1, \ldots, B_{k})$.

It seems that in proving $P(B_{k+1} \cap C_{k+1}) = P(C_{k+1}) (1/(k+1))$, we need to check only $C_{k+1} \in \sigma(B_{k})$ as $C_{k+1} \in \sigma(B_1, \ldots, B_{k-1})$ are already covered by assumption.

So all I have to do is show that $P(B_{k+1} \cap B_k) = (1/(k)(k+1))$ and $P(B_{k+1} \cap B_k^C) = (k-1)/(k)(k+1)$, the latter of w/c can be deduced from the former, which is proven by noting that

$$P(B_{k+1} \cap B_k) := P(Y_k > Y_1, \dots Y_{k-1}; Y_{k+1} > Y_1, \dots Y_{k-1}, Y_k) = P(Y_k > Y_1, \dots Y_{k-1}; Y_{k+1} > Y_k)$$

and then making use of the iid of the $Y_n$'s and evaluating:

$$P(B_{k+1} \cap B_k) = \int_{\mathbb R} \int_{-\infty}^{y_{k+1}} \int_{-\infty}^{y_k} \cdots \int_{-\infty}^{y_k} \int_{-\infty}^{y_k} f(y_1)f(y_2) \cdots f(y_{k-1})f(y_k)f(y_{k+1}) \, dy_1 \, dy_2 \cdots dy_{k-1} \, dy_k \, dy_{k+1}$$

$$= \int_{\mathbb R} \int_{-\infty}^{y_{k+1}} [F(y_k)]^{k-1} f(y_k) \, dy_k \, dy_{k+1} = \frac{1}{(k)(k+1)}$$

Is that right? What if the pdfs don't exist?

Can we evaluate

$$P(B_{k+1} \cap B_k) = \int_{\mathbb R} \int_{-\infty}^{y_{k+1}} \int_{-\infty}^{y_k} \cdots \int_{-\infty}^{y_k} \int_{-\infty}^{y_k} \, dF(y_1) \, dF(y_2) \cdots dF(y_{k-1}) \, dF(y_k)\,dF(y_{k+1}) \text{ ?}$$

• Just curious. If the $Y_i$ have continuous distribution, doesn't that mean their pdfs do exist? – Mick A Nov 27 '15 at 23:44
• @MickA Yes – BCLC Nov 27 '15 at 23:47
• From en.wikipedia.org/wiki/… : "A continuous probability distribution is a probability distribution that has a probability density function". – Mick A Nov 27 '15 at 23:53
• @MickA I think distribution in elem prob refers to pdf while distribution in adv prob refers to cdf – BCLC Nov 27 '15 at 23:55
• Ok, agreed. At the end of that section I linked to, it says another convention of the definition of continuous random variable allows for non-existence of pdf. – Mick A Nov 28 '15 at 0:05

To address the question of showing $P(B_{k+1}\cap B_k)=1/(k(k+1))$, it may be easier to use a combinatorial argument than to integrate.

Suppose our first $k+1$ values for the $Y_i$ are: $y_1,\ldots,y_{k+1}$. Since $Y_i$ have a continuous distribution, these $k+1$ values are distinct almost surely, so we assume that here on.

The $Y_i$ are iid so all $(k+1)!$ permutations of $y_1,\ldots,y_{k+1}$ are equally likely. Of these, exactly $(k-1)!$ have $y_{k+1}$ the largest and $y_k$ the second largest: we permute the $k-1$ smallest values in the first $k-1$ positions. So $P(B_{k+1}\cap B_k)=(k-1)!/(k+1)!=1/(k(k+1))$.

Further, in exactly $k!$ of the $(k+1)!$ permuations we have $y_{k+1}$ the largest. Thus, $P(B_{k+1})=k!/(k+1)!=1/(k+1)$. And replacing $k+1$ with $k$ we also have $P(B_k)=1/k$.

This proves $P(B_{k+1}\cap B_k)=P(B_{k+1})P(B_k)$.

Of course, we also have $P(B_{k+1}\cap B_k^c)=P(B_{k+1})-P(B_{k+1}\cap B_k)=1/(k+1)-1/(k(k+1))=(k-1)/(k(k+1))$.

• Thanks Mick A. You said 'The YiYi are iid so all (k+1)!(k+1)! permutations of y1,…,yk+1y1,…,yk+1 are equally likely' Why exactly? This seems like something intuitive. I think this is rigorously proved by integration. Then again there's the matter of the pdfs possibly not existing... – BCLC Nov 27 '15 at 19:14
• Hi @BCLC : Let $(i_1,i_2,\ldots,i_{k+1})$ be any permutation of the integers $(1,2,\ldots,k+1)$. Then, $P(Y_1\leq y_1\cap Y_2\leq y_2\cap\cdots\cap Y_{k+1}\leq y_{k+1})$ equals, by independence, $P(Y_1\leq y_1)P(Y_2\leq y_2)\cdots P(Y_{k+1}\leq y_{k+1})$, which equals, by identical distribution, $P(Y_{i_1}\leq y_1)P(Y_{i_2}\leq y_2)\cdots P(Y_{i_{k+1}}\leq y_{k+1})$, which equals, by independence, $P(Y_{i_1}\leq y_1\cap Y_{i_2}\leq y_2\cap\cdots\cap Y_{i_{k+1}}\leq y_{k+1})$. – Mick A Nov 27 '15 at 23:35

Indeed, if $$X,Y,Z,W$$ are independent, $$\mu_X = X_{*}\mathbb{P}$$ and $$F_X(\xi)=\mu_X\big((-\infty,\xi]\big)$$ is continuous for $$X,Y,Z,W$$. Then

$$\displaystyle\mathbb{P}\big(X>Y ; Z>W ; X>Z\big)=\int_{\mathbb{R}^2}F_{Y}(x)F_W(z)\mathbb{1}_{\{x>z\}}(x,z)d\mu_X(x)d\mu_Z(z).$$

Suppose that $$k>i$$, then $$\big\{Y_k=\max\limits_{j\le k}\{Y_j\}\big\} \cap \big\{ Y_i=\max\limits_{j\le i}\{Y_j\}\big\}=\big\{\max\{Y_{1},...,Y_{k-1}\}

Using that $$Y_{i},Y_{k}, \max\{Y_{i+1},\ldots,Y_{k-1}\}, \max\{Y_1,\ldots,Y_{i-1}\}$$ are independent and $$Y_k$$ are i.i.d we have for $$1\le p \le i

$$\mathbb{P}\big(Y_k=\max\limits_{j\le k}\{Y_j\} ; Y_i=\max\limits_{j\le i}\{Y_j\}\big)=\displaystyle\mathbb{P}(Y_{k}> \max\{Y_{i+1},\ldots,Y_{k-1}\} ; Y_i>\max\{Y_1,\ldots,Y_{i-1}\}; Y_k>Y_i)=\int_{\mathbb{R}^2}F_{\max\limits_{iz\}}(x,z)d\mu_{Y_k}(x)d\mu_{Y_i}(z)=\int_{\mathbb{R}^2}F_{\max\limits_{iz\}}(x,z)d\mu_{Y_q}(x)d\mu_{Y_p}(z)=\mathbb{P}\big(Y_q>\max\limits_{i\max\limits_{j\le i; j\neq p}\{Y_j\}; Y_q>Y_p\big)=\mathbb{P}\big(Y_q=\max\limits_{j\le k}\{Y_j\} ; Y_p=\max\limits_{j\le i}\{Y_j\}\big).$$

The equality above implies that

$$\displaystyle ik\mathbb{P}\big(Y_k=\max\limits_{j\le k}\{Y_j\} ; Y_i=\max\limits_{j\le i}\{Y_j\}\big)=\\ \sum_{l=1}^{k}\sum_{j=1}^{i}\mathbb{P}\big(Y_l=\max\limits_{j\le k}\{Y_j\} ; Y_j=\max\limits_{j\le i}\{Y_j\}\big)=1$$

And by this post we have that

$$\displaystyle \mathbb{P}\big(Y_k=\max\limits_{j\le k}\{Y_j\} ; Y_i=\max\limits_{j\le i}\{Y_j\}\big) = \mathbb{P}\big(Y_k=\max\limits_{j\le k}\{Y_j\} \big)\mathbb{P}\big(Y_i=\max\limits_{j\le i}\{Y_j\}\big)$$