I am solving some questions in Introduction to Probability Models by Sheldon Ross as part of my preparation for my upcoming exams. I am stuck on this problem number 62 from Chapter 2.
If $\{a_i\}$ is an ascending ordered set of numbers. Then $N_i$ is the number of terms $a_k \ ;\ k<i$ such that $a_k$ appears after $a_i$ in the permutation.
My attempt
So I could see that $N_i < i$, since we only have that many terms that can cause an inversion for $a_i$.
I tried solving for small values of $i$. We can see $P(N_1 = 0) = 1$ since no $a_k$ exists such that $k<1$, since $a_1$ is the smallest number.
$P(N_2 = 0) = \frac{((n-1)+(n-2)+\cdots+1)(n-2)!}{n!} = \frac{1}{2}$
So we can fix $a_2$'s position in the permutation and notice there are $n-1$ free positions for $a_1$. The more to the right we fix the position the less possible places $a_1$ can take and still only cause $0$ inversions. The rest $n-2$ numbers can take any of the other places so that gives us the number of favorable permutations. The denominator is the total number of possible permuatations.
Now for the case of $N_i=r$, we have $i-1$ numbers that are potential candidates for an inversion.
To get exactly $r$ inversions we need to select which $r$ positions of the available $k$ is taken by these numbers. Then which $r$ of the $i-1$ numbers comes after $a_i$ in the permutation. We can now permute the positions of these $r$ numbers among themselves and the rest $(n-r)$ terms can also take any position they want.
We now sum over all the possible $k$'s which is determined by fixing the position of $a_i$.
$P(N_i = r) = \frac{\sum_{k=r}^{n-i-r} {k \choose r}{i-1 \choose r} (n-r)! r!}{n!}$
But this seems overly complex and wrong. Can you help with finding the distribution of $Ni$? Also I planned to show all $n$ random variables are independent (part a) by first showing that $N_i$ is independent to $N_{i-1}, N_{i-2}, \cdots, N_1$.
Best Answer
When considering $N_i$, you only care about the relative positions of $a_1, \ldots, a_i$; you can ignore $a_{i+1}, \ldots, a_n$ and consider the $i!$ permutations of $a_1, \ldots, a_i$. The event that $N_i = r$ is the same as $a_i$ appearing in position $i-r$ among these $i$ objects, which is $\frac{1}{i}$. So $N_i$ is uniform over $\{0, 1, \ldots, i-1\}$.
The above argument is actually rigorous. But if you want to count everything explicitly, here is a more detialed explanation. The event $N_i = r$ means that exactly $r$ of $a_1, \ldots, a_{i-1}$ appears after $a_i$. In particular, this means $i-1-r$ of $a_1, \ldots, a_{i-1}$ appear before $a_i$ and $r$ of them appear after $a_i$. So among these $i$ objects, $a_i$ appears in the $i-r$ position, and there are $(i-1)!$ ways to position the remaining $a_1, \ldots, a_{i-1}$.
We have so far counted the number of ways to order $a_1, \ldots, a_i$ among themselves. Now let's consider all $n$ objects. There are $\binom{n}{i}$ ways to choose $i$ positions for $a_1, \ldots, a_i$; the remaining $n-i$ positions will be filled by $a_{i+1}, \ldots, a_n$, and there are $(n-i)!$ ways to order these objects.
Combining everything and dividing by $n!$ yields $$\frac{1}{n!} (i-1)! \binom{n}{i} (n-i)! = \frac{1}{n!} (i-1)! \frac{n!}{i!} = \frac{1}{i}.$$