Determinar el número esperado de rondas

Question

Estoy tratando de determinar una fórmula para el número esperado de rondas de un juego de azar basado en dados.

Los detalles del juego son como sigue:

1. El juego inicialmente consta de $N$ jugadores

2. Cada jugador tiene un buen morir o acceso a uno.

3. Para cada ronda, cada jugador va a rodar sus morir de una vez

4. La media de los rollos se determina

5. Cualquier jugador que rodó un valor menor que la media es eliminado del juego

6. Las rondas se repiten hasta que su es sólo jugador a la izquierda.

Mi pregunta es ¿cómo se determina el número esperado de todo el año en términos de $N$.

Mi pensamiento es que para cualquier ronda, la expectativa es que la mitad de los jugadores serán eliminados. Esto conduce a una continua reducción a la mitad del número de jugadores, lo que parece sugerir que $\text{E}(\text{Rounds}) \approx \log_2 {N}$ o más concretamente:

$$ \lim_{N \to \infty} \text{E}(\text{Rounds}) =\log_2 {N} $$

Yo no era capaz de formular una relación definitiva, así que me encontré con un simple monte-carlo del juego, para los números de los jugadores que van de los 2 a los jugadores de 200 jugadores, un millón de simulaciones por el tamaño del juego. Los resultados se pueden encontrar aquí:

https://gist.github.com/anonymous/f0db85f06343070045b78f7494f19565

El gráfico de los resultados y de $\log_2 {N}$ se muestra en el siguiente como el rojo y azul, respectivamente:

Donde estoy teniendo dificultad es la explicación de la continua y constante sobre-estimación del resultado de la curva (a través de la simulación) en comparación con el $\log_2{N}$ curva.

Answer 1

Sea e(n) es el número esperado de rondas, comenzando con n jugadores.

Para un determinado número entero positivo n, el valor exacto de e(n) puede ser encontrado a través de un procedimiento recursivo.

He implementado un procedimiento de este tipo en madera de Arce, y los resultados, para $2 \le n \le 8$, se muestra a continuación (las fracciones son los valores exactos).

\begin{align*} e(2) &= \dfrac {6} {5} \approx 1.200000000\\ e(3) &= \dfrac {303} {175} \approx 1.731428571\\ e(4) &= \dfrac {81486} {37625} \approx 2.165740864\\ e(5) &= \dfrac {654386} {263375} \approx 2.484616991\\ e(6) &= \dfrac {1123369554} {409548125} \approx 2.742948839\\ e(7) &= \dfrac {1155681595606} {389948321875} \approx 2.963678854\\ e(8) &= \dfrac {49218033279086166} {15594311926296875} \approx 3.156152930 \end{align*}

Aquí está mi Arce implementación de e(n) ...

Answer 2

Me he encontrado un programa de C++ muy cerca en el algoritmo para el Maple programa por @cuasi. Que es, se basa en el

$$ e(n) = \frac{1+\sum_{0 < k < n}p_{k,n}\cdot e(k)}{1-p_{n,n}}\enspace,$$

where $p_{k,n}$ is the probability of there being $k$ survivors out of $$ n de los jugadores.

He aquí un fragmento de código, que muestra cómo se trabaja con el C++ enlaces de la GMP bignum de la biblioteca.

static void print_expected_survivors(std::vector<mpz_class> const & counts,
                                     long i, mpz_class outcomes)
{
  mpq_class exp_surv = 0;
  for (long j = 0; j != i; ++j) {
    exp_surv += counts[j] * (j+1);
  }
  exp_surv /= outcomes;
  mpf_class ef = exp_surv;
  std::cout << "s(" << i << ") = " << ef << std::endl;
}

En el GMP de la biblioteca, mpz, mpqy mpf soporte para múltiples precisión entero, racional, y número de punto flotante, respectivamente. Esta función poco manipula los datos de los tres tipos, así como de tipo long.

Aquí está una parcela de $e(n) - \log_2(n)$:

No es obvio a partir de los datos si hay una asíntota horizontal diferente de $y=0$.