• This (zero-player) game is an example of a Markov chain.
• For background, see Grinstead and Snell, Ch. 11.
• Three solution approaches:
  1. Compute expected values via system of equations
  2. Compute absorption probabilities
  3. Simulate Markov chain for finite number of steps

Approach 1

• Let ~E_i~ denote the expected payout if the ball is currently at hole ~i~, and let ~c_i~ denote the payout for dropping into hole ~i~. Then: $$\displaystyle E_i = p_4 c_i + p_0 E_a + p_1 E_b + p_2 E_c + p_3 E_d$$ where ~a, b, c, d~ are the neighbors of hole ~i~.
• If ~H = N(N+1)/2~ is the number of holes, this gives a system of ~H~ linear equations in ~H~ variables, which can be solved using Gaussian elimination in ~\mathcal O(H^3)~.
• The input constraints imply that the system is consistent and has a unique solution.
• Can be derived without knowing Markov chain theory.

Approach 2

• Uses Markov chain theory directly.
• Model each hole as a transient state, model falling into a hole as an absorbing state. Have ~H = N(N+1)/2~ transient and ~H~ absorbing states.
• Build ~H \times H~ transition matrix ~\mathbf Q~, use Gaussian elimination to compute fundamental matrix ~\mathbf N = (\mathbf I-\mathbf Q)^{-1}~.
• Compute absorption probabilities ~\mathbf B = \mathbf N \mathbf R~ where ~\mathbf R~ is the ~H \times H~ diagonal matrix ~\mathbf R_{i,j}~ of being absorbed (falling into the hole) ~j~ when hovering over hole ~i~.
• Compute expected value as dot product of first row of ~\mathbf B~ with expected payout. (Optimize to compute only first row of ~\mathbf B~.)

Approach 3

• Keep track of probability of being over hole ~i~ after ~k~ steps: vector of ~p_{k,i}~ elements.
• For all ~i~, compute ~p_{k+1,i}~ from ~p_{k,i}~ by simulating the next event of ball bouncing from hole ~i~ to possible neighbors.
• Compute contribution to expected payout based on probability of falling into hole ~i~ at step ~k~.
• Stop when probability of not having been absorbed is small enough.
• Caveat: if probabilities of falling into holes are very small, this could take many iterations: exploit problem constraint that the probability of not having been absorbed drops below threshold.
• Mathematically equivalent to computing first row of ~\mathbf N \mathbf R = (\mathbf I-\mathbf Q)^{-1} \mathbf R = (\mathbf I + \mathbf Q + \mathbf Q^2 + \dots) \mathbf R~ — but will time out if done using dense matrix!