Theoretically find the expected length of a game

Question

Given the following game:

There is a hider and a seeker, each game consists of the hider randomly selecting one of two places to hide that is $A$ with probability $p$ and $B$ with $1 - p$, and the seeker randomly chooses to search in $A$ with probability $q$ and $B$ with $1 - q$. If seeker finds hider then the game ends, else both randomly pick again. This continues each time both randomly picking where to hide and search until the seeker finds hider.

I want to know how to formulate the average number of game iterations to expect using theory...that is using $p$ and $q$, how can I express how long I should expect it to take for the seeker to find hider?

Answer 1

The probability that the game doesn't end in a particular round is $x = p(1 - q) + q(1 - p)$, so the probability that the game lasts for exactly $n$ rounds is $x^{n-1}(1 - x)$. This means that the expected length of a game is

$$\sum_{n \ge 1} n x^{n-1} (1 - x).$$

This sum can be found by various methods, depending on what you're comfortable with; for now I'll just say that the answer works out to be $\frac{1}{1 - x}$. In other words, it's the reciprocal of the probability that the game ends.

Answer 2

You can sometimes answer such questions using the idea of "conditioning". Students often prefer this method as there are no infinite sums to calculate.

Two things can happen on the first round of this game: either the seeker finds the hider (probability = $pq+(1-p)(1-q)$), or the game starts over (probability = $p+q-2pq$).

If $t$ is the average number of iterations that the game lasts, then averaging over these two scenarios gives $$t=(1)(pq+(1-p)(1-q))+(1+t)(p+q-2pq).$$

Solving for $t$ gives $t=1/(pq+(1-p)(1-q))$.