¿cuál es la probabilidad de que una tijera se convirtió en el campeón?

Question

Aquí está una pregunta de uno de mis alumnos:

supongamos que 8 jugadores en una eliminación de partido. Los jugadores están marcados con marcadas con R (rock), P (para el papel) o S (de tijera). Si dos jugadores están marcados con la misma letra, entonces uno es elegido como ganador de esta ronda. Un ejemplo de este tipo de partidos es:

Primera ronda: el R-P S-S R-S P-S

Segunda ronda: el P-S R-S

Tercera ronda: el S-R

Campeón： R

La pregunta es：Dado r+p+s=8, para el partido que hay r muchos R, p muchas P y s de muchos S, si la tabla para la eliminación partido se asignaron al azar, ¿cuál es la probabilidad de que un S se convirtió en el campeón?

Una pregunta más general es: por un partido con 2^n jugadores, y dado r+p+s=2^n, ¿cuánto oportunidad puede que algunos S gana el campeón?

Mi respuesta no cumplir con su satisfacción. Lo que quiero saber es, en primer lugar para los pequeños de n, uno puede hacer una lista de todas las posibilidades (hay (2^n)! muchos, si hacemos una distinción entre dos rocas, etc.)y encontrar la respuesta; en segundo lugar, se puede utilizar un programa de computadora para resolver la cuestión general mediante la introducción de r,p y s; en tercer lugar, también se puede hacer algunos de inducción para encontrar un patrón para la pregunta general; y, por último, si el número de r,p y s son asignados al azar y dejamos que n tiende a infinito, y la respuesta debe ser un tercero.

Así, podemos tener algunas maneras inteligentes para calcular estas preguntas? O podemos reducirlos a otras preguntas? Supongo que la teoría de grafos puede ayudar, pero mi conocimiento es muy limitado allí.

Answer 1

Aquí está una generación de función de enfoque. Un $P$-árbol de $T$ de la longitud de la $n$ es un completo árbol binario de longitud $n$ con vértices etiquetados $p,r,s$ tal que la raíz es $p$, los hijos de $p$ son $p,p$ o $p,r$, los hijos de $r$ son $r,r$ o $r,s$, y la de los niños de $s$ son $s,s$ o $s,p$. Del mismo modo definen $R$-árboles y $S$-de los árboles. El peso de la $w(T)$ es el producto de todas las hojas los vértices. Deje $P(n)=\sum_T w(T)$, sumando todos los $P$-árboles de longitud $n$, y de igual manera definir $R(n)$ e $S(n)$. Así $$ P(0)=p,\ \ \ P(1)=p^2+2pr, $$ $$ P(2)=p^4+4p^3r+6p^2r^2+4sp^2r+4pr^3+8pr^2s. $$ Claramente $$ P(n+1) = P(n)^2+2P(n)R(n), $$ y lo mismo para $R(n+1)$ e $S(n+1)$. Podemos eliminar dos de los las funciones de estos tres recurrencias y obtener una periodicidad de cada función solo. Para $P(n)$ la recurrencia es la siguiente, escrito por ejemplo, $p3$ para $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. $$ Hay una forma más simple de recurrencia? La mayor plazo es $p3=P(n+3)$, por lo que el las condiciones iniciales se $P(0),P(1),P(2)$. El coeficiente de $p3$ es $$ -8 p1^5 p0^2+16 p1^4 p0^4-8 p1^3 p0^6. $$ Por lo tanto no es un "Laurent" el fenómeno del comportamiento, ya que no es en absoluto un a priori claro por qué hemos de obtener una respuesta que es un polinomio (con no negativo de los coeficientes). Para obtener más información sobre las Laurent fenómeno, ver por ejemplo, http://arxiv.org/abs/math/0104241.

Answer 2

Vamos $R(r,p,s)$, $P(r,p,s)$, $S(r,p,s)$ ser las probabilidades de piedra, papel, tijeras con la distribución inicial $r,p,s$ donde $r + p + s$ es una potencia de $2$. Ahora para $r+p+s = 2^{n+1}$, el rock va a ganar la última ronda si los resultados de la penúltima ronda de la roca y roca o el rock y las tijeras, por lo que teniendo en cuenta la probabilidad de ${r \choose r'}{q \choose q'}{s \choose s'}/{{2^{n+1}} \choose {2^{n}}}$ de la primera mitad de los concursantes está marcada con $r'$, $q'$, $s'$ rocas, papel y tijeras, obtenemos $$ \eqalign{R(r,p,s) &= \sum_{r'+p'+s'=2^n} \dfrac{{r \elegir r'}{p \elegir p'}{s \elegir s'}}{{2^{n+1}} \, seleccione {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}$$ la suma es sobre todos los $r', p', s'$ con $0 \le r' \le r$, $0 \le p' \le p$, $0 \le s' \le s$ y $r' + p' + s' = 2^n$, y del mismo modo con $R,S$ reemplazado por $P,R$ o $S,P$.

Answer 3

No es inmediata si el rock puede ganar en todo, aunque yo creo que debería ser posible trabajar en eso. Por ejemplo, si $(r,p,s) = (3,4,1)$, entonces el rock no puede ganar, pero en $(2,4,2)$ rock gana con probabilidad de $8/105$.

$3^8$ solo $6561$ así que he escrito un par de líneas de código de Mathematica para enumerar las $8$-jugador de torneos. Aquí hay una tabla con las probabilidades con que el rock de los premios:

(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