Reibungslose Weitergabe von Informationen im Laufe der Zeit

8

Angenommen, ich habe eine Ein-Bit-Zufallsvariable und n sei eine natürliche Zahl. Ich möchte eine Folge von Zufallsvariablen 0 = X 0 , X 1 , , X n = X stX{0,1}n0=X0,X1,,Xn=X

H.(X. | {X.0,,X.k}})=1- -kn

Das heißt, jedes zusätzliche liefert 1 / n der Information von X , bis alles durch X n = X offenbart wird . Gibt es eine schöne Konstruktion für diese Sequenz?X.k1/.nX.X.n=X.

Geoffrey Irving
quelle

Antworten:

2

Über Michael Kass: Sei ein Wiener Prozess, der bei Y ( 0 ) = X beginnt , und definiereY.(t)Y.(0)=X.

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

Dann ist , f ( ) = 1 und f ( t ) nimmt dazwischen gleichmäßig gleichmäßig zu. Somit kann für jedes k gefunden werden, dass 0 t st X k = Y ( t ) die gewünschte bedingte Entropie hat ( t wird eine abnehmende Funktion von k sein ).f(0)=0f()=1f(t)k0tX.k=Y.(t)tk

Geoffrey Irving
quelle
3
Könnten Sie nicht einfach wobei XOR ist und Y k unabhängiges Bernoulli mit dem Mittelwert p k ist ? X.k=X.Y.kY.kpk
Sasho Nikolov
Ja, das ist eine zugegebenermaßen einfachere Methode. :)
Geoffrey Irving
0

Das Problem bei der vorherigen Konstruktion besteht darin, dass es keine Garantie dafür gibt, dass nach der Übertragung von n Bits eindeutig aufgedeckt wird (was eine Anforderung zu sein scheint). Hier ist eine ähnliche Konstruktion, die funktioniert, wenn n ungerade ist. Erzeugen Sie n zufällige Bits mit einer Wahrscheinlichkeit von 1/2, S = Y 0 , Y 1 , . . . . Lassen N ( 0 ) und N ( 1 ) sein , die Anzahl von 1 und 0 in S . Senden Sie nun S, wenn entweder X = 1 undXnnnS.=Y.0,Y.1,...N.(0)N.(1)S.X.=1 oder X = 0 und N ( 1 ) < N ( 0 ) ; andernfalls überträgt die eine Komplement von S .N.(1)>N.(0)X.=0N.(1)<N.(0)S.

Siravan
quelle
Ich bin allerdings verwirrt. Sagen Sie in diesem Prozess, dass . Wenn die ersten beiden gesendeten Bits 01 oder 10 sind, beträgt die Wahrscheinlichkeit, dass X 1 ist, wenn diese Bits gesehen werden, 1/2. Das gleiche gilt, wenn wir 11 oder 00 sehen. Dann beträgt die Entropie der bedingten Verteilung nicht 1/3 wie erforderlich. n=3
Suresh Venkat
Wenn 1 ist, können die ersten beiden übertragenen Bits nicht 00 sein. Dann addiert das letzte Bit 1/2 Informationsbits mit einer Wahrscheinlichkeit von 2/3 (die ersten beiden Bits 01 oder 10) und 0 Informationsbits mit einer Wahrscheinlichkeit von 1/3 (11, denn egal was das Ergebnis ist 1). X.
Siravan
Korrektur. Meine vorherige Analyse ist nicht korrekt. Ich denke, es gibt zwei Möglichkeiten, es zu betrachten. Der Algorithmus ist in Bezug auf Bits symmetrisch und überträgt ein Gesamtinformationsbit, sodass jedes Bit 1 / n Informationsbits beitragen sollte. Aber wenn wir die bedingten Wahrscheinlichkeiten berechnen wollen, wird es chaotisch. Ich glaube, die Situation ist eine Variante des Monty Hall-Problems ( en.wikipedia.org/wiki/Monty_Hall_problem ).
Siravan
1
Die Random-Walk-Methode zeigt X am Ende unbedingt an, da der gesendete Endwert . Es erfordert jedoch das Senden von reellen Zahlen anstelle von Bits. Y(0)=X.
Geoffrey Irving