what is the probability that a scissor became the champion? - MathOverflow

what is the probability that a scissor became the champion?

2012-10-17T21:46:19Z

Here is a question from one of my students:

suppose 8 players are in an elimination match. The players are marked with marked with either R (for rock), P (for paper) or S (for scissors). If two players are marked with the same letter, then one is picked as winner of this round. An example of this sort of matches is:

First round：R-P S-S R-S P-S

Second round： P-S R-S

Third round： S-R

Champion： R

The question is：Given r+p+s=8, for the match that there are r many R, p many P and s many S, if the table for the elimination match is assigned randomly, what is the probability that a S became the champion?

A more general question is: for a match with 2^n players, and given r+p+s=2^n, how much chance can some S wins the champion?

My answer did not meet his satisfaction. What I know is, firstly for small n, one can list all possibilities (there are (2^n)! many, if we make a distinction between two rocks etc.)and find the answer; secondly, one may use a computer program to solve the general question by inputting r,p and s; thirdly, one can also do some induction to find a pattern for the general question; and lastly, if the number r,p and s are assigned randomly and we let n goes to infinity, and the answer should be a third.

So can we have some smart ways to figure out these questions? Or can we reduce them to other known questions? I guess graph theory may help but my knowledge is very limited there.

Answer by Robert Israel for what is the probability that a scissor became the champion?

2012-10-17T22:54:01Z

Let $R(r,p,s)$, $P(r,p,s)$, $S(r,p,s)$ be the probabilities of rock, paper, scissors with initial distribution $r,p,s$, where $r + p + s$ is a power of $2$. Now for $r+p+s = 2^{n+1}$, rock will win the last round if the results of the second-last round are rock and rock or rock and scissors, so considering the probability ${r \choose r'}{q \choose q'}{s \choose s'}/{{2^{n+1}} \choose {2^{n}}}$ of the first half of the contestants being marked with $r'$, $q'$, $s'$ rocks, paper and scissors, we get $$ \eqalign{R(r,p,s) &= \sum_{r'+p'+s'=2^n} \dfrac{{r \choose r'}{p \choose p'}{s \choose s'}}{{2^{n+1}} \choose {2^{n}}} (R(r',p',s') S(r-r',p-p',s-s')\cr & + R(r',p',s') R(r-r',p-p',s-s') + S(r',p',s') R(r-r',p-p',s-s'))\cr}$$ the sum being over all $r', p', s'$ with $0 \le r' \le r$, $0 \le p' \le p$, $0 \le s' \le s$ and $r' + p' + s' = 2^n$, and similarly with $R,S$ replaced by $P,R$ or $S,P$.

Answer by Douglas Zare for what is the probability that a scissor became the champion?

2012-10-18T01:25:47Z

It's not immediate whether rock can win at all, although I think it should be possible to work that out. For example, if $(r,p,s) = (3,4,1)$ then rock can't win, but at $(2,4,2)$ rock wins with probability $8/105$.

$3^8$ is only $6561$ so I wrote a few lines of Mathematica code to enumerate the $8$-player tournaments. Here is a table of probabilities with which rock wins:

(8,0,0): 1
(7,1,0): 0  (7,0,1): 1
(6,2,0): 0  (6,1,1): 1/7   (6,0,2): 1
(5,3,0): 0  (5,2,1): 2/21  (5,1,2): 1/3     (5,0,3): 1
(4,4,0): 0  (4,3,1): 1/35  (4,2,2): 23/105  (4,1,3): 19/35  (4,0,4): 1
(3,5,0): 0  (3,4,1): 0     (3,3,2): 6/35    (3,2,3): 3/7    (3,1,4): 26/35   (3,0,5): 1
(2,6,0): 0  (2,5,1): 0     (2,4,2): 8/105   (2,3,3): 2/5    (2,2,4): 74/105  (2,1,5): 19/21  (2,0,6): 1
(1,7,0): 0  (1,6,1): 0     (1,5,2): 0       (1,4,3): 8/35   (1,3,4): 16/35   (1,2,5): 2/3    (1,1,6): 6/7  (1,0,7): 1

Answer by Richard Stanley for what is the probability that a scissor became the champion?

2012-10-18T21:15:26Z

Here is a generating function approach. A $P$-tree $T$ of length $n$ is a complete binary tree of length $n$ with vertices labelled $p,r,s$ such that the root is $p$, the children of $p$ are either $p,p$ or $p,r$, the children of $r$ are either $r,r$ or $r,s$, and the children of $s$ are either $s,s$ or $s,p$. Similarly define $R$-trees and $S$-trees. The weight $w(T)$ is the product of all leaf vertices. Let $P(n)=\sum_T w(T)$, summed over all $P$-trees of length $n$, and similarly define $R(n)$ and $S(n)$. Thus $$ P(0)=p,\ \ \ P(1)=p^2+2pr, $$ $$ P(2)=p^4+4p^3r+6p^2r^2+4sp^2r+4pr^3+8pr^2s. $$ Clearly $$ P(n+1) = P(n)^2+2P(n)R(n), $$ and similarly for $R(n+1)$ and $S(n+1)$. We can eliminate two of the functions from these three recurrences and obtain a recurrence for each function alone. For $P(n)$ the recurrence is the following, writing e.g. $p3$ for $P(n+3)$: $$ 0 = 4 p2^4 p0^4+p2^2 p1^6-p2 p1^8-8 p1^5 p0^2 p3+16 p1^4 p0^4 p3 $$ $$ -8 p1^3 p0^6 p3+4 p1^2 p0^4 p2^3-16 p1 p0^6 p2^3+12 p1^7 p0^2 p2 $$ $$ -18 p1^6 p0^4 p2+12 p1^5 p0^6 p2-4 p2^2 p1^5 p0^2+12 p0^6 p2^2 p1^3$$ $$ -6 p2^2 p1^4 p0^4+9 p1^2 p0^8 p2^2-9 p2 p1^4 p0^8. $$ Is there a simpler recurrence? The highest term is $p3=P(n+3)$, so the initial conditions are $P(0),P(1),P(2)$. The coefficient of $p3$ is $$ -8 p1^5 p0^2+16 p1^4 p0^4-8 p1^3 p0^6. $$ Thus there is a "Laurent phenomenon" behavior, since it is not at all a priori clear why we get an answer that is a polynomial (with nonnegative coefficients). For more on the Laurent phenomenon, see e.g. http://arxiv.org/abs/math/0104241.