6
$\begingroup$

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? :(

$\endgroup$
1
+150
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice! This is exactly what I was looking for. Your solution also gives the winning probabilities for the other players, which is amazing :) I am, however, still confused about equation (2). Could you try explaining it to me with a bit more detail? Thanks! $\endgroup$ – Alex Jul 6 '14 at 20:39
  • $\begingroup$ @Alex: First of all thanks a lot for the bounty! I'm sorry, but at the time I have no better explanation than the rather phenomenological reasoning I'v stated in the answer. I found the relation $(2)$ empirically, based upon three aspects. At first the values for $n=3,4$ with the help of your matrix! Then a concise knowledge of the binary decision tree for $n=3$ as verification for it (based upon regular expressions and derived generating functions). Regrettably for $n>3$ the things become far too complex to describe it in the same way. $\endgroup$ – Markus Scheuer Jul 7 '14 at 17:00
  • $\begingroup$ @Alex: (continued) (which was one of my approaches, namely fully implementing the game and trying to analyse the tree structure). And the third and very important aspect were your equations, which already contain this information! Consider your stated equations $p2=rhs$ and $p3=rhs$. Now transform the first one into $p2-\frac{p3}{2^{n-2}}=\dots$ and the second into $2p_3-p_2=\dots$ ... You see, what I mean? Maybe you could provide a better explanation of $(2)$?!?! :) Best regards! $\endgroup$ – Markus Scheuer Jul 7 '14 at 17:01
  • $\begingroup$ Oh, nice observation. Our formulas are indeed equivalent! You avoided the whole matrix thing with that transformation :) I added a picture to aid in understanding my formulas. By the way, the case for $n=3$ was in one of my exams this summer; I think this generalization resulted in a fun question :D $\endgroup$ – Alex Jul 7 '14 at 18:50
  • $\begingroup$ @Alex: Nice picture, with the formulas below it points out the connection of our answers. :) But, I think that these transition probabilities are limiting (cumulative) probabilities, already adding the probabilities of (structurally) different pathes of the decision tree. So, presumably we won't get a deeper insight of formula $(2)$ from this representation. $\endgroup$ – Markus Scheuer Jul 7 '14 at 19:10
2
$\begingroup$

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

a busy cat

(or click http://i.imgur.com/GFw6XcC.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.

Hi

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.

$\endgroup$
  • 2
    $\begingroup$ Considering that the question is "What is the probability that a player who takes part in the first duel wins the tournament?", I think your probabilities need to be doubled, other than for p(1). $\endgroup$ – Calvin Lin Jun 29 '14 at 18:08
  • $\begingroup$ @CalvinLin Good point. I could have phrased the question better. I meant to ask for the probability that a player wins the tournament given that he takes part in the first duel. $\endgroup$ – Alex Jun 30 '14 at 6:57
  • 1
    $\begingroup$ Your solution seems pretty solid-- I tried to come up with something without reading yours, and went down the same road $\endgroup$ – Phil Tosteson Jul 4 '14 at 23:12

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.