Wandering Robots

It was quite an ordinary day when a mysterious alien vessel appeared as if from nowhere. After waiting several hours and receiving no response it is decided to send a team to investigate, of which you are included. Upon entering the vessel you are met by a friendly holographic figure, Katharina, who explains the purpose of the vessel, Eulertopia.
She claims that Eulertopia is almost older than time itself. Its mission was to take advantage of a combination of incredible computational power and vast periods of time to discover the answer to life, the universe, and everything. Hence the resident cleaning robot, Leonhard, along with his housekeeping responsibilities, was built with a powerful computational matrix to ponder the meaning of life as he wanders through a massive 1000 by 1000 square grid of rooms. She goes on to explain that the rooms are numbered sequentially from left to right, row by row. So, for example, if Leonhard was wandering around a 5 by 5 grid then the rooms would be numbered in the following way.

Many millenia ago Leonhard reported to Katharina to have found the answer and he is willing to share it with any life form who proves to be worthy of such knowledge.
Katharina further explains that the designers of Leonhard were given instructions to program him with equal probability of remaining in the same room or travelling to an adjacent room. However, it was not clear to them if this meant (i) an equal probability being split equally between remaining in the room and the number of available routes, or, (ii) an equal probability (50%) of remaining in the same room and then the other 50% was to be split equally between the number of available routes.

(i) Probability of remaining related to number of exits
(ii) Fixed 50% probability of remaining

The records indicate that they decided to flip a coin. Heads would mean that the probability of remaining was dynamically related to the number of exits whereas tails would mean that they program Leonhard with a fixed 50% probability of remaining in a particular room. Unfortunately there is no record of the outcome of the coin, so without further information we would need to assume that there is equal probability of either of the choices being implemented.
Katharina suggests it should not be too challenging to determine that the probability of finding him in a square numbered room in a 5 by 5 grid after unfathomable periods of time would be approximately 0.177976190476 [12 d.p.].
In order to prove yourself worthy of visiting the great oracle you must calculate the probability of finding him in a square numbered room in the 1000 by 1000 lair in which he has been wandering.
(Give your answer rounded to 12 decimal places)

This is a complicated probability and combinatorics problem. The best way to solve it is to set up a system of equations based on the constraints given, and then to solve that system of equations using programming or other numerical methods. Here is an outline of how to approach this:

First, notice that the probability of ending up in any given room can be described by the probabilities of ending up in the rooms adjacent to it. If we take into account the two possible interpretations of the rule – (i) the probability of staying put is inversely proportional to the number of exits, or (ii) the probability of staying put is a fixed 50% regardless of the number of exits – then we can come up with two different equations describing the probabilities.

Let’s denote:
– the probability of finding Leonhard in room `i` under rule (i) as `P[i,1]`,
– the probability of finding Leonhard in room `i` under rule (ii) as `P[i,2]`,
– `N[i]` the number of exits for the room `i`, and
– `adj[i]` the set of rooms adjacent to room `i`.

Then, we can describe our probabilities as follows:

Under rule (i)
P[i,1] = (1/2N[i] + sum(P[ad,1]/(2*N[ad])) for ad in adj[i]) / (1 + sum(1/N[ad]) for ad in adj[i])

Under rule (ii)
P[i,2] = 0.5*P[i,1] + 0.5*sum(P[ad,2]/N[ad] for ad in adj[i])

These are two sets of equations – with 1,000,000 equations each – that we must solve simultaneously. It’s difficult to solve these by hand, but a computer can do it.

However, it’s important to note that it states we have to assume that each rule is equally likely, so the final probability for each room should be the average of the probabilities under each rule, P[i] = (P[i,1] + P[i,2]) / 2.

Then, you want to sum up these final probabilities for all the “square numbered” rooms.

“Square numbered” rooms are those numbered 1, 4, 9, 16, and so on up to 1,000,000. You only need to consider the squares up to 1,000^2=1,000,000 -> 1,4,9,…,1000000. These are rooms which are located diagonally from top left to bottom right.

You should solve this problem systematically using a language with good libraries for numerical solutions of large systems of equations, like Python with the scipy library, or Matlab.

Please note that solving these equations will take some computational resources and time even on a powerful computer.

More Answers: