1.2.2 Willekeurige bewerkingen

Merk op dat we in onze afleiding van Vgl. 1.25 niet hebben aangenomen dat $M\,[0]$ en $M\,[1]$ weer één van de twee deterministische toestanden $[0]$ of $[1]$ van een bit waren (al was dit toevallig wel het geval voor de NOT-bewerking). Dit betekent dat Vgl. 1.25 net zo goed werkt als $M\,[0]$ of $M\,[1]$ probabilistische bits zijn! In dat geval zeggen we dat $M$ een willekeurige bewerking is.

Een van de simpelste voorbeelden van een willekeurige bewerking is als volgt. Stel je voor dat je $[0]$ beschrijft door een potlood horizontaal op een tafel te leggen en $[1]$ door het verticaal te balanceren. Als je voorzichtig met je hand op de tafel slaat, kan het potlood omvallen, waardoor de toestand verandert van $[1]$ in $[0]$ . Maar als het al op de tafel lag, verandert de toestand $[0]$ niet. Dus door de tafel te slaan wordt de toestand van het potlood met een zekere waarschijnlijkheid gereset naar $[0]$ ; Hoe harder je slaat, hoe groter de waarschijnlijkheid dat je het potlood reset.

Wiskundig gezien wordt deze probabilistische reset beschreven door een bewerking $R(r)$ die gedefinieerd is als

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)

waarbij $r\in[0,1]$ de reset-waarschijnlijkheid is. Je kunt het effect van deze bewerking als volgt voor je zien:

Door lineariteit kunnen we deze bewerking uitbreiden naar alle toestanden:

	$\displaystyle R(r)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}$	$\displaystyle=p_{0}\,R(r)\,[0]+p_{1}\,R(r)\,[1]$
		$\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}.$

De speciale gevallen van deze vergelijking zijn dat $R(0)$ de toestand helemaal niet verandert, terwijl $R(1)$ elke toestand reset naar $[0]$ .

Een ander interessant voorbeeld van een willekeurige bewerking is de probabilistische flip bewerking $F(f)$ die de invoerbit flipt met kans $f$ en met rust laat met kans $1-f$ :

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

(1.28)

waarbij $f\in[0,1]$ de flip-waarschijnlijkheid is. Om het wat intuïtiever te maken, stel je voor dat $[0]$ en $[1]$ twee toestanden van een lichtschakelaar aan de muur voorstellen. Als je een kussen naar de schakelaar gooit, zul je hem met waarschijnlijkheid $f$ met succes raken en flippen, en met waarschijnlijkheid $1-f$ onveranderd laten. Je kunt het effect van $F(f)$ dus als volgt voorstellen:

De volgende oefenopgave zal helpen om de probabilistische flip-bewerking beter te leren kennen.

Oefenopgave 1.6 (Probabilistische flip).

$F(f)$ staat hier voor de probabilistische flip bewerking van Vgl. 1.28.

1.

Schrijf $F(f)\,[0]$ en $F(f)\,[1]$ op als vectoren.
2.

Voor welke waarde van $f$ gedraagt $F(f)$ zich als $\mathrm{NOT}$ ? Hoe kunnen we met behulp van $F$ een probabilistische bit in een willekeurige toestand $\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}$ voorbereiden vanuit $[0]$ ?
3.

Breid $F(f)$ door lineariteit uit naar probabilistische bits door $F(f)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ te berekenen.
4.

Laat $\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ een arbitraire kansverdeling zijn. Laat zien dat $F(1/2)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}1/2\\ 1/2\end{smallmatrix}\bigr{)}$ .

Solution.

We gebruiken de definitie van $F(f)$ uit Vgl. 1.28,

	$\displaystyle F(f)\,[0]$	$\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{)},$
	$\displaystyle F(f)\,[1]$	$\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.

$F(f)$ flipt de bit met zekerheid als $f=1$ , dus $\mathrm{NOT}=F(1)$ . Om een willekeurige toestand $\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}$ te maken vanuit $[0]$ moeten we $f=1-p$ kiezen. Uit de eerste vergelijking hierboven volgt dan dat

$\displaystyle F(1-p)\,[0]=\begin{pmatrix}1-(1-p)\\ 1-p\end{pmatrix}=\begin{pmatrix}p\\ 1-p\end{pmatrix}.$

Gebruik Vgl. 1.25,

\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.

Als je $f=1/2$ in de vorige vergelijking invult krijg je

$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}.$

Uit het laatste deel van deze opgave blijkt dat $F(1/2)$ altijd de uniforme verdeling oplevert, ongeacht de verdeling waarmee je begint. Dit kan gebruikt worden om het opgooien van een zuiver muntje te simuleren. In de volgende opgave zul je zien dat je door het zorgvuldig aanpassen van de flip-waarschijnlijkheid $f$ , je ook $F(f)$ kunt gebruiken om de partijdigheid van een muntje te veranderen.

Huiswerkopdracht 1.3 (Chocolade muntje).

Bob is vandaag jarig! Omdat hij dol is op chocolade besluit Alice een chocolade muntje voor hem te maken. Om het cadeau extra speciaal te maken, wil ze het muntje zo maken dat het, als je het op tafel laat tollen, zal landen op met een waarschijnlijkheid $q=5/15$ , wat staat voor de verjaardag van Bob, 15 mei. Na wat experimenteren met verschillende vormen slaagt Alice erin een chocolade muntje met de juiste waarschijnlijkheid te produceren. Enthousiast laat ze het op tafel liggen en rent ze naar de winkel om een mooie verjaardagskaart te kopen.

Wanneer ze terugkeert, komt Alice er plotseling achter dat het muntje in de zon is blijven liggen en dat de rand ervan is gesmolten. Na wat uitproberen stelt Alice vast dat de nieuwe waarschijnlijkheid om te krijgen, $p=4/15$ is. Er is nog te weinig tijd om het probleem op te lossen, dus Alice schrijft op de verjaardagskaart dat zodra het muntje is gevallen, Bob hem moet omdraaien met waarschijnlijkheid $f$ , en alleen dan zal hij met de juiste waarschijnlijkheid $q$ waarnemen. Help Alice de juiste waarde van $f$ te bepalen.

Hint: De waardes $p$ , $q$ en $f$ moeten voldoen aan $F(f)\,\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)}$ .

Hack.

Recall from your solution to 1.6 that

\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}.

We want this to be equal to $\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)}$ , so we get

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

Solving any of the two equations for $f$ , we find

f=\frac{q-p}{1-2p}.

Substituting $p=4/15$ and $q=5/15$ , we get $f=1/7$ . Setzen wir $p=4/15$ und $q=5/15$ ein, erhalten wir das Ergebnis $f=1/7$ .

Oefenopgave 1.7 (Flip vanuit de reset en NOT (optioneel en uitdagend)).

Hoe kan je $F(f)$ maken vanuit de bewerkingen $R(r)$ en $\mathrm{NOT}$ ?

Solution.

We bekijken twee gevallen:

•

$\frac{1}{2}\leq f\leq 1$ : In dit geval geldt $0\leq\frac{1-f}{f}\leq 1$ . We stellen dat de flipbewerking $F(f)$ kan worden opgebouwd door eerst $R(\tfrac{1-f}{f})$ toe te passen, dan $\mathrm{NOT}$ , en tenslotte $R(1-f)$ . Als je dit uitwerkt zie je inderdaad:

\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]

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

•

$0\leq f\leq\frac{1}{2}$ : Dit geval kunnen we omschrijven naar het eerste geval, aangezien $F(f)$ hetzelfde is als eerst $F(1-f)$ toepassen en daarna $\mathrm{NOT}$ .