En un torneo $n$ a los jugadores tomar parte en una serie de duelos

Question

Recientemente he estado pensando acerca de este problema y creo que he resuelto correctamente. Sin embargo, yo estaba usando un peculiar método con un montón de álgebra. Voy a publicar mi solución como respuesta a continuación. Existe una mejor (o simplemente diferente) la forma de solucionar este problema?

Problema

En un torneo $n$ a los jugadores tomar parte en una serie de duelos en el que ambos jugadores tienen las mismas posibilidades de ganar. Después de cada duelo el ganador juega contra el jugador, que no ha jugado la mayor parte del tiempo (o en el principio de alguien que no ha jugado aún). El primer jugador para vencer a todos los otros jugadores en duelos consecutivos gana el torneo. ¿Cuál es la probabilidad de que un jugador gana el torneo, dado que él toma parte en el primer duelo?

Un ejemplo con $n=3$

Alice y Bob inicio y Colin se sienta primero. Alice beats Bob, Colin beats Alice, Bob beats Colin, Bob beats Alice. Bob gana el torneo.

Aquí Alice, Bob y Colin tenía probabilidades de ganar $\frac{5}{14}$, $\frac{5}{14}$, $\frac{4}{14}$ respectivamente.

EDIT: Sólo 3 días para la recompensa. No queremos que estos puntos a desaparecer en el nirvana, ¿no? :(

Answer 1

Mi solución, basada en la configuración de una matriz de la ecuación y, a continuación, utilizando la matriz adjunta para encontrar lo esencial de las entradas de la matriz inversa.

(o haga clic en http://i.imgur.com/GFw6XcC.png si es demasiado pequeño)

Así que al parecer una fórmula para la probabilidad de que el primer jugador gana el torneo es $$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}}$$

por ejemplo, $p(1)=1$, $p(2)=\frac{1}{2}$, $p(3)=\frac{5}{14}$, $p(4)=\frac{81}{298}$

EDITAR: He aquí una explicación inicial de las fórmulas anteriores. En la siguiente tabla, la celda de la fila $i$ y la columna $j$ representa el estado en el que usted está de pie en el $i$th posición en la cola y la persona en frente ya ha ganado $j$ duelos en fila. Vamos a llamar a ese estado $s_{i,j}$. Deje que la probabilidad de ganar de partida en el estado de $s_{i,j}$$q_{i,j}$. A continuación,$q_{i,1}=p_i$, lo que yo había definido anteriormente. Nota, que me han duplicado la n-ésima fila para mayor comodidad.

Ahora, cada flecha azul representa el resultado de la siguiente duelo que ambas ocurren con una probabilidad de $1/2$. En el diagrama se puede ver que sólo puede ganar si usted llega a la $1$ en la columna de la derecha.

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

Así que, de hecho, $$q_{2,1}=\frac{1}{2} q_{1,1} + \frac{1}{4} q_{n-1,1} + ... + \frac{1}{2^{n-2}} q_{3,1}$$ que es el primero de mis fórmulas. Los otros se encuentran de manera similar.

Answer 2

Aquí es una respuesta mediante un enfoque ligeramente diferente.

Se denota el $n$ jugadores con $player_1$$player_n$, según el orden de sus respectivos duelos. Así que el primer duelo es entre el$player_1$$player_2$, el siguiente duelo es el ganador del primer duelo con $player_3$ hasta que, finalmente, $player_n$ tiene su oportunidad de ganar el juego.

Vamos a denotar con $p_k$ la probabilidad de que el $k$-th reproductor de win, es decir, él es el primero que gana $n-1$ consecutivos duelos contra otros jugadores.

La idea para el Ansatz a continuación es que la estructura de los binarios de árbol de decisión para $player_k$ es esencialmente el mismo como para $player_{k+1}$ con un cambio de un duelo y esto vale para todos los jugadores de $player_k$$2\leq k\leq n-1$.

Para $player_1$ $player_2$ el árbol de decisión es simétrico, por lo que tenemos $p_1=p_2$.

Para $player_k$ $player_{k+1}$ el siguiente es válido $$\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*}$$

La ecuación de $(2)$ nos dice, que $p_{k}$ es esencialmente igual a $p_{k+1}$ con la ventaja de que una carrera de $n-1$ consecutivos duelos que ya había hecho por $player_k$. Así se corresponden $n-1$ duelos consecutivos para el factor de $\frac{1}{2^{n-1}}$ e este camino de la longitud de la $n-1$ en el binario de árbol de decisión es ponderada con la suma de todas las probabilidades de los nodos en el árbol donde $player_{k+1}$ reside. Esto corresponde a la multiplicación con $p_{k+1}$.

Este Ansatz nos da el siguiente sistema de ecuaciones:

$$\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*}$$

Nota: por Favor, observar cómo las probabilidades de $p_k$ están construidas de $p_n$. Si sabemos que la detención de probabilidad de $player_n$ y la proporción de probabilites entre dos consecutivos jugadores que sabemos que la probabilidad para todos los jugadores. Por lo $(5)$ nos da una adecuada penetración en el comportamiento del juego.

Ahora sustituyendo $(4)$ $(5)$ $(3)$ da

$$\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*}$$

Si utilizamos $q_n:=1+\frac{1}{2^{n-1}}$ como fórmula obtenemos después de algunas simplificaciones

$$\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*}$$

Desde $p_k=q_n^{n-k}p_n$ finalmente, para $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*}$$

Nota: la Configuración de $k=2$ $(6)$ da la probabilidad de $player_1$ resp. $player_2$ a ganar, lo que se corresponde con el valor de $p(n)$ en la respuesta de alex.