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

Wir lassen $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ sei eine unendliche Zufallsfolge (unter dem einheitlichen Maß) wo $\alpha_i$ könnte sein $1$ oder $0$ und definieren Sie dann die Boolesche Funktion $B_k$ ::

B_{k} (α_{1} \dots α_{k}) = {\begin{cases} 1 if at least ⌈ k / 2 ⌉ of its inputs are 1 \\ 0 otherwise \end{cases}

$B_k(\alpha_1\ldots\alpha_k) = \begin{cases} 1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1 \\ 0 \text{ otherwise} \end{cases}$

Dann definieren wir zwei Sequenzen:

B_{3} (α_{1} α_{2} α_{3}) B_{3} (α_{4} α_{5} α_{6}) B_{3} (α_{7} α_{8} α_{9}) \dots

$B_3(\alpha_1\alpha_2\alpha_3)B_3(\alpha_4\alpha_5\alpha_6)B_3(\alpha_7\alpha_8\alpha_9)\ldots$

B_{4} (α_{1} α_{2} α_{3} α_{4}) B_{4} (α_{5} α_{6} α_{7} α_{8}) B_{4} (α_{9} α_{10} α_{11} α_{12}) \dots

$B_4(\alpha_1\alpha_2\alpha_3\alpha_4)B_4(\alpha_5\alpha_6\alpha_7\alpha_8)B_4(\alpha_9\alpha_{10}\alpha_{11}\alpha_{12})\ldots$

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.

probability-theory randomness Newb
quelle

Wenn

k = 2 n + 1

$k=2n+1$ dann

P (B_{k} = 1) < P (B_{k} = 0)

$P(B_k = 1) < P(B_k = 0)$ . Ist das informell nicht ausreichend?

OJFord

vielleicht eine verwandte Frage

Nikos M.

Ist nicht jeder

B_{k}

$B_k$ Sequenz die gleiche wie die Teilsummensequenz von

a_{i}

$a_i$ 's (oder genauer gesagt die Differenz von 2 Teilsummensequenzen)?

Nikos M.

Ich kann auch eine andere Art von Antwort in sigal verarbeitenden Begriffen geben. Jeder

B_{k}

$B_k$ Die Sequenz wirkt als Tiefpassfilter (Herausfiltern hoher Frequenzen), da zufälliges Rauschen jeweils besonders hohe Frequenzen aufweist

B_{k}

$B_k$ sollte zunehmend weniger zufällig sein (eventuell gleich einer Folge von Einsen).

Nikos M.

@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:

Die zweite Sequenz ist nicht zufällig. Lassen $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ sei zufällig, iid Bernoulli $1/2$ zufällige Variablen. Lassen $\beta = B_4(\alpha_1 \alpha_2 \alpha_3 \alpha_4)$ .

Wie ist die Verteilung der Zufallsvariablen? $\beta$ ? Antworten: $\beta=1$ wenn mindestens zwei der $\alpha$ sind $1$ , damit $\Pr[\beta=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. $\beta$ $1$ $p=11/16$

DW
quelle

Gut! Das macht durchaus Sinn. Vielen Dank. Haben Sie Gründe, warum die erste Sequenz zufällig ist?

Newb

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 .

B_{3}

$B_3$

B_{3}

$B_3$

P r [B = 1] = P r [B = 0] = \frac{1}{2}

$Pr[B=1] = Pr[B=0] = \frac12$

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

β

$\beta$

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