Probability for Minimum of Random Permutation

199 Views Asked by At

Consider a random permutation $\pi$ of the set $\lbrace 1, \cdots, n\rbrace$ and consider the event $E_i := \lbrace \pi : \pi_i = \min\left(\pi_1, \cdots, \pi_i\right) \rbrace$ and the indicator random variable $X_i(\pi) = \mathbb{1}[\pi \in E_i]$ for this event. It is intuitive that $P[E_i] = \frac{1}{i}$ because if we just look at the first $i$ numbers of the permutation sequence, the chance that any number is the minimum is $1/i$.

What I want to try and show is that $X_i$ is independent from $X_{i-1}$. This seems intuitively the case since knowing $\pi_{i-1}$ is the minimum of its previous subsequence does not necessarily mean $\pi_{i}$ will or will not be the minimum of its corresponding subsequence. However, I am not sure how to rigorously show this? Clearly the intersection of $E_i \bigcap E_{i-1} \neq \emptyset$, so the question is does $P[E_i \bigcap E_{i-1}] = P[E_i] P[E_{i-1}] = \frac{1}{i (i-1)}$. Alternatively, how can we show that $P[E_i | E_{i-1}] = P[E_i]$? Any tips are welcome.

A more general version of this I am looking into is showing that for sime fixed $k$, $P[X_i = x | X_{i_1}, X_{i_2}, \cdots, X_{i_k}] = P[X_i = x]$ for distinct $i_j \in \lbrace 1, \cdots, n\rbrace$. I am not really sure how to go about showing either of these, but clearly this more general version of independence leads to the simpler one stated above.

Perhaps some tips on the simpler problem will help me see how to tackle this latter one.

1

There are 1 best solutions below

6
On BEST ANSWER

So in the intersection event if $\pi \in E_i\cap E_{i-1}$ we know that $\min \{\pi _1,\cdots,\pi _i\}=\min \{\min \{\pi_1,\cdots ,\pi _{i-1}\},\pi _i\}=\min \{\pi _{i-1},\pi _i\}=\pi _i,$ hence $$P(E_i\cap E_{i-1})=P(\pi _i<\pi _{i-1}<\min \{\pi _1,\cdots ,\pi _{i-2}\})=\frac{\binom{n}{i}(i-2)!(n-i)!}{n!}=\frac{1}{i(i-1)},$$ because you choose $i$ of them from the $n$, you shuffle $i-2$(the order of the first $i-2$ does not matter) and you shuffle the remaining $n-i$ elements.

For your question: $$P(E_2\cap E_7)=P(\pi _7<\pi _2<\pi _1)=\frac{\binom{n}{7}(n-7)!|\{\sigma \in S_6:\sigma _2<\sigma _1\}|}{n!}=\frac{\binom{n}{7}(n-7)!\frac{6!}{2}}{n!}=\frac{1}{7*2}$$