1.1.3 Wahrscheinlichkeiten und Berechnungen

Sind probabilistische Bits für Berechnungen überhaupt von Nutzen? Auf den ersten Blick mag es so aussehen, als seien sie es nicht, da die Werte $0$ und $1$ eines normalen bits definitives Wissen darstellen, während ein probabilistisches bit ja nur ungefähres Wissen (also ein Mangel an Wissen) repräsentiert. Warum sollte ich also Speicherplatz auf meinem Computer verschwenden, um probabilistische bits zu speichern, die nur den Mangel an Information widerspiegeln, wenn ich doch einfach die Information speichern könnte, die ich habe, selbst wenn sie unvollständig ist. Der Vorteil von probabilistischen Bits ist, dass sie Teilwissen genauer darstellen können – wenn du etwas nicht weißt, ist es besser das zuzugeben und zufällig zu raten, als so zu tun, als wüsstest du die Antwort sicher. Im folgenden Problem wird das noch einmal anschaulich dargestellt. Hier muss Alice’ Eselsroboter eine Entscheidung treffen muss, ohne alle Informationen zu haben.

Hausaufgabe 1.2 (Alice’ Esel).

Das Problem: Alice will ihren Eselsroboter so programmieren, dass er alleine zu einer Ladestation laufen kann, um sich dort aufzuladen. Es gibt drei Ladestationen in der Nähe. Sie sind alle jeweils 1 km vom Roboter entfernt und bilden ein gleichseitiges Dreieck – mit dem Esel in der Mitte. Der Roboter hat noch genügend Akku, um 2,8 km zu laufen.

Alice wird das Programm, welches den Roboter die Ladestation aussuchen lässt, per WiFi auf ihn hochladen. Sie weiß aber, dass ihre böse Klassenkameradin Eve sie sabotieren will. Da Eve das WiFi überwacht, kann sie den Programmcode mitlesen. Damit Eve nicht sehen kann, wohin der Esel läuft, schaltet Alice das WiFi des Roboters aus, sobald das Programm hochgeladen ist. Solange der Esel dann läuft, kann Eve ihn also nur sabotieren, indem sie Ladestationen hackt und deaktiviert. Sie kann allerdings nur zwei der drei Ladestationen deaktivieren, bevor sie entdeckt wird. Da Eve nicht sehen kann, wohin der Roboter läuft, muss sie sich also nur auf Grund von Alice’ Programm entscheiden, welche zwei Ladestationen sie deaktivieren will.

Fragen:

1.

Wie viele Ladestationen kann der Esel besuchen, bevor seine Batterie leer ist?
2.

Nimm an, dass Alice ihren Roboter so programmiert, dass er die Ladestationen in einer festgelegten Reihenfolge besucht. Kann Eve verhindern, dass der Roboter eine funktionierende Station erreicht? Bedenke, dass Eve Alice’ Programmcode mitlesen kann. Sie weiß also, in welcher Reihenfolge der Esel die Stationen ablaufen wird.
3.

Nimm an, dass Alice ihren Roboter so programmiert, dass dieser selbst zufällig entscheiden kann, wo er hinwill. (Eve kann zwar sehen, was Alice programmiert hat, kann aber nicht vorhersehen, welche Entscheidungen der Esel trifft, sobald er anfängt loszulaufen.) Was für eine Strategie sollte Alice dem Esel einprogrammieren, und wie sollte Eve auswählen, welche Stationen sie deaktiviert, um dem entgegen zu wirken? Mit welcher Wahrscheinlichkeit wird der Esel eine funktionierende Ladestation erreichen, falls sowohl Alice als auch Eve bestmögliche Strategien verwenden?

Hack.

1.

Wenn die Distanz vom Zentrum eines gleichseitigen Dreiecks zu allen Eckpunkten 1km ist, dann hat jede Seite die Länge $\sqrt{3}\text{ km}\approx 1.73\text{ km}$ , da $\cos 30^{\circ}=\frac{\sqrt{3}}{2}$ . Der Roboter muss also $1\text{ km}+1.73\text{ km}=2.73\text{ km}$ weit laufen, um die ersten beiden Ladestationen zu erreichen und hat dann nicht mehr genügend Akku umd die letzte zu besuchen.
2.

Ja, da Eve einfach die beiden Stationen hacken kann, die der Esel zuerst besucht.
3.

Alice’ Strategie: wähle die erste Station zufällig aus, danach wähle die Station zur linken (oder wähle zufällig zwischen der linken und der rechten). Eve kann nur gewinnen, wenn sie genau die zwei Stationen hackt, die der Esel uniform (“gleichverteilt”) zufällig auswählt. Das ist gleichbedeutend zu: Eve muss raten, welche Station der Esel nicht besucht. Da die Stationen uniform zufällig gewählt werden, rät sie mit Wahrscheinlichkeit $\frac{1}{3}$ richtig und gewinnt. Damit gewinnt Alice mit Wahrscheinlichkeit $\frac{2}{3}$ .