Información que se filtra suavemente a lo largo del tiempo

Digamos que tengo una variable aleatoria de un bit , y que sea un número natural. Quiero una secuencia de variables aleatorias st $X \in \{0,1\}$ $n$ $0 = X_0, X_1, \ldots, X_n = X$

H (X | {X_{0}, \dots, X_{k}}) = 1 - \frac{k}{n}

$H\left(X~|~\{X_0,\ldots,X_k\}\right) = 1-\frac{k}{n}$

Es decir, cada adicional proporciona de la información de , hasta que revela todo . ¿Hay una buena construcción para esta secuencia? $X_k$ $1/n$ $X$ $X_n = X$

it.information-theory shannon-entropy Geoffrey Irving
fuente

Respuestas:

Vía Michael Kass: deje que $Y(t)$ sea un proceso Wiener que comience en $Y(0) = X$ , y defina

f (t) = H (X | Y (t))

$f(t) = H(X~|~Y(t))$

Entonces , , está aumentando estrictamente suavemente en el medio. Por lo tanto, para cualquier podemos encontrar st tiene la entropía condicional deseada ( será una función decreciente de ). $f(0) = 0$ $f(\infty)=1$ $f(t)$ $k$ $0 \le t \le \infty$ $X_k = Y(t)$ $t$ $k$

Geoffrey Irving
fuente

¿No podría simplemente tomar donde es XOR e es Bernoulli independiente con media ?

X_{k} = X \oplus Y_{k}

$X_k = X \oplus Y_k$

\oplus

$\oplus$

Y_{k}

$Y_k$

p_{k}

$p_k$

Sasho Nikolov

Sí, ese es un método ciertamente más simple. :)

Geoffrey Irving

El problema con la construcción anterior es que no hay garantía de que se revele inequívocamente después de que se transmiten bits (lo que parece ser un requisito). Aquí hay una construcción similar que funciona si es impar. Generar bits aleatorios con probabilidad de 1/2, . Deje y ser el número de 1 y 0 en . Ahora, transmita S si y o y ; transmitir de otro modo el complemento de . $X$ $n$ $n$ $n$ $S=Y_0, Y_1,...$ $N(0)$ $N(1)$ $S$ $X=1$ $N(1)>N(0)$ $X=0$ $N(1)<N(0)$ $S$

siravan
fuente

Aunque estoy confundido. En este proceso, digamos que . Si los primeros dos bits enviados son 01 o 10, entonces la probabilidad de que X sea 1 condicionado para ver estos bits es 1/2. Lo mismo es cierto si vemos 11 o 00. Entonces la entropía de la distribución condicional no es 1/3 como se requiere.

n = 3

$n=3$

Suresh Venkat

Si es 1, los primeros dos bits transmitidos no pueden ser 00. Luego, el último bit agrega 1/2 bits de información con una probabilidad de 2/3 (los primeros dos bits 01 o 10) y 0 bits de información con una probabilidad de 1/3 (11, porque no importa cuál sea el resultado es 1).

X

$X$

siravan

Corrección. Mi análisis anterior no es correcto. Creo que hay dos formas de verlo. El algoritmo es simétrico en bits y transmite un bit total de información, por lo que cada bit debe aportar 1 / n bits de información. Pero si queremos calcular las probabilidades condicionales, las cosas se complican. Creo que la situación es una variante del problema de Monty Hall ( en.wikipedia.org/wiki/Monty_Hall_problem ).

siravan

El método de paseo aleatorio Qué revela incondicionalmente X por el final, ya que el valor enviado final sería . Sin embargo, requiere el envío de números reales en lugar de bits.

Y (0) = X

$Y(0) = X$

Geoffrey Irving