I am trying to solve the following problem: Given a 8x8 board where each square has one robot on it, define a move as follows: every robot moves either up, down, left, or right (each with an equal probability), such that they do not move outside of the board and such that multiple robots are allowed on each square. After K moves (1 <= K <= 100), find the expected number of empty squares. (For reference, this is the exact problem).
My idea to solve this was Dynamic Programming; let prob[k][r][c] = P(there is at least one robot on the square in row r and column c after exactly k moves). Our base case is prob[0][1..8][1..8] = 1, since each square starts out with one robot. Then, I tested having prob[k+1][r_f][c_f] = sum of prob[k][all r, c that are one move away from the current square] / [number of valid moves from r, c] as the transitions, but it turns out that was wrong.
Right now, I don't know how to proceed on this problem, so could someone explain a solution to it? Is my approach somewhat correct, or am I making some basic mistake in my logic?
I think this is right:
The expected number of empty squares (after k steps) is the sum of the contribution of square 1 to be empty (which is 1) times the probability of square 1 to be empty (after k steps), plus the contribution of square 2 to be empty (which is 1) times the probability of square 2 to be empty (after k steps), etc. ... and so it is just the sum of the probabilities of each square to be empty (after k steps).
OK, so now you have to find the probability that a specific square is empty after k steps. My method would be to just keep track of all 64 robots and for each robot, figure out probability that it is in a certain square after k moves. And that can easily be done iteratively: you know where the robot is after 0 steps, and if you know the probability distribution after k-1 steps, you can easily compute the probability distribution for k steps.
Finally, if you do this for all robots, you can calculate, for each square, the probability no robot is in it after k moves.
You might obtain some speed-up by exploiting the symmetry of the board.