Para un torneo de todos contra todos, ¿cuál es el tamaño menos favorito del favorito?

Question

Supongamos que tenemos un round-robin del torneo (es decir, cada jugador juega exactamente un juego con cada otro jugador) con $n$ a los jugadores, que son todos igual de hábil, excepto para un jugador, el favorito, cuya probabilidad de ganar una partida contra otro jugador que es cierto valor fijo $p > 1/2$. Suponga que todos los juegos son independientes, y también que ningún individuo, el juego termina en empate. El ganador del torneo es el jugador que gana la mayoría de los juegos; supongamos que si varios jugadores empatan en el primer lugar, entonces uno de ellos es elegido (uniformemente) al azar para ser el ganador. Deje $\pi(p,n)$ ser la probabilidad de que el favorito gana el torneo.

Hecho. Para cualquier fijo $p>1/2$, $\lim_{n\to\infty} \pi(p,n) = 1$.

Croquis de la prueba: La probabilidad de que un determinado jugador cualquiera puntuaciones más altas que el favorito va a cero a una tasa que es exponencialmente rápido en $n$ (por, por ejemplo, Hoeffding de la desigualdad), pero sólo hay $n$ competidores, por lo que incluso una unión obligado es suficiente para mostrar que la probabilidad de que cualquier jugador puntúa más alto que el favorito va a cero exponencialmente rápido.

A la luz de esta Realidad, puede ser un poco sorprendente que se fija $p$, especialmente para $p$ cerca de $1/2$, el valor de $\pi(p,n)$ hecho rechaza por un tiempo (como $n$ de aumento), y creo que incluso puede oscilar a su alrededor, antes de finalmente subir a 1.

Intuitivamente, lo que está sucediendo para que los pequeños $n$ es que el aumento en el número de competidores es aumentar las posibilidades de que uno de ellos va a hacer bien y el malestar de los favoritos, y que inicialmente es más importante que el hecho de que el aumento en el número de juegos que está dando el favorito de una oportunidad para demostrar una habilidad borde.

Esto me ha llevado a considerar la siguiente pregunta.

Deje $N(\epsilon)$ denotar el valor de $n$ que minimiza $\pi(1/2 + \epsilon, n)$. ¿Qué se puede decir acerca de la $N(\epsilon)$ as $\epsilon\to0$?

Presumiblemente, $\lim_{\epsilon\to0} N(\epsilon) = \infty$, pero aproximadamente el cómo de rápido?

Answer 1

Puedo mostrar que $N(\epsilon)$ es igual a $\epsilon^{-2}$ hasta un registro de factor en cada lado.

La estrategia que voy a usar es para dar una cota superior para $\pi(1/2+\epsilon,n)$. La optimización de ello, podemos obtener una cota superior para $\pi(1/2+\epsilon,N(\epsilon))$. A continuación, utilizando los límites inferiores para $\pi(1/2+\epsilon,n)$ podemos descartar ciertos valores de $n$ como $N(\epsilon)$.

Para cualquier $m \geq\epsilon n$, tenemos que el límite superior $$ \pi(1/2+\epsilon,n) \leq \frac{(1+2\epsilon)^{n/2+m} (1-2\epsilon)^{n/2-m} }{n} + e^{ - 2 (m-\epsilon n)^2/n}$$

De hecho, por Hoeffding la desigualdad, el segundo término es una cota superior de la probabilidad de conseguir mayor que $m$ gana, por lo que es suficiente para demostrar el primer término es una cota superior de la probabilidad de ganar el torneo con en la mayoría de las $m$ gana. Sin embargo, para cada resultado posible del torneo (especificando el ganador de cada partido) de la participación en la mayoría de las $m$ gana un jugador determinado, la probabilidad de conseguir cuando ese jugador es el favorito dividido por la probabilidad de conseguir si ese jugador es el mismo que todos los demás, es en la mayoría de las $(1+2 \epsilon)^m (1-2\epsilon)^{n-m}$ (multiplique la probabilidad). Por lo tanto la probabilidad de ganar el torneo con en la mayoría de las $m$ gana como el favorito es en la mayoría de las $(1+2 \epsilon)^m (1-2\epsilon)^{n-m}$ veces la probabilidad de ganar el torneo como un reproductor de media y en la mayoría de las $m$ gana, que es en la mayoría de la probabilidad de ganar el torneo como un jugador promedio, que es de $< 1/n$.

Podemos estimar $$ (1+2\epsilon)^{n/2+m} (1-2\epsilon)^{n/2-m} = e^{ 4 \epsilon m - \frac{(2\epsilon)^2}{2} n + O( \epsilon^3 n ) }$$

Por lo que el establecimiento $m = \epsilon n + \sqrt{n \log n /2}$, el segundo término es $1/n$ y el primer término es $$\frac{ e^{2 \epsilon^2 n + 2 \epsilon \sqrt{2 n \log n}} }{n}$$ so choosing $n$ to be approximately $\epsilon^{-2}/ \log (\epsilon^{-1})$, the exponent is $O(1)$, so $\pi(1/2+\epsilon,n)=O(1/n) = O( \log (\epsilon^{-1})/ \epsilon^{-2})$.

Por lo tanto $\pi(1/2+\epsilon,N(\epsilon)) = O( \log (\epsilon^{-1})/ \epsilon^{-2})$.

Ahora, utilizando el límite inferior $\pi(1/2+\epsilon, n) \geq 1/n$, obtenemos $N(\epsilon) \geq C \epsilon^{-2} / \log (\epsilon^{-1})$ para algunas constantes $C$.

A límite superior $N(\epsilon)$, podemos usar diferentes límite inferior. Por Hoeffding la desigualdad, la probabilidad de que algún jugador puntuaciones por encima de $(1/2 + \epsilon/2 n)$ o el favorito de los puntajes por debajo de $(1/2 + \epsilon/2 n)$ es en la mayoría de las $e^{ - \epsilon^2 n /2}$, lo $\pi(1/2+\epsilon,n) \geq 1 -n e^{-\epsilon^2 n/2}$. En particular, debido a que $\pi(1/2+\epsilon,N(\epsilon))=o(1)$ entonces $ \epsilon^2 N(\epsilon)/2 \geq \log N(\epsilon) - o(1)$, lo $N(\epsilon)/\log N(\epsilon) \geq 2 \epsilon^{-2} (1-o(1))$ y, por tanto,$N(\epsilon) \geq 4 \epsilon^{-2} \log (\epsilon^{-1}) (1+o(1))$.

Answer 2

(Esta no es una solución. He puesto como una respuesta porque no tengo un privilegio para dejar un comentario) Otro enfoque es comenzar con un elemental método que Muestra la dureza del problema.

Voy a aliviar la condición a condición de que ningún jugador gana más juegos de el mejor jugador.

En ese entorno el nativo de primaria enfoque es mucho más sencillo: Vamos a $ k = {n+1 \choose 2} $ e $ m $ el número de el mejor jugador de la gana, indicar también el número de soluciones para $ \sum_{i=1}^n x_i = l $ por $ s(n,l) $ (trivial), y el número de soluciones para $ \sum_{i=1}^n x_i = l $ s.t. $ \forall i (x_i \leq b) $ por $ sb(n,l,b) $ (simple cálculo mediante la Inclusión–exclusión en el principio).

Lo que obtenemos que: $$ \pi_2(p_\epsilon, n+1) = \sum_{m=0}^n \frac{sb(n,k-m,m)}{s(n,k-m)} (1/2)^{k-m} p_\epsilon^m (1-p_\epsilon)^{n-m}$$ Lo cual es difícil de analizar, de manera asintótica en los métodos como en la de Arthur respuesta son mejores.

Answer 3

Una Introducción:

Tenemos uno de los favoritos y $m\in\mathbb N:=\{1\ 2\ \ldots\}$ patzers como yo, por un total de $n:=m+1$ intrépidos jugadores de ajedrez (que son como los equipos de baloncesto--no se basa están permitidos). Una probabilidad de ganar en un juego entre patzers es $\frac 12, $ e $\ p:=\frac 12+\epsilon\ $ para el favorito, y $\ \frac 12-\epsilon\ $ contra el favorito, donde $\ 0<\epsilon<\frac 12$.

Vamos a concentrarnos en la subtorneo de patzers sólo. El valor esperado de cada uno de ellos es, a continuación,$\ \frac {m-1}2.\ $ de La varianza de una $1$-evento del juego entre ellos es

$$\frac 12\cdot\left(\frac 12\right)^2 + \frac 12\cdot\left(\frac 12\right)^2\ =\ \frac 14 $$

Por lo tanto la varianza de toda la subtournament para un jugador es $\ \frac {m-1}4\ $ por lo tanto la respectiva desviación estándar es $\ \frac {\sqrt{m-1}}2.\ $ Por lo tanto, la probabilidad de que un patzer puntuación de, al menos, $\ M\ :=\ \frac{m-1}2 + \frac{\sqrt{m-1}}2\ $ puntos es, al menos, $15\% = 0.15\ $ -- un jugador como este puntaje $M$ puntos en $15$ los torneos de una $100$, en promedio.

Por otro lado, el favorito de las puntuaciones en la mayoría de los $\ F\ :=\ m\cdot p\ $ en al menos la mitad de las ocasiones (es decir, los torneos). Los juegos del favorito son independientes de los juegos entre el menor de los competidores. Por lo tanto la probabilidad de que un patzer conseguir la puntuación $\ \ge M,\ $ y de los favoritos de obtener no más de $\ F,\ $ al menos $\ 7.5\%.$

Sin embargo, $\ F\le M\ $ siempre

$ p $ \ \le\ \frac{m-1+\sqrt{m-1}}{2\cdot m} \,\ =\,\ \frac 12 + \frac{\sqrt{m-1}-1}{2\cdot m} $$

Entonces la probabilidad de que el favorito de ganar un torneo no es más que $\ 92.5\%:\ $

$$ \pi\ \left(\frac 12 + \frac{\sqrt{n-2}-1}{2\cdot (n-1)},\ n\right)\,\ \le\,\ 0.925 $$

Esto puede servir como una primera, muy cruda visión del problema.