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 '15 at 10:55

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.


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.