Problem 575
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)
游荡的机器人
在一个相当平常的日子里，一艘神秘的外星飞船突然不知从何出现并降临到地球上。在等待了数小时没有收到应答之后，包括你在内的一支调查队被派上外星飞船。进入飞船之后，你碰到了一个友善的全息智能，自称叫“凯瑟琳”，她向你解释了这艘飞船“欧拉邦”号的目的。
她说，欧拉邦号比时间的存在还要久远。它的使命是将一种不可思议的计算能力和漫长的时间相结合，以探求生命、宇宙和一切的答案。飞船上的常驻清洁机器人“莱昂哈德”，除了清洁飞船的职能之外，还内置了一个强大的计算矩阵，使得其在庞大的1000乘1000方形网格房间中四处游荡清扫时能够思考生命的意义。她进一步解释说，这些房间是按照行从上至下，从左至右的顺序进行编号的。举例来说，如果莱昂哈德是在5乘5的方形网格房间中四处游荡，那么这些房间的编号如下所示：
数百万年前，莱昂哈德曾经向凯瑟琳报告说已经找到了答案，并且他愿意将其分享给能够证明其值得拥有这份知识的任意生命形式。
凯瑟琳又解释道，莱昂哈德的设计者们接受到的指令说，要让他以相等的概率停留在当前房间或移动到相邻的房间。但是，设计者们不知道这句话到底指的是(i)将概率平均分配给停留在当前房间和所有其它可行的路径上，还是(ii)将相等的概率(50%)分配给停留在当前房间，再将剩下的50%平均分给所有其它可行的路径上。
(i)停留的概率与出口的数目有关
(ii)总是以50%的概率停留
记录显示，设计者们决定用抛硬币的方式决定如何给他编写程序。正面向上意味着停留的概率由出口的数目动态地决定，而反面向上意味着莱昂哈德以固定的50%的概率停留在当前房间。不幸的是，抛掷硬币的结果并没有被记录，因此在缺乏更多信息的情况下，我们只能假设这两种选择以相同的概率被执行。
凯瑟琳表示，很容易计算得出，如果是5乘5的方形网格房间，那么经过充分长的时间后，在编号为平方数的房间中找到莱昂哈德的概率大约为0.177976190476（保留12位小数）。
为了证明你有获取这份神谕的价值，你必须计算出，如果莱昂哈德是在1000乘1000的方形网格中四处游荡，在编号为平方数的房间中找到他的概率。
（将你的答案保留12位小数）