Valor esperado de la función aplicada a un número binario construido aleatoriamente

Question

Hace poco se me planteó esta cuestión al jugar con números binarios y traté de codificar una solución para ello:

Dejemos que $b$ sea una cadena de 1s y 0s. Dividir la cadena en partes separadas de tal manera que la cadena se divide sólo cuando un 0 está junto a un 1 (o viceversa, por supuesto). Por ejemplo, 11100110 se divide en 111, 00, 11 y 0. Calcula el número de dígitos de cada parte (en nuestro ejemplo serían 3, 2, 2 y 1, respectivamente), y toma la suma de cuadrados del número de dígitos de cada parte (en nuestro ejemplo sería $3^2+2^2+2^2+1^2=18$ ). Dejemos que los procedimientos que acabamos de describir se representen con una función $\omega$ Por ejemplo $\omega(11100110)=18$ . Además, $b$ es una cadena tal que el $k$ es 1 con probabilidad $x_k$ (y 0 en caso contrario). También dejemos que la longitud de $b$ sea $L$ . Estoy tratando de encontrar el valor esperado de $\omega(b)$ dado $L$ y el conjunto de $x_k$ para $1 \leq k \leq L$ pero no puedo encontrar un algoritmo más rápido que la fuerza bruta en este momento. ¿Cuáles son algunas optimizaciones que puedo hacer al encontrar programáticamente el valor esperado de $\omega(b)$ ? Además, me gustaría saber cuál sería la eficiencia del algoritmo (preferiblemente un límite inferior de eficiencia).

EDITAR : El algoritmo de fuerza bruta se refiere al $O(2^L \cdot L)$ uno.

Answer 1

Escriba la cadena como $b=b_1,b_2,\dots,b_L$ . Para cada $i\in \{1,\dots,L\}$ y cada $j\in \{1,\dots,L\}$ definan una variable aleatoria $A_{i,j}$ de la siguiente manera: $$ A_{i,j}=\begin{cases} 1 & b_i\text{ and $ b_j $ are in the same block}\\ 0& \text{otherwise} \end{cases} $$ Puede demostrar que $$ \omega(b)=\sum_{i=1}^L\sum_{j=1}^L A_{i,j}\tag1 $$ Piénsalo: por cada bloque de longitud $k$ hay una contribución de $k^2$ y $k^2$ es el número de pares ordenados $(i,j)$ donde $b_i,b_j$ están en ese bloque.

Por la linealidad de la expectativa, esto significa que $$ \mathbb E[\omega(b)]=\sum_{i=1}^L\sum_{j=1}^L\mathbb P(A_{i,j}=1)\tag2 $$ Además, cuando $i<j$ tenemos $$ P(A_{i,j}=1)=x_ix_{i+1}\cdots x_j+(1-x_i)(1-x_{i+1})\cdots(1-x_j)\tag3 $$ desde $b_i$ y $b_j$ están en el mismo bloque si y sólo si $b_i,b_j$ y todos los que están en medio son todos $1$ o todo $0$ . Puede calcular $(2)$ en $O(L^2)$ tiempo siempre que se tenga cuidado. El escollo es que $(2)$ es una suma de $L^2$ términos, y algunos términos son un producto de hasta $O(L)$ factores $x_i$ , que sería $O(L^3)$ ingenuamente. Por eso es importante almacenar en caché los resultados anteriores y utilizarlos en el futuro; una vez que se calcula $x_2x_3x_4$ , deberías guardarlo, y luego usarlo para calcular rápidamente $(x_2x_3x_4)x_5$ .