4
$\begingroup$

Imagine a salesman assigned to a neighborhood, each home has a unique and independent conversion rate associated with it that we might model like

 N = [.3, .2, .5, .1, .1, .1, .1, .5, .4]

There are two versions of this problem :

  1. The salesman gets drunk before going selling and knocks on doors randomly, rather than in any particular order.
  2. The salesman is very astute and knocks on doors from most likely to least likely

How many doors does he need to knock, on average, before he makes 3 sales?

$\endgroup$
  • $\begingroup$ How do you deal with the case when he knocks on all doors and makes only 0, 1, or 2 sales? $\endgroup$ – Adrian May 23 '15 at 21:24
  • $\begingroup$ I would think that would be a rare case. The average number is the value I'm going for here (the expected value) - if all of the homes had the same conversion rate of .1, the number of doors I would need to knock would be 30 -- but this isn't so easy to calculate when the conversion rates vary. $\endgroup$ – Robert May 23 '15 at 21:52
  • $\begingroup$ Are you thinking of a finite number of homes, or of an infinite population of homes? The N = ... in your post looks like a short, finite list. $\endgroup$ – Adrian May 23 '15 at 22:24
  • $\begingroup$ A finite number of homes with a known list of conversion rates. $\endgroup$ – Robert May 24 '15 at 1:09
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is an exceptional answer. Would you be able to unpack the final equation into an example using an example "neighborhood" of doors? $\endgroup$ – Robert May 24 '15 at 3:33
  • $\begingroup$ @Robert Thanks. I think I can handle the last one, but still thinking about it! $\endgroup$ – Matthew Drury May 24 '15 at 3:50
  • $\begingroup$ Just want to point out that, for case 2, your definition of waiting time can give strange results in edge cases. To take an extreme example, suppose we have N=2 doors and are asking how long it takes to get 3 sales (which is impossible). Your definition will give a waiting time of 2, right? $\endgroup$ – Adrian May 24 '15 at 11:02
  • $\begingroup$ Yah, I suppose mine is, how long until he can stop knocking on doors. $\endgroup$ – Matthew Drury May 24 '15 at 14:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.