1.2.2 Zufällige Operationen

Wie du vielleicht bemerkt hast, haben wir in der Herleitung von Gl. 1.25 nicht angenommen, dass M⁢[0]M\,[0] und M⁢[1]M\,[1] wieder einer der deterministischen Zustände [0][0] oder [1][1] eines Bits waren (obwohl das für die NOT\mathrm{NOT} Operation der Fall war). Das bedeutet, dass Gl. 1.25 genauso gut funktioniert, wenn M⁢[0]M\,[0] und M⁢[1]M\,[1] probabilistische Bits sind! In diesem Fall nennen wir MM eine zufällige Operation.

Eine der einfachsten zufälligen Operationen ist die folgende: Stell dir vor, du stellst [0][0] als einen horizontal liegenden Bleistift dar und [1][1] indem du den Stift vertikal auf dem Ende balancierst. Wenn du nun mit der Hand sanft auf den Tisch schlägst, fällt der Stift vielleicht um und ändert dabei den Zustand von [1][1] zu [0][0]. Lag der Stift jedoch bereits vorher, ändert sich der Zustand nicht. Also ist das schlagen des Tisches ein probabilistisches Zurücksetzen des Zustands des Stifts zu [0][0]; je stärker du zuschlägst, desto höher ist die Wahrscheinlichkeit des Zurücksetzens.

Mathematisch beschreiben wir einen probabilistischen Reset (reset engl. für “zurücksetzen”) als

R⁢(r)⁢[0]=[0]=(10),R⁢(r)⁢[1]=r⁢[0]+(1−r)⁢[1]=(r1−r),R(r)\,[0]=[0]=\begin{pmatrix}1\\ 0\end{pmatrix},\qquad R(r)\,[1]=r\,[0]+(1-r)\,[1]=\begin{pmatrix}r\\ 1-r\end{pmatrix}, (1.27)

wobei r∈[0,1]r\in[0,1] als die Reset-Wahrscheinlichkeit bezeichnet wird.

Durch Linearität können wir diese Operation auf alle Zustände erweitern:

R⁢(r)⁢(p0p1)\displaystyle R(r)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix} =p0⁢R⁢(r)⁢[0]+p1⁢R⁢(r)⁢[1]\displaystyle=p_{0}\,R(r)\,[0]+p_{1}\,R(r)\,[1]
=p0⁢(10)+p1⁢(r1−r)=(p0+p1⁢rp1⁢(1−r)).\displaystyle=p_{0}\,\begin{pmatrix}1\\ 0\end{pmatrix}+p_{1}\,\begin{pmatrix}r\\ 1-r\end{pmatrix}=\begin{pmatrix}p_{0}+p_{1}r\\ p_{1}(1-r)\end{pmatrix}.

Beachte die beiden Spezialfälle dieser Gleichung R⁢(0)R(0), welcher den Zustand nicht verändert und R⁢(1)R(1), der jeden Zustand zu [0][0] zurücksetzt.


Ein anderes interessantes Beispiel einer zufälligen Operation ist der probabilistische Flip F⁢(f)F(f), der das Inputbit mit Wahrscheinlichkeit ff invertiert oder flippt (engl. für “umdrehen”) und mit Wahrscheinlichkeit 1−f1-f nichts ändert:

F⁢(f)⁢[0]=(1−f)⁢[0]+f⁢[1],F⁢(f)⁢[1]=f⁢[0]+(1−f)⁢[1],F(f)\,[0]=(1-f)\,[0]+f\,[1],\qquad F(f)\,[1]=f\,[0]+(1-f)\,[1], (1.28)

wobei f∈[0,1]f\in[0,1] die Flip-Wahrscheinlichkeit genannt wird. Eine anschauliche Vorstellung eines probabilistischen Flips bietet dir ein Lichtschalter, dessen Zustände [0][0] und [1][1] repräsentieren. Wirfst du nun ein Kissen gegen den Lichtschalter, so ändert sich der Zustand – also das Licht geht an oder aus – mit Wahrscheinlichkeit ff und mit Wahrscheinlichkeit 1−f1-f ändert sich nichts. Du kannst also die Funktion von F⁢(f)F(f) wie folgt visualiseren:

Die folgende Übung wird dir helfen, dich mit dem probabilistischen Flip vertraut zu machen.

Übungsaufgabe 1.6 (Probabilistischer Flip).

Sei F⁢(f)F(f) die probabilistische Flip Operation aus Gl. 1.28.

  1. 1.
    ​

    Schreibe F⁢(f)⁢[0]F(f)\,[0] und F⁢(f)⁢[1]F(f)\,[1] als Vektoren.

  2. 2.
    ​

    Für welchen Wert von ff entspricht F⁢(f)F(f) der NOT\mathrm{NOT} Operation? Wie können wir mit FF ein probabilistisches Bit aus dem [0][0] Zustand in einen beliebigen Zustand (p1−p)\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)} versetzen?

  3. 3.
    ​

    Erweitere F⁢(f)F(f) durch Linearität auf probabilistische Bits indem du F⁢(f)⁢(p0p1)F(f)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)} berechnest.

  4. 4.
    ​

    Sei (p0p1)\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)} eine beliebige Wahrscheinlichkeitsverteilung. Zeige, dass F⁢(1/2)⁢(p0p1)=(1/21/2)F(1/2)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}1/2\\ 1/2\end{smallmatrix}\bigr{)} gilt.

Lösung.
  1. 1.
    ​

    Aus der Definition von F⁢(f)F(f) in Gl. 1.28,

    F⁢(f)⁢[0]\displaystyle F(f)\,[0] =(1−f)⁢(10)+f⁢(01)=(1−ff),\displaystyle=(1-f)\,\bigl{(}\begin{smallmatrix}1\\ 0\end{smallmatrix}\bigr{)}+f\,\bigl{(}\begin{smallmatrix}0\\ 1\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}1-f\\ f\end{smallmatrix}\bigr{)},
    F⁢(f)⁢[1]\displaystyle F(f)\,[1] =f⁢(10)+(1−f)⁢(01)=(f1−f).\displaystyle=f\,\bigl{(}\begin{smallmatrix}1\\ 0\end{smallmatrix}\bigr{)}+(1-f)\,\bigl{(}\begin{smallmatrix}0\\ 1\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}f\\ 1-f\end{smallmatrix}\bigr{)}.
  2. 2.
    ​

    F⁢(f)F(f) flippt das Bit mit Sicherheit wenn f=1f=1, also ist NOT=F⁢(1)\mathrm{NOT}=F(1). Um [0][0] zu einem beliebigem Zustand (p1−p)\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)} zu verändern, müssen wir f=1−pf=1-p wählen. Tatsächlich sieht man aus der ersten Gleichung oben, dass

    F⁢(1−p)⁢[0]=(1−(1−p)1−p)=(p1−p).\displaystyle F(1-p)\,[0]=\begin{pmatrix}1-(1-p)\\ 1-p\end{pmatrix}=\begin{pmatrix}p\\ 1-p\end{pmatrix}.
  3. 3.
    ​

    Nach Gl. 1.25,

    F⁢(f)⁢(p0p1)=p0⁢(1−ff)+p1⁢(f1−f)=(p0⁢(1−f)+p1⁢fp0⁢f+p1⁢(1−f)).\displaystyle F(f)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=p_{0}\begin{pmatrix}1-f\\ f\end{pmatrix}+p_{1}\begin{pmatrix}f\\ 1-f\end{pmatrix}=\begin{pmatrix}p_{0}(1-f)+p_{1}f\\ p_{0}f+p_{1}(1-f)\end{pmatrix}.
  4. 4.
    ​

    Wenn man f=1/2f=1/2 in die vorige Gleichung einsetzt, erhält man

    F⁢(1/2)⁢(p0p1)=(p0/2+p1/2p0/2+p1/2)=12⁢(p0+p1p0+p1)=12⁢(11).F(1/2)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=\begin{pmatrix}p_{0}/2+p_{1}/2\\ p_{0}/2+p_{1}/2\end{pmatrix}=\frac{1}{2}\begin{pmatrix}p_{0}+p_{1}\\ p_{0}+p_{1}\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\ 1\end{pmatrix}.

Die letzte Aufgabe der Übungsaufgabe zeigt, dass F⁢(1/2)F(1/2) immer zur Gleichverteilung (engl. uniform distribution) führt, egal wie die eingehende Verteilung aussieht. Das ist nützlich, wenn man einen fairen Münzwurf simulieren will. Tatsächlich wirst du in der nächsten Hausaufgabe zeigen, dass man durch verändern der Flip-Wahrscheinlichkeit die Fairness der Münze ändern kann.

Hausaufgabe 1.3 (Schokoladenmünzen).

Es ist der 15. Mai und Bob feiert Geburtstag! Da er Schokolade liebt, hat Alice sich entschlossen, ihm eine Schokoladenmünze zu machen. Damit die Münze ganz besonders ist, hat sie die Münze so geformt, dass sie genau mit der Wahrscheinlichkeit q=5/15q=5/15, die seinem Geburtstag entspricht, auf [Uncaptioned image] landet, wenn man sie zuvor kreiseln lässt. Nach langem ausprobieren hat sie endlich genau die richtige Form gefunden. Aufgeregt lässt sie die Münze auf dem Tisch liegen, um eine Geburtstagskarte zu kaufen.

Als sie zurückkommt, muss sie leider feststellen, dass die Münze in der Sonne lag und eine Kante ein wenig angeschmolzen ist. Durch ausprobieren stellt sie fest, dass die neue Wahrscheinlichkeit von [Uncaptioned image] jetzt p=4/15p=4/15 ist. Leider hat sie keine Zeit mehr um eine neue Münze zu machen, also schreibt sie in die Geburtstagskarte, dass Bob die Münze nach dem Kreiseln mit Wahrscheinlichkeit ff einfach umdrehen soll, damit [Uncaptioned image] genau mit Wahrscheinlichkeit qq eintritt. Hilf Alice herauszufinden, welchen Wert ff haben sollte.

Hinweis: Die Werte p,qp,q und ff sollten folgende Gleichung erfüllen: F⁢(f)⁢(p1−p)=(q1−q)F(f)\,\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)}.

Hack.

Erinnere dich an deine Lösung von 1.6:

F⁢(f)⁢(p1−p)=p⁢(1−ff)+(1−p)⁢(f1−f)=(p⁢(1−f)+(1−p)⁢fp⁢f+(1−p)⁢(1−f)).\displaystyle F(f)\,\begin{pmatrix}p\\ 1-p\end{pmatrix}=p\begin{pmatrix}1-f\\ f\end{pmatrix}+(1-p)\begin{pmatrix}f\\ 1-f\end{pmatrix}=\begin{pmatrix}p(1-f)+(1-p)f\\ pf+(1-p)(1-f)\end{pmatrix}.

Diese Gleichung soll gleich (q1−q)\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)} sein, also erhalten wir

p⁢(1−f)+(1−p)⁢f\displaystyle p(1-f)+(1-p)f =q,\displaystyle=q,
p⁢f+(1−p)⁢(1−f)\displaystyle pf+(1-p)(1-f) =1−q.\displaystyle=1-q.

Durch Lösen einer der Gleichungen nach ff erhalten wir

f=q−p1−2⁢p.f=\frac{q-p}{1-2p}.
Übungsaufgabe 1.7 (Flip durch Reset und NOT\mathrm{NOT}).

Wie kannst du F⁢(f)F(f) aus den R⁢(r)R(r) und NOT\mathrm{NOT} Operationen bauen?

Lösung. Wir unterscheiden zwei Fälle:
  • •
    ​

    12≤f≤1\frac{1}{2}\leq f\leq 1: In diesem Fall gilt 0≤1−ff≤10\leq\frac{1-f}{f}\leq 1. Wir behaupten, dass die Flip-Operation F⁢(f)F(f) gebaut werden kann, indem zuerst R⁢(1−ff)R(\tfrac{1-f}{f}), dann NOT\mathrm{NOT} und dann R⁢(1−f)R(1-f) angewendet wird. Tatsächlich gilt:

    R⁢(1−f)⁢NOT⁢R⁢(1−ff)⁢[0]=R⁢(1−f)⁢NOT⁢[0]=R⁢(1−f)⁢[1]=(1−f)⁢[0]+f⁢[1]\displaystyle R(1-f)\,\mathrm{NOT}\,R(\tfrac{1-f}{f})\,[0]=R(1-f)\,\mathrm{NOT% }\,[0]=R(1-f)\,[1]=(1-f)\,[0]+f\,[1]

    und

    R⁢(1−f)⁢NOT⁢R⁢(1−ff)⁢[1]\displaystyle R(1-f)\,\mathrm{NOT}\,R(\tfrac{1-f}{f})\,[1] =R⁢(1−f)⁢NOT⁢(1−ff⁢[0]+(1−1−ff)⁢[1])\displaystyle=R(1-f)\,\mathrm{NOT}\,\Bigl{(}\tfrac{1-f}{f}\,[0]+(1-\tfrac{1-f}% {f})\,[1]\Bigr{)}
    =R⁢(1−f)⁢((1−1−ff)⁢[0]+1−ff⁢[1])\displaystyle=R(1-f)\,\Bigl{(}(1-\tfrac{1-f}{f})\,[0]+\tfrac{1-f}{f}\,[1]\Bigr% {)}
    =(1−1−ff)⁢[0]+1−ff⁢((1−f)⁢[0]+f⁢[1])\displaystyle=(1-\tfrac{1-f}{f})\,[0]+\tfrac{1-f}{f}\left((1-f)\,[0]+f\,[1]\right)
    =f⁢[0]+(1−f)⁢[1].\displaystyle=f\,[0]+(1-f)\,[1].
  • •
    ​

    0≤f≤120\leq f\leq\frac{1}{2}: Dieser Fall kann auf den ersten reduziert werden, da F⁢(f)F(f) anzuwenden das gleiche ist wie zunächst F⁢(1−f)F(1-f) und anschließend NOT\mathrm{NOT}.