The Coffee Shop Game


The Coffee Shop Games, 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}$.


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

maximum probability in Poisson processes is always the same

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


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