In a tournament $n$ players take part in a series of duels

Question

I've recently been thinking about this problem and I think I solved it correctly. However, I was using a rather peculiar method with lots of algebra. I'll post my solution as an answer below. Is there a better (or just different) way of solving this problem?

Problem

In a tournament $n$ players take part in a series of duels in which both players have equal chances of winning. After each duel the winner plays against the player, that hasn't played for the longest time (or in the beginning someone that hasn't played yet). The first player to beat all other players in consecutive duels wins the tournament. What is the probability that a player wins the tournament given that he takes part in the first duel?

An example with $n=3$

Alice and Bob start and Colin sits out first. Alice beats Bob, Colin beats Alice, Bob beats Colin, Bob beats Alice. Bob wins the tournament.

Here Alice, Bob and Colin had winning probabilities $\frac{5}{14}$, $\frac{5}{14}$, $\frac{4}{14}$ respectively.

EDIT: Only 3 days left for the bounty. We don't want those points to disappear into nirvana, do we? :(

Answer 1

Here's is an answer using a slightly different approach.

We denote the $n$ players with $player_1$ to $player_n$ according to the order of their duels. So the first duel is between $player_1$ and $player_2$, the next duel is the winner of the first duel with $player_3$ until finally $player_n$ has his chance to win the game.

Let's denote with $p_k$ the probability that the $k$-th player win's, i.e. he is the first who wins $n-1$ consecutive duels against all other players.

The idea for the Ansatz below is that the structure of the binary decision tree for $player_k$ is essentially the same as for $player_{k+1}$ with a shift of one duel and this holds for all players $player_k$ with $2\leq k\leq n-1$.

For $player_1$ and $player_2$ the decision tree is symmetric, so we have $p_1=p_2$.

For $player_k$ and $player_{k+1}$ the following is valid \begin{align*} p_1&=p_2\tag{1}\\ p_k&=\left(1+\frac{1}{2^{n-1}}\right)p_{k+1}\qquad2\leq k \leq n-1\tag{2} \end{align*}

The equation in $(2)$ tells us, that $p_{k}$ is essentially equal to $p_{k+1}$ with the advantage, that a run of $n-1$ consecutive duels was already done by $player_k$. Thereby correspond $n-1$ consecutive duels to the factor $\frac{1}{2^{n-1}}$ and this path of length $n-1$ in the binary decision tree is weighted with the sum of all probabilities of the nodes in the tree where $player_{k+1}$ resides. This corresponds to the multiplication with $p_{k+1}$.

This Ansatz gives us following system of equations:

\begin{align*} p_1+p_2+\dots+p_n&=1\tag{3}\\ p_1&=p_2\tag{4}\\ p_k&=p_n\left(1+\frac{1}{2^{n-1}}\right)^{n-k}\qquad 2\leq k \leq n-1\tag{5} \end{align*}

Note: Please observe how the probabilities $p_k$ are built from $p_n$. If we know the stopping probability of $player_n$ and the proportion of probabilites between two consecutive players we know the probability for all players. So $(5)$ gives us a proper insight into the behaviour of the game.

Now substituting $(4)$ and $(5)$ in $(3)$ gives

\begin{align*} p_n=\frac{1}{1+\left(1+\frac{1}{2^{n-1}}\right)^{n-2}+\sum_{k=2}^{n-1}\left(1+\frac{1}{2^{n-1}}\right)^{n-k}}\qquad (n\geq2) \end{align*}

If we use $q_n:=1+\frac{1}{2^{n-1}}$ as shorthand we get after some simplifications

\begin{align*} p_n&=\frac{1}{1+q_n^{n-2}+\sum_{k=2}^{n-1}q_n^{n-k}}\\ &=\frac{1}{2^{n-1}}\left(\frac{1}{2q_n^{n-1}-q_n^{n-2}-1}\right)\qquad (n\geq2)\\ \end{align*}

Since $p_k=q_n^{n-k}p_n$ we finally get for $n\geq 2$

\begin{align*} p_1&=p_2\\ p_k&=\frac{1}{2^{n-1}}\left(\frac{\left(1+\frac{1}{2^{n-1}}\right)^{n-k}} {\left(1+\frac{1}{2^{n-2}}\right)\left(1+\frac{1}{2^{n-1}}\right)^{n-2}-1}\right)\qquad(2\leq k\leq n)\tag{6}\\ \end{align*}

Note: Setting $k=2$ in $(6)$ gives the probability for $player_1$ resp. $player_2$ to win, which corresponds to the value $p(n)$ in the answer from alex.

Answer 2

My solution, based on setting up a matrix equation and then using the adjugate matrix to find the essential entries of the inverse matrix.

(or click https://i.stack.imgur.com/PSvKd.png if it's too small)

So apparently a formula for the probability that the first player wins the whole tournament is $$p(n)=\frac{2^{n+1}(2^{n-1}+1)^{n}}{2^{n+2}(2^{n-1}+1)^{n}+(2^{n+1}+4)^{n}-(4^{n}+4)\cdot2^{n^{2}-n}-2^{n^{2}+2}}$$

e.g. $p(1)=1$, $p(2)=\frac{1}{2}$, $p(3)=\frac{5}{14}$, $p(4)=\frac{81}{298}$

EDIT: Here's an explanation of the initial formulas above. In the following table the cell at row $i$ and column $j$ represents the state in which you stand at the $i$th position in the queue and the person in front has already won $j$ duels in a row. Let's call that state $s_{i,j}$. Let the probability of winning starting at state $s_{i,j}$ be $q_{i,j}$. Then $q_{i,1}=p_i$, which I had defined above. Note, that I have duplicated the nth row for convenience.

Now, each blue arrow represents either outcome of the next duel which both occur with probability $1/2$. From the diagram you can see that you can only win if you reach the $1$ in the rightmost column.

We have $q_{2,1}=\frac{1}{2} q_{1,1} + \frac{1}{2} q_{n,2}$ and $q_{n,2}=\frac{1}{2} q_{n-1,1} + \frac{1}{2} q_{n-1,3}$ etc.

So indeed $$q_{2,1}=\frac{1}{2} q_{1,1} + \frac{1}{4} q_{n-1,1} + ... + \frac{1}{2^{n-2}} q_{3,1}$$ which is the first of my formulas. The others are found similarly.