# The Coffee Shop Game

### Problem

### Solution 1

We assume that the arrivals at the cafe follow the Poisson distribution, i.e., that the probability of $k$ arrivals in the interval $[t,s]$ is given by

$P(k\text{ arrivals in }(t, t + s]) = (\lambda s)^k e^{-\lambda s}/k!,$

where $\lambda s$ is the mean number of arrivals in $(t, t + s].$ Let $A$ represent the event that you win, and note that $A$ occurs if there is exactly one arrival in the time interval $(t, 1].$ Now the number of arrivals in the interval $(t, 1]$ has a Poisson distribution with mean $\lambda(1-t).$ Therefore, with $k = 1,$ $s = 1-t$,

$\displaystyle P(A)=\frac{\lambda(1-t)e^{-\lambda(1-t)}}{1!}.$

Your objective is to select $t$ to maximize $P(A).$ To this end, set $f(t) = \lambda(1-t)e^{-\lambda(1-t)},$ differentiate with respect to $t$ to obtain

$\displaystyle f'(t)=\lambda e^{-\lambda(1-t)}(\lambda(1-t)-1),$

and then set $f'(t)$ equal to zero. We find that $P(A)$ is maximized with $t = 1-\frac{1}{\lambda}.$ Substitution then yields the maximum probability of winning the game using this strategy, namely

$\displaystyle P(A)=\frac{\lambda(1-(1-\frac{1}{\lambda}))e^{-\lambda(1-(1-\frac{1}{\lambda}))}}{1!}=\frac{1}{e}.$

### Solution 2

Assume that we have $n$ periods each of length $\Delta t$, $n\equiv \frac{t}{\Delta t}$, such that only one single event happens over $\Delta t$, with probability $p$. We assume independence, so the probability mass function $\phi (x,t)$:

$\displaystyle\phi (x,t)= \begin{cases} p^x {t/\Delta t\choose x} (1-p)^{t/\Delta t-x} & 0\leq x\leq \frac{t}{\Delta t} \\ 0 & \text{otherwise} \end{cases}$

We need to maximize the probability $\phi(1,t)$ with respect to $t$ -- the probability that the best stopping time strategy (not necessarily specified) can yield. Solving for

$\displaystyle\phi (1,t)_t=\frac{p (1-p)^{\frac{t}{\text{$\Delta $t}}-1} (\text{$\Delta $t}+t \log (1-p))}{\text{$\Delta $t}^2}=0,$

we $\displaystyle t^*=\frac{\text{$\Delta $t}}{\log (1-p)}$, so

$\displaystyle\Phi \left(x,t^*\right)=\frac{p}{e\cdot (p-1) \log (1-p)}.$

Making $\Delta t$ infinitesimal is equivalent to making $p$ so as well.

$\displaystyle\frac{1}{e}\cdot\underset{p\to 0}{\text{lim}}\frac{p}{(p-1) \log (1-p)}=\frac{1}{e}$

### Solution 3

Let $\lambda$ be the rate of arrivals. Probability that exactly one person enters after time $t$ is

$P(\lambda;t)=\exp\left[-\lambda (1-t)\right]\left[\lambda(1-t)\right].$

Estimate $\lambda$ by averaging over some finite interval initially, and then choose $t$ that gives maximum $P(\lambda;t)$. Substituting $x=\lambda(1-t)$, the probability of winning is the maximum value of the function $xe^{-x}$. Setting the derivative of the logarithm of the function to $0$,

$\displaystyle\frac{1}{x_{ideal}} - 1 = 0; ~ x_{ideal} = 1.$

Thus, the probability of winning is $e^{-1}$.

### Remark

It is remarkable that the probability of winning the game does not depend on the rate of arrivals, i.e., on the constant $\lambda.$ This becomes obvious if you notice that the various functions metamorphose one into another by a change of variables. Here's a graphic support

The same is true for a slight modification of the problem wherein you have to guess the penultimate arrival. In this case, $\displaystyle t=1-\frac{2}{\lambda}$ and the probability of winning is $e^{-2}.$

### Acknowledgment

This problem comes from an article __Probability $1/e$__ by Reginald Koo and Martin L. Jones (*The College Mathematics Journal*, VOL. 42, NO. 1, 2011). The authors credit the exercise 2.9 from Stochastic Processes by S. Ross (Wiley, New York, 1996.)

Solution 2 is by N. N. Taleb who remarked that $1/e$ doesn't come from Poisson but from memorylessness; because it is memoriless, probability is independent of time. Solution 3 is by Amit Itagi.

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny