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{ ?}$$

  • $\begingroup$ Just curious. If the $Y_i$ have continuous distribution, doesn't that mean their pdfs do exist? $\endgroup$ – Mick A Nov 27 '15 at 23:44
  • $\begingroup$ @MickA Yes $\endgroup$ – BCLC Nov 27 '15 at 23:47
  • 1
    $\begingroup$ From en.wikipedia.org/wiki/… : "A continuous probability distribution is a probability distribution that has a probability density function". $\endgroup$ – Mick A Nov 27 '15 at 23:53
  • 1
    $\begingroup$ @MickA I think distribution in elem prob refers to pdf while distribution in adv prob refers to cdf $\endgroup$ – BCLC Nov 27 '15 at 23:55
  • 1
    $\begingroup$ 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. $\endgroup$ – 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))$.

I don't know if this addresses all your questions but perhaps it is helpful.

  • $\begingroup$ 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... $\endgroup$ – BCLC Nov 27 '15 at 19:14
  • 1
    $\begingroup$ 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})$. $\endgroup$ – 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}\}<Y_k\big\}\cap \big\{\max\{Y_{1},...,Y_{i-1}\}<Y_i\big\}=\{\max\{Y_{1},...,Y_{i-1}\}<Y_i\}\cap \{\max\{Y_{i+1},...,Y_{k-1}\}<Y_k\} \cap \{Y_i<Y_k\}.$$

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<q \le k$

$\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_{i<j<k}\{Y_j\}}(x)F_{\max\limits_{j<i}\{Y_j\}}(z)\mathbb{1}_{\{x>z\}}(x,z)d\mu_{Y_k}(x)d\mu_{Y_i}(z)=\int_{\mathbb{R}^2}F_{\max\limits_{i<j\le k; j\neq q}\{Y_j\}}(x)F_{\max\limits_{j\le i; j\neq p}\{Y_j\}}(z)\mathbb{1}_{\{x>z\}}(x,z)d\mu_{Y_q}(x)d\mu_{Y_p}(z)=\mathbb{P}\big(Y_q>\max\limits_{i<j\le k;j\neq q}\{Y_j\} ; Y_p>\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)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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