Primer jugador en ganar k coincide con

Question

Una serie de partidos se llevan a cabo entre n idénticos a los competidores. Cada uno es ganado por uno de los n con igual probabilidad (sin ataduras). Estoy buscando una descripción probabilística de los resultados cuando se mira en el primer jugador en ganar 1, 2, ... partidos.

Por ejemplo, si el jugador #3 es el primer jugador en ganar 400 partidos, ella tiene una mejor que 1/n la oportunidad de ser el primer jugador para ganar 401 partidos.

En particular: ¿cuántos partidos se deben jugar antes de que algún jugador gana k? (La dominante término es, por supuesto, kn , pero ¿cuál es el siguiente (negativo) plazo?) ¿Con qué frecuencia el plomo cambiar de lugar? (Espero infinitamente a menudo, pero con la disminución de la frecuencia... tal vez sqrt-ly muchas veces?)

Tengo una decente matemáticas fondo, pero no se ha estudiado ninguna probabilidad desde un básico de pregrado de la clase.

Relacionadas con la pregunta: ¿cuánto tiempo hasta que todo el mundo está en el plomo?

Answer 1

Esto no es sencillo.

Para $n=2$ puede basarse en la probabilidad o el número de maneras de llegar a el paso anterior de tener uno de los actores que han ganado $k-1$ juegos y de nadie más después de haber ganado más, dando a la expresión $$2 \sum_{j=k}^{2k-1} \left. j {j-1 \choose k-1} \middle/ 2^j \right.$$ $$= 2k \left(1 - {2k \choose k} \middle/ 4^k \right).$$

Para $n \gt 2$ puede desarrollar un enfoque similar basado en

$$n \sum_{j=k}^{nk-n+1} \left. j {j-1 \choose k-1} f(j-k,n-1,k-1) \middle/ n^j \right.$$

donde $f(a,b,c)$ es el número de maneras de poner $a$ etiquetado de las pelotas en $b$ etiquetado de cajas de sujetos para cada casilla de no tener más de $c$ bolas.

Agregó

Es posible que desee buscar en: Klamkin, M. S. y Newman, D. J. "Extensiones de la Sorpresa de Cumpleaños." J. Combinat. Th. 3, 279-282, 1967.

No lo he leído, pero al parecer se le da a expresiones como $$\int_0^\infty \left(e_{k-1}\left(\frac{t}{n}\right)\right)^n \, e^{-t} \, dt$$ where $e_{k-1}(x) = 1+\frac{x^1}{1!}+\cdots + \frac{x^{k-1}}{(k-1)!}$ is a truncated exponential, and asymptotic values like $$\left(k!\right)^{1/k} \,\Gamma\left(1+\frac{1}{k}\right) \, n^{1-1/k} $$ for fixed $k$ as $n$ increases. For $n=365$ and and $k=2$, the first of these gives about $24.616585894$, which is correct (we are looking for the mean not the median of the birthday problem) and the second gives about $23.9$.