Fallo en la lógica de resolución del valor esperado (Proyecto Euler 323)

Question

El planteamiento del problema para Proyecto Euler #323 es la siguiente:

Sea $y_0, y_1, y_2, ...$ sea una secuencia de enteros aleatorios sin signo de 32 bits (es decir. $0 \leq y_i < 2^{32}$ (todos los valores son igualmente probables).

Para la secuencia $x_i$ se da la siguiente recursión:

• $x_0 = 0$ y

• $x_i = x_{i-1} | y_{i-1}$ para $i > 0$ . ( | es el operador bitwise-OR)

Se puede ver que eventualmente habrá un índice N tal que $x_i = 2^{32} -1$ (un patrón de bits de todos los unos) para todos los $i \geq N$ .

Halla el valor esperado de N. Da tu respuesta redondeada a 10 dígitos después del punto decimal.

No estoy interesado en la solución real del problema, pero deseo entender dónde han ido mal mis intentos. Mi intento al problema hasta ahora ha sido como sigue:

• Para cualquier $y_i$ la probabilidad de que cualquier bit sea un 1 es $\frac{1}{2}$ ya que todos los valores tienen la misma probabilidad. En otras palabras, la probabilidad de que un bit "cambie" de 0 a 1 en el siguiente turno es $\frac{1}{2}$ .

• Por lo tanto, el número esperado de 1s en $x_1$ est $32 \div 2 = 16$

• Siguiendo esta lógica, el número esperado de 1s en $x_2$ es 24, ya que la mitad de los dieciséis ceros se voltearían.

• Entonces el número esperado de 1s en $x_3$ es 28, para $x_4$ son 30 y por $x_5$ Son 31.

• El valor esperado para el último bit es equivalente a lanzar una moneda al aire hasta que salga cara (1), que sería $\sum_{1}^{\infty} \frac{n}{2^n} = 2$ .

• Por lo tanto, el valor esperado de N es 5 + 2 = 7.

Sin embargo, aparte de que la respuesta es completamente errónea, algo me hace pensar que los valores esperados no funcionan así. ¿Puede alguien aclararme en qué me he equivocado?

Descargo de responsabilidad: Aunque intento abstenerme de publicar preguntas relacionadas con el Proyecto Euler en Math StackExchange, creo que la respuesta a mi problema no facilitaría a nadie más la resolución del problema, y de hecho podría ayudar a otros a entender en qué se equivocaron.

Answer 1

El problema más obvio que veo es que has pasado de "el valor esperado para el número de monedas sin lanzar en la fase 5 es 1" a "el número esperado de lanzamientos necesarios hasta que haya una sola moneda sin lanzar es 5". Luego calculas el valor esperado del número de lanzamientos para terminar, condicionado a que el principio sea correcto (asumiendo implícitamente que siempre terminarás con una sola moneda sin lanzar en algún momento).

Una forma de resolver realmente el problema es considerar su proceso como 32 independientes Procesos Bernouli y observando que (como cuando sólo quedaba una moneda) el primer tiempo de éxito tiene un distribución geométrica . El momento en que el último proceso tiene éxito es el mayor estadística de pedidos de los 32 procesos. Aunque en la página aparece una fórmula para las estadísticas de orden, merece la pena intentar deducir la fórmula, al menos para la estadística de orden más grande. Esto es bastante sencillo utilizando la función FCD de las variables para determinar la FDA de los estadísticos de orden. Si bien es posible pasar de la FCD a la correspondiente PDF (aunque la wikipedia dice que la distribución se llama función de masa de probabilidad cuando la variable es discreta), se puede pasar directamente de la función acumulativa directamente a la valor esperado sin pasar por el pdf, al menos para variables discretas.

Answer 2

Cada vez que O $y_i$ en $x_{i-1}$ , estás OR-ing a $1$ en el $k$ -ésima posición con probabilidad $\frac{1}{2}$ y lo que usted está OR-ing en el $32$ posiciones de bits es $32$ bits elegidos independientemente. Si $X_k$ indica el valor de $i$ en el que el $k$ -ésimo bit pasa de $0$ a $1$ entonces $X_k$ es una variable aleatoria geométrica con parámetro $\frac{1}{2}$ . Así, $$P\{X_k \leq m\} = 1 - P\{X_k > m\} = 1 - \frac{1}{2^m}.$$ Además, el $X_k$ son variables aleatorias independientes.

La hora $N$ a la que llegas al estado todo-uno es, por tanto, el máximo de $32$ independiente variables aleatorias geométricas con parámetro $\frac{1}{2}$ . Ahora, $$P\{N > m\} = P\{\text{at least one}~X_k > m\} = 1 - P\{\text{all}~ X_k \leq m\} = 1 - \left(1 - \frac{1}{2^m}\right)^{32}$$ y $$\begin{align*}E[N] &= \sum_{m=0}^{\infty} P\{N > m\} = \sum_{m=0}^{\infty} 1 - \left(1 - \frac{1}{2^m}\right)^{32} \\ &= 1 + \left[1 - \left(\frac{1}{2}\right)^{32}\right] + \left[1 - \left(\frac{3}{4}\right)^{32}\right] + \left[1 - \left(\frac{7}{8}\right)^{32}\right] + \cdots \end{align*}$$ que debería estar cerca de $7$ .

Answer 3

Una cosa que está fallando es que, a nivel informal, el "valor esperado $k$ " se identifica con "valor $k$ ." Así por ejemplo en el casi final, cuando se piensa que el número esperado de $0$ restante es $1$ es muy posible que quede algo más que $1$ y también es muy posible que no quede ninguno. No hay razón para pensar que las expectativas producidas por estos dos casos se cancelen.

Tampoco está claro qué significan las expectativas. Cuando se dice que el número esperado de $0$ después de $k$ operaciones bit a bit es $e$ ¿está condicionando el evento a que el proceso no haya terminado a tiempo $\le k-1$ ?

Para ver lo que ocurre, haremos un par de cálculos, con números mucho más pequeños que $32$ . Imaginemos, por ejemplo, que el número $b$ de bits es $2$ .

Entonces, después de una operación, con probabilidad $1/4$ seguiremos en $(1,1)$ con probabilidad $1/2$ estaremos en $(0,1)$ o $(1,0)$ y con probabilidad $1/4$ estaremos en $(0,0)$ . Sea $e$ sea el número previsto de operaciones utilizadas.

Así, con probabilidad $1/4$ hemos desperdiciado un lanzamiento, y el número esperado de lanzamientos necesarios es $1+e$ . Con probabilidad $1/2$ hemos utilizado $1$ y el número esperado de lanzamientos adicionales es $2$ . Y con probabilidad $1/4$ no necesitamos un segundo lanzamiento, por lo que la expectativa es $1$ . De ello se deduce que $$e=\frac{1}{4}(1+e)+\frac{1}{2}(1+2)+ \frac{1}{4}(1).$$ Resolver para $e$ . Obtenemos $e=8/3$ .

Un cálculo basado en mi comprensión de su método diría que la expectativa es $1+2$ .

Answer 4

Intuitivamente, creo que tu razonamiento tiene sentido si hablas de la media número de intentos que debe hacer para alcanzar $2^{32}-1$ . Por lo tanto, si se repite el experimento un gran número de veces, en promedio, 7 deberían ser suficientes.

Sin embargo, la definición (según Wikipedia) del valor esperado de una variable aleatoria es la media ponderada de todos los valores posibles que puede tomar dicha variable aleatoria. En otras palabras, lo que habría que calcular es la media de {la probabilidad de que se necesite 1, 2 veces la probabilidad de que se necesiten dos números, 3 veces la probabilidad de que se necesiten tres números, etc.}. Al cabo de un tiempo, la probabilidad de que se necesiten N números será tan baja que no impactará el décimo dígito después del punto decimal.

Pero debo decir que, intuitivamente, no me extrañaría que el valor estuviera en torno a 7, siguiendo tu razonamiento.