Four players $\{N,E,S,W\}$ repeatedly play a game. The probability of each player winning each game is fixed, say $\{p_N,p_E,p_S,p_W\}$ repectively. They keep score by placing a counter on a square lattice as follows:

Each time $N$ wins, the counter moves one place to the North. Similar for East, South and West. Thus North and South are enemies, as are East and West.

Victory for the overall match is achieved when the counter reaches a distance $D$ from its original position in any one of the four directions.

Find an expression for the probability that $N$ wins. [Note that this is clearly symmetrical, so it suffices to find the expression for any one of the players]


The recursive method for solving the standard 2-player gambler's ruin will not work, or at the very least is difficult as the ruin probability for $S$ will have to be calculated conditional on either of $E$ or $W$ going bust before she does.

As the victory conditions are symmetric we can attempt to apply reflective symmetry to the victory paths. This is an effective way of solving the 2-player gambler's ruin as follows (just using $N$ and $S$):

Each path leading to $N$'s victory has a unique reflection which leads to $S$'s victory. Each reflective pair have a probability ratio $({p_N\over p_S})^D$, and so

$$ Pr(N \text{ wins}) = {p_N^D\over p_N^D + p_S^D} $$

Applying the same principle to the 4-player problem, we can reflect for $\{N,S\}$ while keeping $\{E,W\}$ moves unaltered. From this we obtain

$$ {Pr(N \text{ wins})\over Pr(S \text{ wins})} = \left({p_N\over p_S}\right)^D $$ and similarly for $\{E,W\}$.

I can't find a symmetry (reflective or rotational) that allows me to compare $N$ with $E$ or $W$. Indeed this may not be a fruitful approach.

All ideas welcome!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.