5
$\begingroup$

This problem is from the Simon Marais Mathematics Competition Paper B which was conducted a couple of weeks ago (on October 14, 2023).

Problem statement (verbatim):

There are $256$ players in a tennis tournament who are ranked from $1$ to $256$, with $1$ corresponding to the highest rank and $256$ corresponding to the lowest rank. When two players play a match in the tournament, the player whose rank is higher wins the match with probability $\frac{3}{5}$.

In each round of the tournament, the player with the highest rank plays against the player with the second highest rank, the player with the third highest rank plays against the player with the fourth highest rank, and so on. At the end of the round, the players who win proceed to the next round and the players who lose exit the tournament. After eight rounds, there is one player remaining in the tournament and they are declared the winner.

Determine the expected value of the rank of the winner.

My attempt:

Define a random variable $X$ denoting rank of a player.

Define $P(X=n)$ to be the probability that a player with rank $n$ will be the winner.

We want to determine $$\mathbb E[X]=\sum_{n=1}^{256} n\cdot P(X=n) $$

There are $2^8$ players in the first round, $2^7$ in the second round after elimination,..., $2^{9-k}$ in the $k$-th round, and finally $2$ players in the $8$-th i.e., final round.

With this in mind, I attempted to find a probability distribution.

$P(X=1)=\left(\frac{3}{5}\right)^8$ because 1 is the highest rank and this player has equal chances to win all the $8$ rounds.

$P(X=2)=\left(\frac{2}{5}\right)\left(\frac{3}{5}\right)^7$ because if rank 2 can beat 1 in the first round, in following rounds, the opponents will be lower ranked.

For the sake of brevity, let $a:=3/5$ and $b:=2/5$.

I computed like this till $n=10$ on my own speculating on the opponent and rounds for each player. I hope I haven't made mistake anywhere. $\displaystyle \begin{array}{ c|c|c|c|c|c|c|c|c|c|c } \text{Rank} \ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline P( X=n) & a^{8} & a^{7} b^{1} & a^{7} b^{1} & a^{6} b^{2} & a^{7} b^{1} & a^{6} b^{2} & a^{6} b^{2} & a^{5} b^{3} & a^{7} b^{1} & a^{6} b^{2} \end{array}$

I could generalize that $$P(X=2^k)=a^{8-k}b^k$$ $$P(X=2^k-1)=P(X=2^k-2)=a^{8-k+1}b^{k-1}$$

I am unable to proceed further.

$\endgroup$
1
  • 1
    $\begingroup$ Have you tried a recursive approach? Starting with the least significant bit. $\endgroup$ Oct 28, 2023 at 15:16

1 Answer 1

1
$\begingroup$

Probability mass function approach (see next heading for nicer approach)

Let $r$ be the player's zero-indexed-rank, defined as the player's rank minus $1$. This allows us to use the binary expansion, $b(r)$, of $r$.

Let $W$ be the zero-indexed-rank of the winner. Let $p = 3/5$ (your "$a$") be the probability of the higher-ranked player winning a given match.

Let $1(b)$ and $0(b)$ be the number of $1$'s and $0$'s in a binary number respectively.

Observe that $$P(W = r) = p^{0(b(r))}(1-p)^{1(b(r))}.$$

Now the expectation,

$$ \begin{align} E(W) &= \sum_{r=0}^{2^8-1}rP(W=r) \\ &= \sum_{i=0}^8\left( p^{8-i}(1-p)^{i} \left[\sum_{r:1(b(r))=i}r\right] \right) \\ \end{align}$$

To calculate $\sum_{r:1(b(r))=i}r$, use the fact that there are $\binom{8}{i}$ terms, and that, by symmetry, each of the $8$ binary digits must appear as "$1$" the same number of times when you view each term as a binary expansion.

Because each term has $i$ "$1$"s, we have that each binary digit appears $\binom{8}{i}\frac{i}{8}$ times. So the sum is $\binom{8}{i}\frac{i}{8}(2^8-1)$. So the expectation is

$$ \begin{align} E(W) &= \sum_{i=0}^8\left( p^{8-i}(1-p)^{i} \left[\binom{8}{i}\frac{i}{8}(2^8-1)\right] \right) \\ &=\frac{2^8-1}{8}\sum_{i=0}^8i\binom{8}{i} p^{8-i}(1-p)^{i}\\ &=\frac{2^8-1}{8}E(Y) \end{align} $$

where $Y\sim$Binomial$(8, 1-p)$, so $E(W) = \frac{2^8-1}{8}8\frac25 = 102.$ Converted to the rank defined in the question, the answer is $103$.

(By the way, we usually call such ranks "seeds" in real life. However, real tournaments don't work like this obviously. Notice that $P(W=1) = P(W=128)$ which is clearly not very realistic. This process's expected winner's rank-percentile is $1-p=2/5=40\%$, which is only slightly higher than the random chance of $50\%$.)

Alternative (simpler) approach using recursion

After seeing that the answer is $(N-1)(1-p)+1$ where $N$ is the number of players, I had a feeling that I've severely over-complicated the problem.

Sure enough, consider $4$ players ranked $0, 1, 2, 3$. Then the expected rank from $0,1$ is $0.4$ and that from $2,3$ is $2.4$. Then taking the expectation again is $0.4\times0.6+2.4\times0.4 = 1.2 = 3\times0.4$.

This pattern continues. We want to prove that, for each subtree $t$, its expected rank of the winner is $$E_{[a,b]} = (b-a)(1-p)+a,$$ where $a,b$ are the minimum and maximum rank of the descendents of $t$ respectively. (Note that I don't bother saying "zero-indexed rank" anymore -- this formula is invariant under constant rank shifts, that is, if $a, b \to a + c, b + c$, then $E \to E + c$. This invariance also allows us to just prove it for $a=0$)

We proceed by induction on the depth $n$ of the subtree. The base case $n=1$ is true because $E = 0\times p + 1\times (1-p) = (1-0)(1-p)+0.$

Now assume the hypothesis is true for $n=k$. Then for a depth $n=k+1$ subtree with ranks $0,\dots,2^{k+1}-1$, we have

$$ \begin{align} E_{[0,2^{k+1}-1]} &= E_{[0,2^{k}-1]}p+E_{[2^k,2^{k+1}-1]}(1-p)\\ &= (((2^k-1)-0)(1-p)+0)p+(((2^{k+1}-1)-2^k)(1-p)+2^k)(1-p)\\ &=(2^k-1)(1-p)(p+(1-p))+2^k(1-p)\\ &=(2^{k+1}-1)(1-p)\\ &=((2^{k+1}-1)-0)(1-p)+0 \end{align} $$

which proves $n=k+1$. In particular the formula is true for $n=8$ which proves our claim.

$\endgroup$
6
  • 1
    $\begingroup$ Sharp observation. This is so cool! :) $$P(W = r) = p^{0(b(r))}(1-p)^{1(b(r))}$$ $\endgroup$ Oct 28, 2023 at 16:05
  • 2
    $\begingroup$ Thank you. I noticed it because each player's path in the tournament bracket (binary-tree) is completely pre-determined (if they keep winning). Stepping in the tree one way gives $p$ while stepping the other way gives $1-p$. $\endgroup$ Oct 28, 2023 at 16:09
  • 1
    $\begingroup$ > Let $1(b)$ and $0(b)$ be the number of $1$'s and $0$'s in a binary number respectively. Did you mean number of $0$'s and $1$'s in $8$-bit representation? For example, $128=10000000_b$ and $1=00000001_b$. Now I understand the intuition behind indexing the ranks from $0$. It's so that $256$ doesn't take up $9$ bits. $\endgroup$ Oct 28, 2023 at 16:21
  • 1
    $\begingroup$ Yea so $1(b(128))=1(b(1))=1$. $\endgroup$ Oct 28, 2023 at 16:42
  • 1
    $\begingroup$ Please check the alternative nicer approach, which is the approach I hinted at originally in the comments about "recursion starting with the least significant bit". Note that we never need to calculate $P(W=r)$ in this alternative approach. $\endgroup$ Oct 28, 2023 at 20:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .