Welche dieser beiden Sequenzen ist zufällig und welche nicht?

7

Wir lassen α=α1α2α3 sei eine unendliche Zufallsfolge (unter dem einheitlichen Maß) wo αi könnte sein 1 oder 0und definieren Sie dann die Boolesche Funktion Bk::

Bk(α1αk)={1 if at least k/2 of its inputs are 10 otherwise

Dann definieren wir zwei Sequenzen:

B3(α1α2α3)B3(α4α5α6)B3(α7α8α9)
B4(α1α2α3α4)B4(α5α6α7α8)B4(α9α10α11α12)

Welche dieser beiden Sequenzen ist ( algorithmisch ) zufällig und warum? Ich sollte beachten, dass es anscheinend eine offensichtliche messungstheoretische Tatsache gibt, die verrät, welche nicht zufällig ist.

Newb
quelle
1
Wenn k=2n+1 dann P(Bk=1)<P(Bk=0). Ist das informell nicht ausreichend?
OJFord
vielleicht eine verwandte Frage
Nikos M.
Ist nicht jeder Bk Sequenz die gleiche wie die Teilsummensequenz von ai's (oder genauer gesagt die Differenz von 2 Teilsummensequenzen)?
Nikos M.
Ich kann auch eine andere Art von Antwort in sigal verarbeitenden Begriffen geben. JederBk Die Sequenz wirkt als Tiefpassfilter (Herausfiltern hoher Frequenzen), da zufälliges Rauschen jeweils besonders hohe Frequenzen aufweist Bksollte zunehmend weniger zufällig sein (eventuell gleich einer Folge von Einsen).
Nikos M.
1
@Newb Laut dem von Ihnen verlinkten Wikipedia-Artikel gibt es mehrere Möglichkeiten und die Standardeinstellung ist eine Konvention des Feldes. Sie sollten hier vorsichtig sein, solche Konventionen ohne Klärung zu verwenden - nicht jeder Leser ist ein Domain-Experte.
Raphael

Antworten:

2

Die zweite Sequenz ist nicht zufällig. Lassenα1,α2,α3,α4 sei zufällig, iid Bernoulli 1/2zufällige Variablen. Lassenβ=B4(α1α2α3α4).

Wie ist die Verteilung der Zufallsvariablen? β? Antworten:β=1 wenn mindestens zwei der αsind 1, damit Pr[β=1]=11/16.

Mit anderen Worten, ist auf . Daraus folgt, dass die zweite Sequenz nicht algorithmisch zufällig ist: Es handelt sich um eine Menge unabhängiger Bernoulli-Zufallsvariablen mit , dh das Ergebnis einer unendlichen Folge von Würfen einer voreingenommenen Münze.β1p=11/16

DW
quelle
Gut! Das macht durchaus Sinn. Vielen Dank. Haben Sie Gründe, warum die erste Sequenz zufällig ist?
Newb
1
Im Gegensatz dazu liegt es daran, dass "fair" ist: Es gibt 4 3-Bit-Sequenzen, die auf 1 abbildet, und 4 3-Bit-Sequenzen, die auf 0 abgebildet werden. Unter der Annahme, dass die ursprüngliche Sequenz zufällig ist, ist . B3B3Pr[B=1]=Pr[B=0]=12
Gardenhead
Ich stimme dem nicht zu, es heißt nur, dass die Zufallsvariable nicht die gleichen p1- und p2-Wahrscheinlichkeiten hat. Warum wird eine Zufallsvariable mit P1 = 1/3 und P0 = 2/3 nicht als zufällig angesehen? Warum sind RVs mit einer anderen Verteilung nicht zufällig (ein Gaußscher RV ist nicht zufällig, er ist auf den Mittelwert ausgerichtet)? β
Nikos M.
Tatsächlich poste ich eine Frage (bald?), Die die Beziehung zwischen probabilistischer und algorithmischer Zufälligkeit anspricht (gemäß der anderen Frage, die ich in den Kommentaren verlinkt habe)
Nikos M.
Ich denke, Sie haben Recht, obwohl beide in gewissem Sinne zufällig sind, ist algorithmisch zufällig nicht dasselbe wie probabilistisch zufällig. Da ich kein Experte für algorithmische Zufälligkeit bin, kann ich das wirklich sagen. Ich würde mich auch für eine Ausarbeitung dieser Punkte interessieren.
Gardenhead