On Board Games, Small Worlds and Wald's Equation

Consider a simple board game played on a board with n+1 spaces, numbered 0,1,...,n (from left to right). Fix a weighted die with n faces 1,...,n. Choose one of the spaces uniformly at random and place a token on it. Roll the die. If the die shows value i, move the token by i spaces towards the left, as long as it does not fall off the board. More precisely, if the token's position is t, then the token moves to position t'=t-i if t>=i, and otherwise stays put. Repeat, until the token reaches the left end of the board (space 0).

We would like to find a weighting of the die that allows us to move the token to space 0 with as few die rolls as possible (on average). Note that dice cannot be switched once the game has started.

In this talk I will explain the (asymptotically) optimal weighting of the die, why there is no better weighting, how this is related to the Small World Phenomenon, why (some) computer scientists care, and what all this has to do with Wald's Equation.