what is the probability that a scissor became the champion? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:55:35Z http://mathoverflow.net/feeds/question/109955 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109955/what-is-the-probability-that-a-scissor-became-the-champion what is the probability that a scissor became the champion? unknown (google) 2012-10-17T21:46:19Z 2012-10-18T23:53:25Z <p>Here is a question from one of my students:</p> <p>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:</p> <p>First round：R-P S-S R-S P-S</p> <p>Second round： P-S R-S</p> <p>Third round： S-R</p> <p>Champion： R</p> <p>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?</p> <p>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?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/109955/what-is-the-probability-that-a-scissor-became-the-champion/109959#109959 Answer by Robert Israel for what is the probability that a scissor became the champion? Robert Israel 2012-10-17T22:54:01Z 2012-10-17T22:54:01Z <p>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) &amp;= \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 &amp; + 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$.</p> http://mathoverflow.net/questions/109955/what-is-the-probability-that-a-scissor-became-the-champion/109964#109964 Answer by Douglas Zare for what is the probability that a scissor became the champion? Douglas Zare 2012-10-18T01:25:47Z 2012-10-18T01:25:47Z <p>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$.</p> <p>$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:</p> <pre><code>(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 </code></pre> http://mathoverflow.net/questions/109955/what-is-the-probability-that-a-scissor-became-the-champion/110043#110043 Answer by Richard Stanley for what is the probability that a scissor became the champion? Richard Stanley 2012-10-18T21:15:26Z 2012-10-18T23:53:25Z <p>Here is a generating function approach. A $P$-<em>tree</em> $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 <em>weight</em> $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 <em>a priori</em> clear why we get an answer that is a polynomial (with nonnegative coefficients). For more on the Laurent phenomenon, see e.g. <a href="http://arxiv.org/abs/math/0104241" rel="nofollow">http://arxiv.org/abs/math/0104241</a>.</p>