On an 8×8 chessboard, we choose two random squares S and C. We have a peg that is allowed to move always by 1 square horizontally or vertically in each move. What is the expected number of moves, when starting at S and going to C, when we always follow the shortest path possible? What is the graph describing this problem?
I created a program to evaluate the expected number of moves so I get 4 but I don't know how to prove it and describe with a graph. A hint will be great for me.
The graph of the question is simply the 8×8 grid graph, but it will matter nothing for the derivation that follows.
I am going to follow the approach outlined in the comments. Assuming first that S and C may be the same, the average Manhattan (shortest) distance between them is the sum of the average distance between their ranks and the average distance between their files, which by symmetry may be taken to be twice the average distance between their ranks.
With probability $\frac18$, the two endpoints have the same rank. With probability $\frac7{32}$, they are one rank apart, with probability $\frac3{16}$ two ranks and so on. The expected number of ranks separating them works out as $$0\cdot\frac8{64}+\sum_{n=1}^7n\cdot\frac{2n}{64}=\frac{21}8$$ Then the average Manhattan distance between S and C is $\frac{21}4=5.25$.
If S may not equal C, the 64 forbidden configurations contribute nothing to the total Manhattan distance across all configurations. Since there are $64^2$ configurations in all, the average distance becomes $$\frac{21}4\cdot\frac{64^2}{64^2-64}=\frac{16}3=5.333\dots$$