Una pregunta sobre el Poker (y probabilidad en general)

Question

Bueno, pues he estado pensando en esto por un largo tiempo, y estoy empezando a pensar que no hay una respuesta. Así que por favor lea la pregunta, y si hay una respuesta, diga cómo se llegó a ella, y si no la hay, dime por qué.

Hay un cierto número de manos que pueden ser tratados de una baraja de 52 cartas. Jugar cinco cartas de poker, hay 52*51*50*49*48 las manos posibles, si no me equivoco. La pregunta es, ¿cuántas manos se tenga que tratar con el fin de tener reparten cada mano al menos una vez? Suponga que se reparten cinco cartas, entonces esas cartas se barajan en la cubierta y otra al azar cinco cartas sean repartidas. Cuántas veces le tienen que lidiar, en promedio, antes de tener reparten cada hamd?

Answer 1

En primer lugar usted necesita para calcular el número correcto de las distintas manos. Digamos que los trajes son siempre relevantes. En ese caso el número de distinto poker de cinco cartas de las manos es el número de maneras de elegir 5 tarjetas de 52, que es

$$\binom{52}{5} = \frac{52!}{5!47!} = \frac{52\cdot 51\cdot 50\cdot 49\cdot 48}{5\cdot4\cdot3\cdot2\cdot1} = 2598960$$

(véase aquí para una explicación)

Ahora podemos preguntar cuánto tiempo se tarda, en promedio, antes de haber visto cada mano. Deje $T_{k,n}$ ser el número esperado de las manos hasta que he visto todo lo $n$ posible de las manos, cuando ya se ha visto $k$ de las manos. Entonces sabemos que el $T_{n,n}=0$ (ya has visto todas las manos) y queremos encontrar a $T_{0,n}$, se espera que el número de manos que puede recibir cuando todavía no hemos visto ninguna de las manos repartidas. La actualización de la regla de la siguiente manera de considerar las probabilidades de ser tratado de una nueva mano, o una mano que ya hemos visto:

$$T_{k,n} = \frac{n-k}{n} (1 + T_{k+1,n}) + \frac{k}{n} (1 + T_{k,n})$$

que se simplifica a

$$T_{k,n} = \frac{n}{n-k} + T_{k+1,n}$$

que podemos resolver, dando la solución

$$T_{0,n} = n\sum_{i=1}^n \frac{1}{i} = n H_n$$

donde $H_n$ $n$ésimo número Armónico.

Para el problema que se quiere tener en cuenta que han $n=2598960$. El $2598960$ésimo número Armónico es de aproximadamente $15.34784$, lo que significa que usted esperar esperar

$$15.34784 \times 2598960 = 39888416$$

o aproximadamente 40 millones de ofertas antes de haber visto cada posible de cinco cartas de póquer. Para poner esto en perspectiva, un repartidor de trabajo en la velocidad fenomenal, una mano por segundo, y nunca dejar de comer o dormir, tomaría aproximadamente 1 año y 3 meses para hacer frente a cada mano de poker posible.

Answer 2

Otra manera de obtener el promedio de tiempo de espera, que está estrechamente relacionada con la de Chris, método y, por supuesto, conduce al mismo resultado, pero podría ser un poco más accesible si no se había encontrado relaciones de recurrencia antes, es esto: en Primer lugar, usted tiene que esperar hasta que he visto al menos una mano; a continuación, usted tiene que esperar hasta que he visto al menos dos manos; entonces usted tiene que esperar hasta que he visto al menos tres manos, etc. El total de tiempo de espera promedio es la suma de cada uno de estos tiempos de espera. Ahora, cuando ya has visto las $j$ manos, la probabilidad de obtener una mano en la que no ha visto todavía, y así avanzar a la siguiente etapa de espera de la etapa, se $n-j$ $n$ donde $n$ es el número de todas las manos posibles. Es posible que si usted tiene un $1$ $m$ oportunidad de ver algo que, en promedio, usted tendrá que esperar $m$ veces a verla, y de hecho, esto resulta ser cierto (véase la distribución geométrica). Así que el tiempo medio de espera para ver algo es el recíproco de la oportunidad de verla, así que si la posibilidad de ver una nueva mano es $(n-j)/n$, en promedio, usted tendrá que esperar $n/(n-j)$ veces a verla. Ahora sólo tienes que añadir todos estos promedio de los tiempos de espera:

$$t=\sum_{j=0}^{n-1}\frac n{n-j}=n\sum_{j=0}^{n-1}\frac1{n-j}=n\sum_{i=1}^{n}\frac1{i}$$

(con $i=n-j$), que es exactamente Chris resultado.

Answer 3

Aquí hay otra solución, que obviamente no es tan elegante como y mucho más complicado que el de las otras respuestas, pero tal vez sirva como un buen ejemplo de que a) en matemáticas a menudo se puede hacer las cosas de maneras muy diferentes y, a veces, algo milagrosamente) terminan con el mismo resultado y b) que de estas maneras diferentes que usted puede elegir hacer una gran diferencia en la cantidad de trabajo que tienes que hacer para obtener el resultado.

Podemos modelo de negociación como un proceso de Markov. El estado está dada por el número de $i$ de las manos no la ha visto. Con cada oferta, en el estado de $i$ el estado se queda sin cambios con una probabilidad de $i/n$ y una transición de estado $i$ estado $i-1$ se produce con una probabilidad de $1-i/n$, donde de nuevo $n$ es el número de manos posibles. Así, por ejemplo, para $n=5$ tendríamos la siguiente matriz de transición:

$$\left(\begin{array}{ccccc} 1&\frac15&0&0&0&0\\ 0&\frac45&\frac25&0&0&0\\ 0&0&\frac35&\frac35&0&0\\ 0&0&0&\frac25&\frac45&0\\ 0&0&0&0&\frac15&1\\ 0&0&0&0&0&0\\ \end{array}\right)\;.$$

Si tenemos el número de filas y columnas empezando $0$, esta matriz de autovectores $x_k=(-1)^i\binom ki$ $k=0,\dotsc,n$ y los correspondientes autovalores $\lambda_k=1-k/n$ (donde el coeficiente binomial es cero si la parte inferior argumento es mayor que el de arriba). Nuestro estado inicial ha probabilidad de $1$ estado $n$ $0$ en todos los demás estados, y esto tiene el expansión

$$\delta_{in}=\sum_{k=0}^n(-1)^k\binom nkx_k=\sum_{k=0}^n(-1)^{k+i}\binom nk\binom ki$$

en términos de los vectores propios de la matriz de transición. El estado final ha $i=0$, por lo que la probabilidad de haber visto todas las manos a la hora de $t$ es la componente correspondiente del vector de estado en el tiempo $t$. Cada autovector es multiplicado por su valor propio en cada parte, por lo que la probabilidad de estar en el estado $i=0$ tiempo $t$ está dado por

$$p_t=\sum_{k=0}^n(-1)^k\binom nk\lambda_k^t=p_t=\sum_{k=0}^n(-1)^k\binom nk\left(1-\frac kn\right)^t\;.$$

La probabilidad de que no se ha hecho todavía en el tiempo de $t$ es

$$1-p_t=-\sum_{k=1}^n(-1)^k\binom nk\left(1-\frac kn\right)^t\;,$$

y el tiempo de espera promedio es la suma de todas estas probabilidades:

$$ \begin{eqnarray} T &=& \sum_{t=0}^\infty(1-p_t) \\ &=& \sum_{t=0}^\infty\left(-\sum_{k=1}^n(-1)^k\binom nk\left(1-\frac kn\right)^t\right) \\ &=& -\sum_{k=1}^n(-1)^k\binom nk\sum_{t=0}^\infty\left(1-\frac kn\right)^t \\ &=& -\sum_{k=1}^n(-1)^k\binom nk\frac nk\;. \end{eqnarray} $$

Para evaluar esto, considere la posibilidad de

$$\sigma(q)=\sum_{k=1}^n(q-1)^k\binom nk\frac1k\;.$$

Diferenciando con respecto a $q$ rendimientos

$$\begin{eqnarray} \sigma'(q) &=& \sum_{k=1}^n(q-1)^{k-1}\binom nk \\ &=& \frac1{q-1}\left(\sum_{k=0}^n(q-1)^k\binom nk-1\right) \\ &=& \frac{(q-1+1)^n-1}{q-1} \\ &=& \frac{q^n-1}{q-1} \\ &=& \sum_{i=0}^{n-1}q^i \;, \end{eqnarray} $$

y así

$$\sigma(q)=\sum_{i=1}^{n}\frac{q^i}i+C\;.$$

La integración constante de $C$ puede ser recuperado de $\sigma(1)=0$:

$$\sigma(q)=\sum_{i=1}^{n}\frac{q^i}i-\sum_{i=1}^{n}\frac1i\;,$$

y así obtenemos

$$T=-n\sigma(0)=n\sum_{i=1}^{n}\frac1i\;,$$

de acuerdo con las otras respuestas.