1
$\begingroup$

I would like to learn (more) rigorous approaches to problems I always solve intuitively (as intuition only takes you there some of the time).

Let $P=c_1,c_2,\dots,c_n$ be a permutation on $N$ distinct elements (lets say it is a permutation of integers from $1$ to $N$), and $E_n$ the event that all elements preceding $c_n$ are less than it. $$E_n=\forall_{1\le i<n}\{c_i<c_n\}$$ That is, for a permutation of $N$ distinct integers, what is the probability, that all integers precedig the $n$-th integer in the resulting sequence, are less than it.

Intuitively, $P(E_n)=\frac{1}{n}$. But how could I derive this through conditional and joint probabilities? Because $E$ is really $$E_n=\forall_{1\le i<n}\{c_i<c_n\}\cap\{\text{All permutations of the remaining } N-n\text{ elements}\}$$

Would some be so kind to provide a probabilistic "decomposition", or analysis of this event? How to derive this probability the long way? And what approach would be best suited here, perhaps my definition of $E_n$ is not appropriate.

I think there is a way to derive this through conditional probabilities. Because

given that we do not care about the order of the last $N-n$ elements, what is the probability that that $c_n$ is the largest out of the first $n$ elements of the permutation.

How could I express this mathematically, with events, and compute the needed probabilities? Again, I know how to solve this by thinking about the specifics of this problem. I would like a mathematical derivation, so I can learn more, "the long way".

$\endgroup$
  • $\begingroup$ To check: the permutation is on $N\geq n$ elements, and should be viewed as $(c_1,\dots,c_n,\dots,c_N)$? $\endgroup$ – Clement C. Feb 1 '17 at 20:28
  • $\begingroup$ Yes, its a sequence of $N$ distinct elements. Lets say they are numbers from 1 to N. I will edit the question, original formulation was missing the ordering you mention. $\endgroup$ – LeastSquaresWonderer Feb 1 '17 at 20:30
1
$\begingroup$

I am going to change a little bit your notations, to write the (uniformly randomly chosen) permutation as $\sigma\colon [N]\to [N]$.

We have $$ \Pr[ E_n ] = \sum_{m=1}^N \Pr[ E_n \mid \sigma(n)=m ]\Pr[\sigma(n)=m ] = \frac{1}{N}\sum_{m=1}^N \Pr[ E_n \mid \sigma(n)=m ] $$ by the law of total probability, and the fact that $\Pr[\sigma(n)=m ] = \frac{1}{N}$ for every $m\in[N]$ (as the permutation is chosen u.a.r.).

Now, what is $\Pr[ E_n \mid \sigma(n)=m ]$? Since we condition on the $n$-th "slot" being equal to $m$, we need to have exactly $n-1$ numbers lesser than $m$ in the previous slots. A counting argument immediately shows that there are $\binom{m-1}{n-1}$ such possibilities, out of $\binom{N-1}{n-1}$ choices of assigning the $n-1$ previous slots from the $N-1$ unassigned numbers.

From this counting, we get that the fraction of permutations mapping $n$ to $m$ such that the first $n-1$ numbers are all mapped into $\{1,\dots,m-1\}$ is exactly $$ \frac{\binom{m-1}{n-1}}{\binom{N-1}{n-1}} $$ (note that by definition of the binomial coefficients, this is indeed $0$ if $m <n$), and therefore \begin{align*} \Pr[ E_n ] &= \sum_{m=1}^N \Pr[ E_n \mid \sigma(n)=m ]\Pr[\sigma(n)=m ] = \frac{1}{N}\sum_{m=1}^N \frac{\binom{m-1}{n-1}}{\binom{N-1}{n-1}} = \frac{1}{N}\sum_{m=n}^N \frac{\binom{m-1}{n-1}}{\binom{N-1}{n-1}} \operatorname*{=}^{(\dagger)} \frac{1}{n} \end{align*}

To conclude, it thus only remains to show $(\dagger)$, or equivalently $ \sum_{m=n}^N \frac{\binom{m-1}{n-1}}{\binom{N-1}{n-1}} = \frac{N}{n} $. But this follows from the Hockey-stick identity, which states that $$ \sum_{m=n}^N \binom{m-1}{n-1} = \sum_{m=n-1}^{N-1} \binom{m}{n-1} = \binom{N}{n}. $$

$\endgroup$

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.