Cómo ganar Matt Parker jackpot - encontrar la mediana de la siguiente distribución

Question

En un reciente video de el legendario Matt Parker afirmó que se había mantenido voltear una de dos caras (feria) de la moneda hasta que él calificó como una secuencia de diez consecutivos 'voltea el interruptor de', es decir, dejando $T$ denotar una cola y $H$ a un jefe, a continuación, una secuencia de diez interruptor de flips se define a ser $THTHTHTHTH$ o $HTHTHTHTHT$. Él hizo un concurso y permite a cada espectador a adivinar una vez en la exacta cantidad de lanzamientos que necesitaba para obtener dicha secuencia. A los diez espectadores con los diez más cercano respuestas serían premiados.

El concurso está de más, así que no hay ningún incentivo para mantener una solución para el siguiente problema para ti. ¿Cuál es el mejor número para apostar? Por supuesto que esto de alguna manera depende de cómo otros espectadores respuesta: usted tiene más probabilidades de ganar si tu apuesta no está cerca de muchas otras apuestas, por lo que si un gran número de espectadores es matemáticamente inclinado y apuestas el mismo número - decir 1023 - entonces ya no es la mejor (para maximizar las ganancias) de la apuesta. He por lo tanto simplifica a la siguiente pregunta: vamos a $X$ ser el estocástico variable que representa el número de lanzamientos necesarios hasta que una secuencia de diez consecutivos interruptor de volteretas si se logra, entonces para que el número de $a \in \mathbb{N}$ hace que el valor esperado de la (valor absoluto del error $$ \mathbb{E}[\vert X - a \vert] $$ alcanzar su valor mínimo? Es bien sabido que el $a$ es la mediana de la distribución de) $X$, pero ¿cómo se puede calcular? Aproximaciones numéricas son bienvenidos, teórico (generalizable) los resultados son los preferidos.

He encontrado una manera de calcular el valor esperado de $X$ sí para general $n$ (es decir, el número total de tiradas de la moneda necesaria para obtener una secuencia de la forma $THTHTHTH...$ o $HTHTHTHT...$ de la longitud de la $n$). Deje $\mathbb{E}_i$ denotar el número esperado de la moneda para decidir necesario para obtener una secuencia deseada de la longitud de la $n$, suponiendo que ya tenemos una secuencia de longitud $i \in \mathbb{N}$. Nos encontramos $$ \mathbb{E}_0 = 1 + \mathbb{E}_1 $$ como estamos seguros de tener una secuencia de longitud $1$ después de un flip. Además, para $1 \leq i \leq n-1$ $$ \mathbb{E}_i = \frac{1}{2}\left(\mathbb{E}_1 + 1\right) + \frac{1}{2}\left(\mathbb{E}_{i+1} + 1\right) $$ ya que, dada una secuencia de $i$ volteretas que termina, por ejemplo, en una cola, tenemos un $\frac{1}{2}$ de probabilidad de aumentar esta a una secuencia de $i+1$ flips (si tenemos, por ejemplo, una cabeza) y un $\frac{1}{2}$ oportunidad de volver donde empezamos, en $1$ flip. Usando ese $\mathbb{E}_n = 0$ el de arriba nos da el sistema de $n$ ecuaciones en el $n$ variables $\mathbb{E}_0, \ldots, \mathbb{E}_{n-1}$. Uno puede comprobar fácilmente que la única solución está dada por $$ \mathbb{E}_i = 2^{n} - 2^{i} \quad 0 \leq i \leq n $$ Desde que Matt Parker comenzó a $0$ y quiso ponerse $10$ volteretas, el valor esperado del número de lanzamientos necesarios es $2^{10} - 1 = 1023$ y esto debe ser una apuesta razonable.

¿Alguien sabe cómo encontrar la distribución de $X$ (o directamente la mediana de $X$)? Como he dicho, las soluciones analíticas son de curso preferido, pero cualquier tipo de método - incluso los que requieren de cálculos numéricos, pero preferiblemente que no sea de simulaciones de Monte Carlo - sería interesante para mí.

EDIT: me enteré de que el problema se puede reducir a un problema combinatorio. De hecho, tenemos que $$ P(X \leq k) = \frac{\# \lbrace \text{secuencias de longitud $k$, el cual contiene un deseada de larga duración $n$}\rbrace}{2^k} $$ donde $2^k$ es el número total de secuencias de longitud $k$, ya que cada secuencia de longitud $k$ tiene la misma probabilidad de ocurrir. Deje $S_k$ el conjunto de secuencias de longitud $k$ $0$'s y $1$'s (podemos identificar colas con $0$, y los jefes con $1$). Tenemos un mapa $$ f: S_k \S_{k-1} $$ donde, para cualquier secuencia $s \in S_k$, $i$ésimo elemento de a $f(s)$ $1$ si $s(i) \neq s(i+1)$$0$$s(i) = s(i+1)$. Este mapa hace que el deseado secuencias en $S_k$ corresponden bijectively con las secuencias en $S_{k-1}$ que contengan $n-1$ ceros en una fila. Por lo tanto, basta con contar el número de secuencias de una determinada longitud de $k-1$ que contengan $n-1$ ceros en una fila. Cualquier idea sobre cómo continuar?

Answer 1

La probabilidad de obtener $10$ consecutivos interruptor de flips se puede modelar como una cadena de Markov, con los estados correspondientes al número de consecutivo interruptor de volteretas en el pasado inmediato. El estado en el que $10$ consecutivos interruptor de lanzamientos se han encontrado es absorbente. La distribución estacionaria con autovalor $1$ probabilidad de $1$ en este estado de absorción. Hay un cuasi-estacionaria de distribución en el que cada estado tiene la mitad de la probabilidad de uno con uno menos interruptor flip y probabilidad "fugas" en el estado de absorción a una tasa de aproximadamente el $2^{-10}$. La mediana es el menor entero $a$ que $\textsf P(X\le a)\gt\frac12$. El tiempo que tarda $\frac12$ fuga es de aproximadamente dada por $a\cdot2^{-10}=\log2$ o $a=2^{10}\log2\approx 710$.

Aquí está el código Java que sigue la evolución de la distribución del proceso hasta que la probabilidad de $10$ interruptor de volteretas supera $\frac12$. La mediana resulta ser $712$. La precisión del cálculo anterior es, en parte, a título gratuito, ya que el proceso de toma de $10$ pasos para equilibrar antes de probabilidad se inicia una fuga en el estado de absorción. Sin embargo, el acuerdo muestra que el cuasi-estacionario modelo es bastante buena, por lo $P(X\le x)\approx1-\left(1-2^{-10}\right)^t\approx1-\mathrm e^{-2^{-10}t}$ debe ser una buena aproximación.

Con respecto a la teoría de juegos aspecto del problema, esto está relacionado con el helado proveedor problema, donde el flip números se asignan a la playa usando la función de distribución acumulativa $P(X\le x)$. Sin embargo, la conclusión en el caso continuo que no hay equilibrio para $3$ jugadores no ir a través de en el caso discreto.

Answer 2

Deje $a^k_{n}$ denotar el número de cero-uno secuencias de longitud $n$ con mayor tiempo de funcionamiento de cero no exceda $k$, e $a^k_{n,m}$ denotar el número de secuencias con $m$ ceros a la derecha, $m=0,\dots,k$.

Entonces $$ a^{k}_{n,m} = a^{k}_{n-m,0},\ m = 1,\dots,k, n\ge m, $$ y $a^k_{n,0} = a^k_{n-1}$, $n\ge 0$. Por lo tanto, $$ a_n^k = \sum_{m=0}^k a^k_{n,m} = a^k_{n-1} + \sum_{m=1}^{k}^k_{n-m,0} = \sum_{j=1}^{k+1}^k_{n-j} \etiqueta{1} $$ para $n\ge k+1$. (En otras palabras, tomar una secuencia y eliminar todos los ceros finales y anterior; usted va a terminar con una secuencia cuyos más largo de funcionamiento de cero no exceda el $k$.)

Los valores iniciales se $a_n^k = 2^n, n\le k$. Por lo tanto, es fácil ver que la generación de la función $A^k(z) = \sum_{n=0}^\infty a_n^k z^n$ es igual a $$ A^k(z) = \frac{\sum_{j=0}^k z^j}{1-\sum_{j=1}^{k+1} z^j} = \frac{1-z^{k+1}}{1-2z+z^{k+2}}. $$

La escritura de la fracción parcial de expansión para $A^k(z)$, es posible obtener una fórmula explícita para $a_n^k$.

Ahora, denotando $T_m$ el número de lanza para conseguir $m$ jefes, tenemos $$ P(T_m>n) = \frac{1}{2^n}P(\text{en la mayoría de las $m-1$ consecutivos de cabeza en la primera $n$ lanza}) = \frac{a^{m-1}_n}{2^n}. $$

Sin embargo, para $m=9$ (que corresponde a $10$ alternando mueve de un tirón, como te he explicado) no hay nada muy emocionante, ya que las raíces pueden ser calculadas sólo aproximadamente. Sin embargo, el uso de la recurrente fórmula (1) proporciona una manera eficaz para calcular el número necesario de secuencias.

Una buena aproximación es $a_n^{8} \sim C_\tau \tau^{-n-1}$ donde $\tau = 0.500493118286\dots$ es el único positivo de la raíz del polinomio $f(\tau) = \sum_{j=1}^{9}z^{j} -1$ (alternativamente, la raíz de $z^{10}-2z+1$ dentro $(0,1)$), y $$ C_\tau = \frac{\sum_{j=0}^{8} \tau^j}{f'(\tau)} = 0.503980275733\dots $$ En efecto, desde el $A^8(z)$ es racional, y $f$ no tiene doble raíces, tiene una fracción parcial de expansión $A^8(z) = \sum_{\zeta: f(\zeta) = 0} \frac{C_\zeta}{\zeta - z}$. Por lo tanto, la sucesión es de la forma $a_n^8 = \sum_{\zeta: f(\zeta) = 0} C_\zeta \zeta^{-n-1}$. En particular, desde la $\tau$ es la raíz con el menor valor absoluto, $a_n^8\sim C_\tau \tau^{-n-1}$. Por otra parte, las normas de otras raíces son más grandes que las $1.11$, por lo que el error relativo de esta aproximación es de orden $r^{-n}$$r>2$. Esto es especialmente bueno para nuestro problema, ya que estamos interesados con valores muy grandes de $n$.

Así que la probabilidad de que necesitamos es aproximadamente $$ P(T_9>n)\sim \frac{C_\tau}{\tau (2\tau)^n}, $$ y esto es muy fuerte (hasta algunos exponencialmente pequeño error relativo). Con el fin de encontrar la mediana, uno debe encontrar el más pequeño de $n$ tal que $P(T_9>n)< 1/2$. Esto da el valor de $$n= \lceil- \log(4C_\tau)/\log(2\tau)\rceil-1 = 711$$ de la mediana, lo cual está de acuerdo con joriki cálculos.

Answer 3

Intuitivamente parece que deberías apostar en este evento que ocurre en los primeros 10 lanzamientos.

Razonamiento: Si se toma una particular 10 voltea a tener un $\frac{1}{2^9}$ de probabilidad de las diez lanzamientos de ser una secuencia de interés.

Sin embargo, se desea específicamente la primera secuencia de este, lo que significa que no habrá restricciones en los anteriores lanzamientos (para evitar una secuencia anterior de este tipo). Por lo tanto, su probabilidad de alguna secuencia de 10 siendo el primero de estos secuencia es menor o igual a $\frac{1}{2^9}$, con igualdad sólo durante los primeros diez lanzamientos.