Can You Get A Haircut Already?

A FiveThirtyEight Riddler puzzle.

By Vamshi Jandhyala in Riddler mathematics

February 28, 2020

Problem

At your local barbershop, there are always four barbers working simultaneously. Each haircut takes exactly 15 minutes, and there’s almost always one or more customers waiting their turn on a first-come, first-served basis.

Being a regular, you prefer to get your hair cut by the owner, Tiffany. If one of the other three chairs opens up, and it’s your turn, you’ll say, “No thanks, I’m waiting for Tiffany.” The person behind you in line will then be offered the open chair, and you’ll remain at the front of the line until Tiffany is available.

Unfortunately, you’re not alone in requesting Tiffany — a quarter of the other customers will hold out for Tiffany, while no one will hold out for any of the other barbers.

One Friday morning, you arrive at the barber shop to see that all four barbers are cutting hair, and there is one customer waiting. You have no idea how far along any of the barbers is in their haircuts, and you don’t know whether or not the customer in line will hold out for Tiffany.

What is the expected wait time for getting a haircut from Tiffany?

Solution

Let $T$ be the random variable of the remaining time for haircut being done by Tiffany.

Let $B_i$ be the random variable of the remaining time for haircut being done by Barber $i$, for $i=1,2,3$.

Let $C_T$ be the indicator random variable which takes the value $1$ if the waiting customer holds out for Tiffany and $0$ otherwise.

We have,

$$ \begin{eqnarray*} T &\sim& \mathcal{U}(0,15) \
B_i &\sim& \mathcal{U}(0,15), i = 1,2,3 \
\mathbb{P}[C_T = 1] = \frac{1}{4} &,& \mathbb{P}[C_T = 0] = \frac{3}{4} \end{eqnarray*} $$

Let $Y$ be the random variable of the waiting time for Tiffany when there is one customer waiting.

We have,

$$ \begin{equation} \label{rv_wait_time} Y = \begin{cases} 15 + T & C_T = 1 \
15 + T & C_T = 0, T < \min(B_1, B_2, B_3) \
T & C_T = 0, T \geq \min(B_1, B_2, B_3) \end{cases} \end{equation} $$

The expected wait time for getting a haircut from Tiffany, $\mathbb{E}[Y]$ is given by

$$ \begin{equation} \label{exp_wait_time} \mathbb{P}[C_T = 1]\cdot\mathbb{E}[Y | C_T = 1] + \
\mathbb{P}[C_T = 0]\cdot\mathbb{E}[Y | C_T = 0] \
= \frac{1}{4}(15 + \mathbb{E}[T]) + \frac{3}{4} \mathbb{E}[Y | C_T=0] \end{equation} $$

As $T \sim \mathcal{U}(0,15)$,

$$ \begin{equation} \label{exp_uni_rv} \mathbb{E}[T] = \frac{0 + 15}{2} = 7.5 \end{equation} $$

To calculate $\mathbb{E}[Y \vert C_T=0]$, we need the distribution function of $B=\min(B_1, B_2,B_3)$.

By definition,

$$ \begin{equation} \label{dist_B} F_B(x)=\mathbb{P}[B \leq x] = 1 - \mathbb{P}[B>x] \
= 1 - \mathbb{P}[\min(B_1,B_2,B_3) > x] \end{equation} $$

From \ref{rv_wait_time} and \ref{dist_B} we get,

$$ \begin{equation} \label{cond_exp_y_t} \mathbb{E}[Y | T, C_T=0] = (15+T)(1-F_B(T)) + \
T \cdot F_B(T) \
= 15(1-F_B(T)) + T \end{equation} $$

Using Symmetry

An elegant way of calculating $\mathbb{E}[Y \vert C_T=0]$ from \ref{cond_exp_y_t} without deriving $F_B$ explicitly is as follows,

$$ \begin{equation} \label{cond_exp_y_t_eleg} \mathbb{E}[Y \vert C_T=0] = \mathbb{E}[\mathbb{E}[Y \vert T, C_T=0]] \
= \mathbb{E}[15(1-F_B(T))] + \mathbb{E}[T] \
= 15\cdot \frac{1}{4} + 7.5 = 11.25 \end{equation} $$

The quantity $\mathbb{E}[1-F_B(T)]$ can be interpreted as the average probability of $T$ being the minimum of $T, B_1, B_2$ and $B_3$, which by symmetry is $\frac{1}{4}$.

Derivation of $F_B$

To derive $F_B$ we need to first calculate $\mathbb{P}[\min(B_1,B_2,B_3) > x]$.

Of course, $min(B_1,B_2,B_3)>x$ exactly when $B_i>x$ for $i=1,2$ and $3$.

Since these variables are i.i.d., we have

$$ \begin{align*} \mathbb{P}[\min(B_1,B_2,B_3) > x] &= \mathbb{P}[B_1>x] \cdot \mathbb{P}[B_2>x] \cdot \mathbb{P}[B_3>x] \
&= \mathbb{P}(B_1>x)^3 \end{align*} $$

As the $B_i$ are uniformly distributed on $(0,15)$, this yields

$$ \begin{equation} \label{min_uniform_iid} F_B(x) = \left{ \begin{array}{ll} 1 - \left(\frac{15-x}{15}\right)^3 & x \in (0, 15)\
0 & x < 0\
1 & y > 15 \end{array} \right. \end{equation} $$

From \ref{min_uniform_iid} and \ref{cond_exp_y_t} we get,

$$ \begin{equation} \label{cond_exp_y_t_1} \mathbb{E}[Y | T, C_T=0] = 15\left( \frac{15-T}{15} \right) ^3 + T
\end{equation} $$

From \ref{cond_exp_y_t_1} we get,

$$ \begin{equation} \label{cond_exp_y} \mathbb{E}[Y | C_T=0] = \int_0^{15} f_T(t) \left(15\left( \frac{15-t}{15} \right) ^3 + t\right) dt \
= \int_0^{15} \frac{1}{15} \left(15\left( \frac{15-t}{15} \right) ^3 + t \right ) dt \
= 11.25 \end{equation} $$

where $f_T(t) = \frac{1}{15}$ is the density function of $T$.

Calculating $\mathbb{E}[Y]$

From \ref{exp_wait_time}, \ref{exp_uni_rv} and \ref{cond_exp_y_t_eleg} (or \ref{cond_exp_y}) and we get,

$$ \begin{equation*} \mathbb{E}[Y] = \frac{1}{4}(15+\mathbb{E}[T]) + \frac{3}{4} \mathbb{E}[Y | C_T=0] \
= \frac{1}{4} \cdot 22.5 + \frac{3}{4} \cdot 11.25 = 14.0625 \end{equation*} $$

Therefore the expected wait time for getting a haircut from Tiffany is 14.0625 mins.

Monte Carlo Simulation

from random import random, uniform

runs = 1000000
total_wait_time = 0
for _ in range(runs):
    t, b1, b2, b3 = [uniform(0, 15) for _ in range(4)]
    if random() <= 0.25:
        wait_time = 15 + t
    else:
        if t < min(b1, b2, b3):
            wait_time = 15 + t
        else:
            wait_time = t
    total_wait_time += wait_time
print("Average wait time: ", total_wait_time/runs)