There are two ways to interpret the drunk salesman problem:
- The drunk salesman does not remember what doors he has already knocked on, and is equally likely to knock on any door on any knock.
- The drunk salesman does remember what doors he has knocked on, and will not knock on any door more than once.
The first problem is a straightforward application of Wald's theorem from martingale theory. The second one takes some interpretation to make sense of, but it's possible to give it a meaningful interpretation and solution.
The key observation is that the drunk salesman always knocks on the average door, every time.
The expected number of sales from a single knock is
$$ P = \sum_i Pr(Sale \mid Door =i) \times Pr(Door = i) = \frac{1}{N} \sum_i Pr(Sale \mid Door = i) $$
the average of the probabilities. The is the same as if was a single door whose probability of a sale is the average of the probabilities across all doors, and we model the drunk salesman as never moving, persistently knocking on the same average door again and again (a metaphor for addiction found in the unlikeliest of places).
To find the expected number of knocks before the number of sales first exceeds 3 we must introduce a stopping time. Let $S_i$ denote the number of sales the person makes for knock $i$, this is an i.i.d sequence of binary random variables with $Pr(S = 1) = P$. Then our stopping time of interest is:
$$ \tau = \min \{ i \mid \sum_i S_i \geq 3 \} $$
Wald's theorem for stopping times says that:
$$ E \left[ \sum_i^{\tau} S_i \right] = E[ \tau ] E[S] $$
The summation on the left is, by definition:
$$ E \left[ \sum_i^{\tau} S_i \right] = E[3] = 3 $$
And so the expected number of doors is:
$$ E[ \tau ] = \frac{3}{E[S]} = \frac{3}{P} $$
More difficult is the drunk salesman with memory, where the salesman remembers not to knock on the same door twice. In this case lets reason as follows: for the first knock, each door is equally likely, so the expected number of sales for the first knock is:
$$ E_1 = \frac{1}{N} \sum_i Pr(Sale \mid Door = i) $$
as before. Now for the second knock, one door has been removed, with each door equally likely to be the missing one. This means that the expected number of sales for the second knock is:
$$ \begin{align}
E_2 &= \sum_i E(Sale \mid Removed = i) \times Pr(Removed = i) \\
&= \frac{1}{N} \sum_i \frac{1}{N-1} \sum_{j \ne i} Pr(Sale \mid Door = j) \\
&= \frac{1}{N(N-1)} \sum_i \sum_{j \ne i} Pr(Sale \mid Door = j)
\end{align}
$$
In the double sum, each individual $Pr(Sale \mid Door = j)$ occurs $N-1$ times, so:
$$\begin{align}
E_2 &= \frac{1}{N(N-1)} (N-1) \sum_i Pr(Sale \mid Door = i) \\
&= \frac{1}{N} \sum_i Pr(Sale \mid Door = i)
\end{align}$$
Rather miraculously, the drunk-with-memory salesman has the same chance of making a sale at knock 2 as as knock 1. This pattern continues for all the knocks, so $S_i$ is again an i.i.d sequence (but a finite sequence this time) with $E[S] = P$.
The stopping time analysis of the previous case applies again, but with the added twist that our definition must be:
$$ \tau = \min \{ \min \{ i \mid \sum_i S_i \geq 3 \}, N \} $$
that is, once all the doors are exhausted, the salesman must stop.
This affects the left hand side of Wald's theorem, which becomes:
$$ E \left[ \sum_i^{\tau} S_i \right] = 3 Pr \left[ \sum_i^{N} S_i \geq 3 \right] + 2 Pr \left[ \sum_i^{N} S_i = 2 \right] + Pr \left[ \sum_i^{N} S_i = 1 \right] $$
These are all multinomial probabilities, and can be calculated in terms of $P$. Once you have this value, Wald's theorem works as before.
