Python x Math: Find the expected number of moves of a rock to move from one corner to another

Question

Python code problem in related to a statistical math problem

Question

A rock is placed on the bottom-left cell of a 8x8 chessboard. On each second, the rock will randomly move to a cell that it can move to, with equal probability. Find the expected number of moves until it first visits the top-right cell.

Issue

I have found this question and the author suggested a math solution to calculate the expected number of moves, but my python code fail to calculate the same answer. The suggested answer is 70, but my code result is around 30. I am assuming there is some logical error in my code

Code

import math
import random

def main():
    board_size = 8
    iterations = 1000000
    Test(board_size, iterations)

# returns a new position after moving in the given direction for the given number of steps
def Move(pos, direction, steps):
    if direction == "U":
        return (pos[0], pos[1] + steps)
    elif direction == "D":
        return (pos[0], pos[1] - steps)
    elif direction == "L":
        return (pos[0] - steps, pos[1])
    elif direction == "R":
        return (pos[0] + steps, pos[1])
    
# returns a new position after moving in a random direction for a random number of steps
def RandomMove(pos, board_size):
    direction = random.choice(GetPossibleDirections(pos, board_size))
    steps = GetSteps(direction, pos, board_size)
    return Move(pos, direction, steps)

# returns a list of possible directions to move in
def GetPossibleDirections(pos, board_size):
    result = ["U", "D", "L", "R"]
    if pos[0] == 0:
        result.remove("L")
    elif pos[0] == board_size - 1:
        result.remove("R")
    if pos[1] == 0:
        result.remove("D")
    elif pos[1] == board_size - 1:
        result.remove("U")
    return result

# returns the number of steps to move in the given direction
def GetSteps(direction, pos, board_size):
    if direction == "U":
        return math.floor(random.random() * (board_size - pos[1] - 1) + 1)
    elif direction == "D":
        return math.floor(random.random() * (pos[1]) + 1)
    elif direction == "L":
        return math.floor(random.random() * (pos[0]) + 1)
    elif direction == "R":
        return math.floor(random.random() * (board_size - pos[0] - 1) + 1)

# returns the number of steps it takes to reach the top-right cell from the bottom-left cell
def Simulate(pos, board_size):
    steps = 0
    while pos != (board_size - 1, board_size - 1):
        pos = RandomMove(pos, board_size)
        steps += 1
    return steps

# runs a simulation of the given number of games on a board of the given size
def Test(board_size, iterations):
    print("Simulating", iterations, "games on a", board_size, "x", board_size, "board...")
    total_steps = 0
    for i in range(iterations):
        total_steps += Simulate((0, 0), board_size)
        progress_bar(i + 1, iterations)
    print("Average number of moves:", total_steps / iterations)

def progress_bar(current, total, bar_length=20):
    fraction = current / total
    arrow = int(fraction * bar_length - 1) * '-' + '>'
    padding = int(bar_length - len(arrow)) * ' '
    ending = '\n' if current == total else '\r'
    print(f'Progress: [{arrow}{padding}] {int(fraction*100)}%', end=ending)

if __name__ == "__main__":
    main()

Try here: OnlineGDB

For those who are interested in the math solution:

We use first-step analysis to find the answer. Let the number of moves to reach the end cell from the row and column touching the end cell be y, and the rest be x.
we have:

x = (12/14)(x+1) + (2/14)(y+1)  
y = ( 7/14)(x+1) + (6/14)(y+1) + (1/14)  

Noted that x is the answer. Hence, for a 8x8 chessboard, the answer is 70

A 3x3 chessboard illustration:

x = (2/4)(x+1) + (2/4)(y+1)  
y = (2/4)(x+1) + (1/4)(y+1) + (1/4)

x = 10

3x3 example	3x3 example	3x3 example
y	y	end cell
x	x	y
x	x	y

I wrote the python code and tested. The result is around 30. Please let me know if there is anything wrong with my code or the suggested answer(70) is not correct.

If the suggested answer is not correct, you can also try to find out what is wrong with the method. Thanks!

Answer 1

I found the problem, haha
It is my code logic problem. I randomly choose a direction first and then randomly choose the number of steps. But these two events are not independent to each other, hence I cannot do so.

The correct approach is to find the possible cells, instead of direction and steps.

Here is my updated code and feel free to try.
https://www.onlinegdb.com/6F1gHKw6I

import math
import random

def main():
    boardSize = int(input("Enter board size: "))
    iterations = int(input("Enter number of iterations: "))
    startPos = (0,0)
    endPos = (boardSize - 1, boardSize - 1)
    Test(boardSize, iterations, startPos, endPos)

# returns a new position after moving in a random direction for a random number of steps
def RandomMove(pos, boardSize):
    possible_cells = [] # For 3x3 board, if at (0,0) , then it is [(0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1)]
    for i in range(0, boardSize):
        if (i, pos[1]) != pos:
            possible_cells.append((i, pos[1]))
        if (pos[0], i) != pos:
            possible_cells.append((pos[0], i))
    newPos = random.choice(possible_cells)
    return newPos

# returns the number of steps it takes to reach the top-right cell from the bottom-left cell
def Simulate(boardSize, startPos, endPos):
    pos = startPos
    steps = 0
    while pos != endPos:
        pos = RandomMove(pos, boardSize)
        steps += 1
    return steps

# runs a simulation of the given number of games on a board of the given size
def Test(boardSize, iterations, startPos, endPos):
    print("Simulating", iterations, "games on a", boardSize, "x", boardSize, "board...")
    total_steps = 0
    for i in range(iterations):
        total_steps += Simulate(boardSize, startPos, endPos)
        progress_bar(i + 1, iterations)
    print("Average number of moves:", total_steps / iterations)

def progress_bar(current, total, bar_length=20):
    fraction = current / total
    arrow = int(fraction * bar_length - 1) * '-' + '>'
    padding = int(bar_length - len(arrow)) * ' '
    ending = '\n' if current == total else '\r'
    print(f'Progress: [{arrow}{padding}] {int(fraction*100)}%', end=ending)

if __name__ == "__main__":
    main()