Let the set $\{1,\ldots , n\}$. We arrange randomly the numbers in a row. Let $X_i$, the value of the number in the $i$-th place. Let $A_i$ the event "$X_i$ is larger then $X_{i-1},\ldots, X_1$".

Questoin: $A_2,A_3,A_7$ are:

  1. Independent
  2. Dependent, but mutually independent.
  3. $A_2,A_3$ independent, but $A_3,A_7$ dependent.

Now, I know that for every $i$: $Pr(A_i) = \frac{1}{i}$ so we can conclude that the events are independent. BUT, are they really independent events? I mean, if we knew that $A_2$ didn't occur then we had new information for $A_3,A_7$, so are they dependent? I'm confused.

  • $\begingroup$ "so we can conclude that the events are independent." Please explain. $\endgroup$
    – drhab
    Feb 7, 2015 at 10:55

1 Answer 1


The events $A_1,\dots,A_n$ are independent.

Here $X_{i}\neq X_{j}$ for each pair $\left(i,j\right)$ where $i\neq j$ and $P(A_{i})=\frac{1}{i}$ as you mentioned in your question.

Fix $i\in\left\{ 1,\dots,n\right\} $. Every order $X_{\sigma(1)}<X_{\sigma(2)}<\cdots<X_{\sigma(i)}$ where $\sigma$ is a permutation on $\{1,\cdots,i\}$ has the same probability to occur and there are $i!$ possibilities. So denoting $B_{\sigma}:=\{X_{\sigma(1)}<X_{\sigma(2)}<\cdots<X_{\sigma(i)}\}$ we have $P(B_{\sigma})=\frac{1}{i!}$ for each $\sigma$.

Independency of the $A_{i}$ can be proved by showing that $P\left(E_{1}\cap\cdots\cap E_{n}\right)=P\left(E_{1}\right)\cdots P\left(E_{n}\right)$ whenever $E_{i}\in\left\{ A_{i},A_{i}^{c}\right\} $ for $i=1,\dots,n$. Using induction on $i$ it is enough to prove that $P\left(E_{1}\cap\cdots\cap E_{i}\cap A_{i+1}\right)=P\left(E_{1}\cap\cdots\cap E_{i}\right)P\left(A_{i+1}\right)$.

We have: $P\left(B_{\sigma}\cap A_{i+1}\right)=P(\left\{ X_{\sigma\left(1\right)}<\cdots<X_{\sigma\left(i\right)}<X_{i+1}\right\} )=\frac{1}{\left(i+1\right)!}=P\left(B_{\sigma}\right)P\left(A_{i+1}\right)$

Now realize that every event $E_{1}\cap\cdots\cap E_{i}$ can be written as a finite union of disjoint events $B_{\sigma}$.

An immediate consequence is that: $$P\left(E_{1}\cap\cdots\cap E_{i}\cap A_{i+1}\right)=P\left(E_{1}\cap\cdots\cap E_{i}\right)P\left(A_{i+1}\right)$$ This completes the proof.

This is an adapted version of this answer. It wouldn't suprise me if a more concise proof can be given.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .