Intuitive solution of an order combinatorics problem

Question

I am seeking a quick and intuitive one-or-two-step solution to the following combinatorics/probability problem.

Suppose $m$ men and $w$ women compete in a tournament. All rankings are equally likely. What is the expected overall ranking of the $k$'th ranked woman?

I already know the answer through brute force computation of $\sum_s sP(s|k)$ where $P(s|k)$ stands for the probability of the $k$'th ranked woman ranking $s$ overall. What are the intuitive arguments to obtain the solution in one or two steps?

Answer 1

Let $w$ be fixed and $X_{k,m}$ represent the random variable of the overall ranking of the $k$th woman when there are $m$ men, where $1 \leq k \leq w$.

We start with $m=0$ and proceed inductively.

Clearly $E[X_{k,0}] = k$.

Given $X_{k,m}$, we wish to evaluate $X_{k,m+1}$. Let us insert $1$ additional man into the picture. We only need to consider where he is in relation to the women: there are $w+1$ places he can go. There is a one-to-one correspondence over $i\in\{0,1,2,...,w\}$ amongst the configurations where he is between the $i$'th and $i+1$'th women. So the probabilities of him being between any adjacent women are equal. There is a probability of $\frac{k}{w+1}$ that $X_{k,m+1} = X_{k,m}+1$ (i.e. the man goes in front of the $k$th woman). Otherwise $X_{k,m+1} = X_{k,m}$ (i.e. the ranking of the $k$th woman remains unchanged).

This gives us $E[X_{k,m+1}] = E[X_{k,m}] + \frac{k}{w+1}$. Solving recursively gives us $E[X_{k,m+1}] = k + \frac{mk}{w+1}$.

Answer 2

Thanks @Hans for clarifying. If I understand you correctly, you mean for $i,j \in \{1, 2, ... w\}$ with $i \neq j$, there is a sample-point-by-sample-point correspondence by swapping all the men in section $i$ with all the men in section $j$ (while keeping their rank). That is certainly true and would indeed enable the use of @Kelvin's trick of using $\frac{1}{w+1}$. Sorry that was not obvious to me to begin with. Here is maybe an easier (and certainly equivalent) way to use the "swapping".

We are given that each of the $(m+w)!$ permutations is equally likely. In each permutation $\pi$, the men are divided into $w+1$ "sections", separated by the $w$ women. (Some sections might be empty.) Let $M_0(\pi), M_1(\pi), \cdots, M_w(\pi)$ denote the number of men in each section. Next we show that $M_i$ and $M_j$ have identical distributions (though not independent).

Consider a function $f$ which swaps the $i$th and $j$th sections of $\pi$ (while maintaining the men's internal rankings within each section) to obtain a new permutation $f(\pi)$. (Note: $\pi = f(\pi)$ if both sections are empty.) Clearly $f$ is bijective; in fact $f = f^{-1}$. Also $M_i(\pi) = M_j(f(\pi))$ and $M_j(\pi) = M_i(f(\pi))$ by construction of $f$.

Now consider any value $r$ and these two sets:

$$S = \{ \pi: M_i(\pi) = r \}$$

$$T = \{ \sigma: M_j(\sigma) = r \}$$

We have: $f(S) \subset T$ (because $M_i(\pi) = r \Rightarrow M_j(f(\pi)) = r$) and similarly $f(T) \subset S$. But since $f$ is bijective, this means $|S| = |f(S)| \le |T|$ and $|T| = |f(T)| \le |S|$, which further means $|S| = |T|.$ Adding the fact that all permutations are equally likely, we have:

$$P(M_i=r) = \frac{|S|}{(m+w)!} = \frac{|T|}{(m+w)!} = P(M_j=r)$$

which directly proves that $M_i$ and $M_j$ have the same distribution. Finally, $\forall \pi: \sum_{0 \le i \le w} M_i(\pi) = m$, so we can use linearity of expectations to obtain first: $E[M_i] = \frac{m}{1+w}$, and then: expected total no. of men before the $k$th woman $= E\big[\sum_{0 \le i < k} M_i\big] = \frac{km}{1+w}$.