1.1.3 Probability and computation

Is there any use of probabilistic bits in computation? It might seem at first that they are not particularly useful since the values $0$ and $1$ of a regular bit represent definite knowledge while a probabilistic bit represents approximate knowledge (or the lack of knowledge). Why should I waste the space on my computer to store probabilistic bits that reflect my lack of information if instead I could store the actual information that I have, even if it is incomplete? The advantage of probabilistic bits is that they represent partial knowledge more accurately – if you don’t know something, it is better to admit it and make a random guess rather than pretend that you know the correct answer with certainty. This is illustrated in the problem below where Alice’s donkey robot has to make a decision while lacking full information.

Homework 1.2 (Alice’s donkey).

Problem: Alice wants to program her donkey robot so that it can walk on its own to a charging station and charge itself. There are three nearby stations, each at a distance of 1 km from the donkey, forming an equilateral triangle with the donkey located in its center. Alice’s donkey has enough battery left to walk only 2.8 km.

Alice is going to upload a program to her donkey robot that tells it where to go, however she knows that her evil classmate Eve is trying to sabotage her. Since Eve can read everything that’s transmitted over the WiFi, Eve can also see what program Alice is uploading. Because of this, once the program is uploaded, Alice will disconnect her donkey from the WiFi so that Eve cannot follow its movements. While the donkey walks, the only way for Eve to sabotage it is by hacking and disabling the charging stations towards which it has been programmed to go. However, Eve can shut down only two stations before her intrusion is detected. Since Eve cannot follow the donkey’s movements, she has to decide which two charging stations to disable based only on Alice’s program.

Questions:

1.

How many charging stations can the donkey visit before its battery runs out?
2.

Assume that Alice programs her donkey to visit stations in some predetermined order. Can Eve prevent it from reaching a working charging station? Remember that Eve has full access to Alice’s program and so she knows in what order the donkey is programmed to visit the stations.
3.

Assume that Alice programs the donkey to make its own random choices about where to go. (While Eve can see that this is what Alice has programmed, she cannot predict what choices the donkey will make once it starts to walk.) What randomized strategy should Alice upload to the donkey, and what hacking strategy should Eve use to counteract it? What is the probability that Alice’s donkey successfully reaches a working charging station if both Alice and Eve are using optimal strategies?

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