how do i theoretically find the expected length of the following game?

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 choses to search in A with probability q and B with 1 - q. If seeker finds hider then game ends, else both randomly pick again. This continues each time both randomly picking where to hide and search, until 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 seeker to find hider?

-

2 Answers

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))$.

-

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.

-
how would you find the sdum – stuart Oct 30 '10 at 19:57
how would you find the sum in question? – stuart Oct 30 '10 at 19:57
@stuart: there are a couple of different ways. There is a combinatorial proof that sum nx^{n-1} = 1/(1 - x)^2: the latter is (1 + x + x^2 + ...)^2, and there are n ways to get two numbers between 0 and n to sum to n-1. You can also start with sum x^n = 1/(1 - x) and take the derivative of both sides with respect to x, then multiply by (1 - x). Finally, you can factor out (1 - x) and regroup the terms like (1 + x + x^2 + ...) + (x + x^2 + x^3 + ...) + ... and so on, and sum each individual geometric series, then sum their sums. (This is a disguised version of the combinatorial proof.) – Qiaochu Yuan Oct 30 '10 at 20:16