Ideas matemáticas
-
Linealidad de la expectativa para cualquier coeficiente $a$ y $b$ y cualquier variable aleatoria $X$ y $Y$ tenemos $\mathbb{E}[aX+bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]$ . Esto nos permite mirar cada bit por separado, en lugar de los números en su conjunto, lo que reduce enormemente la complejidad.
-
(?) Cadenas de Markov : Las cadenas de Markov utilizadas en este problema son tan sencillas que no se requiere ningún conocimiento formal sobre ellas (y de hecho no utilizo la terminología de las cadenas de Markov en la explicación que sigue, salvo en una nota al margen). Sin embargo, son muy útiles en problemas similares más complejos. A Cadena de Markov es una colección de estados junto con las probabilidades de transición de un estado a otro.
Solución
Se puede empezar considerando sólo un bit, por ejemplo el bit $k$ . Dejemos que $X_k$ sea el $k^{\text{th}}$ un poco de $x$ . Sea $Y$ sea la salida, y $Y_k$ es su $k^{\text{th}}$ poco. Definir $K_k$ de manera similar. Aquí, indizo el bit más bajo ( $0^{\text{th}}$ potencia de 2) por 0, y el más alto por $l$ . Si $X$ y $K$ no tienen la misma longitud, podemos añadir 0s delante.
Calculemos $\mathbb{P}[Y_k=1]$ para cada $k$ . Obsérvese que esto nos da el valor esperado para este bit: $$\mathbb{E}[Y_k] = 1\mathbb{P}[Y_k=1] + 0\mathbb{P}[Y_k=0]$$
Necesitaremos las probabilidades de lo que sacaremos si se pasa 1 o 0 al RGN en $k^{\text{th}}$ posición. Para ello, definimos una matriz T de 2 por 2:
Dejemos que $T_{i,j}$ sea la probabilidad de que, si obtenemos el bit de entrada i en el $k^{\text{th}}$ posición en nuestro RNG, y $K_k=j$ , obtendremos 1 en la salida.
Esto puede ser precalculado para todos los $i$ , $j$ . Por ejemplo, $T_{0,1} = \frac{A + C}{100}$ , ya que tanto XOR como OR con producen 1 dadas las entradas 0 y 1.
Dejemos que $P_{k, n}$ sea la probabilidad de que el $k^{\text{th}}$ es 1 después de haber pasado por $n$ RNGs. Claramente, $P_{k, 0} = X_k$ (esto es 0 o 1, dependiendo de nuestro bit inicial).
Cada siguiente RNG cambia esa probabilidad de la siguiente manera:
$$P_{k, d + 1} = P_{k, d}T_{1,K_k} + (1 - P_{k, d})T_{0, K_k}$$
( $1 - P_{k, d}$ es la probabilidad de tener un $0$ )
Esto puede calcularse mediante programación dinámica.
Obsérvese que la distribución del bit de salida depende únicamente del bit de entrada y del bit correspondiente de $K$ así que sólo hay cuatro posibilidades para ello. Es decir, no es necesario repetir todo el cálculo para cada bit, sino que podemos hacerlo una vez para cada una de las cuatro posibilidades.
Nota al margen : Aquí tenemos las cadenas de Markov. Tenemos dos estados, 0 y 1. Comenzamos en el estado dado por $X_k$ . Tenemos dos posibles matrices de transición (no son T, pero pueden ser calculadas a partir de ella), y la que utilicemos depende de $K_k$ . Nos interesa la probabilidad de estar en el estado 1 después de $N$ transiciones.
Llamemos a la salida Y. Sabemos la probabilidad de que $Y_k=1$ , a saber $P_{k, n}$ . La expectativa de una variable binaria es la probabilidad de obtener 1, por lo que $\mathbb{E}[Y_k] = P_{k,n}$ .
Por último, podemos utilizar la linealidad de la expectativa para calcular la expectativa de Y:
$$ \mathbb{E}[Y] = \mathbb{E}[Y_0 + 2Y_1 + 2^2Y_2 + \dots + 2^lY_l] = \\ = \mathbb{E}[Y_0] + 2\mathbb{E}[Y_1] + \dots + 2^l \mathbb{E}[Y_l] = \\ = P_{0,n} + 2P_{1,n} + 2^2P_{2,n} + \dots + 2^lP_{l,n} $$
2 votos
Es prematuro tratar de encontrar la expectativa de inmediato antes de comprender la estructura del problema. Considera: al principio tienes un valor posible, $X$ . Después de pasar por una máquina, tienes tres valores posibles: $X\wedge K$ , $X\vee K$ , $X\oplus K$ . Después de dos máquinas, tienes nueve valores posibles... ¿o no? ¿Algunos de ellos resultan ser iguales entre sí, o a valores que has visto antes? Intenta dibujar las posibilidades como si fuera el gráfico de transición de una máquina de estado.
0 votos
@Rahul ¡Gracias! Tu idea era correcta :)