1.1.3 Waarschijnlijkheid en berekeningen

Zijn probabilistische bits eigenlijk wel nuttig voor berekeningen? In eerste instantie lijkt het misschien dat ze niet bijzonder zinvol zijn, omdat de waarden $0$ en $1$ van een gewone bit staan voor definitieve informatie, terwijl een probabilistische bit staat voor beperkte informatie (of het gebrek aan informatie). Waarom zou ik opslagruimte op mijn computer verspillen aan probabilistische bits die mijn gebrek aan informatie aangeven, als ik in plaats daarvan ook de werkelijke informatie die ik heb kan opslaan, ook al is die incompleet? Het voordeel van probabilistische bits is dat ze gedeeltelijke kennis nauwkeuriger beschrijven – als je iets niet weet, is het beter om dat te erkennen en een gok te wagen dan het is om te doen alsof je het juiste antwoord met zekerheid weet. Dit wordt toegelicht in de volgende opdracht, waarin Alice’s robot-ezel een beslissing moet maken zonder alle informatie te hebben.

Huiswerkopdracht 1.2 (Alice’s ezel).

Het probleem: Alice wil haar robot-ezel zo programmeren dat hij uit zichzelf naar een laadstation kan lopen en zichzelf kan opladen. Er zijn drie stations in de buurt, elk op een afstand van 1 km van de ezel, die een gelijkzijdige driehoek vormen met de ezel in het midden. Alice’s ezel heeft nog maar genoeg batterij over om 2,8 km te lopen.

Alice is van plan om een programma te uploaden naar de robot-ezel die hem vertelt waar hij heen moet lopen, maar ze weet dat haar kwaadaardige klasgenoot Eve probeert haar te saboteren.

Omdat Eve alles kan lezen wat over de WiFi wordt uitgezonden, kan Eve ook zien welk programma Alice aan het uploaden is. Daarom gaat Alice, zodra het programma is geüpload, haar ezel loskoppelen van de WiFi, zodat Eve zijn bewegingen niet kan volgen. Terwijl de ezel loopt, is de enige manier voor Eve om de ezel te saboteren, het hacken en uitschakelen van de laadstations waar hij naar toe is geprogrammeerd. Maar Eve kan slechts twee stations uitschakelen voordat haar inbraak wordt ontdekt. Omdat Eve de bewegingen van de ezel niet kan volgen, moet ze alleen op basis van Alice’ programma beslissen welke twee laadstations ze wil uitschakelen.

Vragen:

1.

Hoeveel laadstations kan de ezel bezoeken voordat haar batterij leeg is?
2.

Stel dat Alice haar ezel zo programmeert dat hij de stations in een bepaalde volgorde bezoekt. Kan Eve voorkomen dat de ezel een werkend laadstation bereikt? Hou in gedachten dat Eve volledige toegang heeft tot Alice’s programma en dus weet in welke volgorde de ezel geprogrammeerd is om de stations te bezoeken.
3.

Stel dat Alice de ezel programmeert om voor zichzelf willekeurige keuzes te maken over waar hij heen gaat. (Eve kan zien dat Alice dit heeft geprogrammeerd, maar ze kan niet voorspellen welke keuzes de ezel zal maken als hij eenmaal begint te lopen). Welke strategie moet Alice uploaden naar de ezel, en welke hackstrategie moet Eve gebruiken om deze strategie tegen te gaan? Wat is de kans dat Alice’s ezel met succes een werkend laadstation bereikt als zowel Alice als Eve optimale strategieën gebruiken?

Hack.

1.

If the distance from the center of an equilateral triangle to all its vertices is 1km then each of its sides has length $\sqrt{3}\text{ km}\approx 1.73\text{ km}$ because $\cos 30^{\circ}=\frac{\sqrt{3}}{2}$ . The donkey must walk $1\text{ km}+1.73\text{ km}=2.73\text{ km}$ to visit the first two charging stations and it cannot reach the third station.
2.

Yes, since Eve can hack the two stations that Alice has programmed the donkey to visit first.
3.

Alice’s strategy: choose the first station to visit at random, then turn left to visit the next one (or just choose randomly among the two remaining ones). Eve can only guess two stations uniformly at random and she wins only if she correctly guesses both stations the donkey will visit. Equivalently, Eve has to guess which station the donkey will not visit. Since this is uniformly distributed, Eve can only win with probability $\frac{1}{3}$ . Hence Alice wins with probability $\frac{2}{3}$ .