Problem 575

[LarryBlake]

Two questions:
1. Did Leonhard start in a particular room (for example, room 1)?
2. If Leonhard's program says stay in a room, does he stay forever?

[Animus]

Two questions:
1. Did Leonhard start in a particular room (for example, room 1)?
2. If Leonhard's program says stay in a room, does he stay forever?

1. Since he has been wandering around almost forever, it should not influence the answer, especially since
2. No, if he choses to stay he will remake his decision after some time (which is the same wether he stayed in a room or moved on into another), and will leave the room with the same given probabilities of his programming.

[LarryBlake]

Thanks. So that means that I'm looking for the probability that:
A. His wandering led him to a square numbered room (1, 4, 9, 16, etc.) and
B. The program said stay there (for now).

Right?

[hk]

No.
The problem asks you to calculate the probability Leonhard will be in a square numbered room the moment you are looking for him.
That's it.
Please note that the space vessel has been moving around for almost eternity.

[LarryBlake]

Let's say that when the program determines Leonhard should stay in a room, he stays for X minutes. Let's also say that when I'm looking, he's stopped somewhere, spending his X minutes.

If he arrives in a room, does he immediately check if he should wander further? If so, he could do something like "move, move, move, stop for X minutes".

That's what I meant. Is that consistent with what you just said?

[v6ph1]

The decision stay in a room holds as long as it takes to change the room.
So each decision is taken a specific amount of time later than the previous. It doesn't matter whether this time is a millennium or a nano second.

[LarryBlake]

In my example "move, move, move, stop for X minutes", could he be anywhere except where he stopped? I agree that the stop duration doesn't matter.

[v6ph1]

Just take a simple discrete model:
After each time step a move or stay happens.
After the next step, a new decision is necessary.

[LarryBlake]

I think I have it now.

Let's say Leonhard is in room 42. That could be because one "turn" ago he was in room 1042 (or 41 or 43) and moved, or he was in 42 and didn't move.

Is that right?

[hk]

if he is found in a certain room,say x, one turn ago he could have been in one of the neighbours of that room or in room x too,yes.

[pred]

The wording of this one had me confused for a good while.

At first, I thought that the engineers, at design-time, had it set up so that the robot followed either the first or the second algorithm (but without noting which one it was), and that the idea was that you would use the case of n = 5 to figure out which one of the two it were. That turns out not to be the case.

At second, I thought that the engineers had it set up so that the robot itself chose randomly between the two algorithms at each time-step. That also turns out not to be the case.

That is, the probability that comes out of it at the end will never reflect the actual behaviour of the robot, which is fair enough as far as the exercise is concerned, but it did take some playing around with the numbers to figure out what was going on.

To ensure that I was not just going crazy, I gave the instruction to one other individual who independently reproduced the first interpretation above.

[tsnguyen]

I am also confused by this problem. So when does the act of "flipping a coin" happen? Does it happen whenever the robot decides to move (option i and ii are chosen with equal probability at each and every step), or does it happen when the designers program the robot (either option i or ii is chosen once and for all at the beginning)? Or it is something else that I am supposed to figure out?

Thanks

[hk]

The flipping of the coin happens before building the robot.

[sfrimann]

I am a little confused after reading these posts

At first, I thought that the engineers, at design-time, had it set up so that the robot followed either the first or the second algorithm (but without noting which one it was), and that the idea was that you would use the case of n = 5 to figure out which one of the two it were. That turns out not to be the case.

This is my exact interpretation of the problem as well, and I cannot see how the problem can be interpreted any other way. If this is the wrong interpretation can someone please clarify what the correct interpretation is?

[Animus]

You are expected to take both possibilities into account with equal probability. The test case given is therefore the mean value of the expected values of both possibilities.

[vamsikal3]

<deleted post>

[hk]

I am able to get the same answer as the example provided in the problem for a 5 x 5 square grid. Hopefully, I am not giving anything away, but, I had to write a sparse matrix gaussian elimination solver to get the answer. Unfortunately, my sparse matrix solver doesn't scale to a 1000 x 1000 grid. Is it possible to solve this problem without gaussian elimination on a sparse 10^6 x 10^6 matrix.

Yes, it is.

[vlad_tepesch]

You are expected to take both possibilities into account with equal probability. The test case given is therefore the mean value of the expected values of both possibilities.

but exactly this does not make any sense. Obviously the designer implemented it one or the other way and the robot follows this or the other way. the n=5 testcase could help to reveal which implementation the robot has but it is impossible that he is in the superposition that the test case suggest he is.

The other variant that the robot itself chooses randomly at each turn (this is the way I understood first it because of uncareful reading) would just influence the given per-turn probabilites by averaging them. But the testcase does not fit.