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

8

Digamos que tengo una variable aleatoria de un bit , y que sea ​​un número natural. Quiero una secuencia de variables aleatorias stX{0,1}n0=X0,X1,,Xn=X

H(X | {X0,,Xk})=1kn

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

Geoffrey Irving
fuente

Respuestas:

2

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))

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)=0f()=1f(t)k0tXk=Y(t)tk

Geoffrey Irving
fuente
3
¿No podría simplemente tomar donde es XOR e es Bernoulli independiente con media ? Xk=XYkYkpk
Sasho Nikolov
Sí, ese es un método ciertamente más simple. :)
Geoffrey Irving
0

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 .XnnnS=Y0,Y1,...N(0)N(1)SX=1N(1)>N(0)X=0N(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
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
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
1
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
Geoffrey Irving