Hilbert's Barber Shop

Question

Hilbert opens a barber shop with an infinite number of chairs and an infinite number of barbers. Customers arrive via a Poisson random process with an expected 1 person every 10 minutes. Upon arrival, they sit in the first unoccupied chair and their haircut begins immediately. The haircut lasts 15 minutes, after which the person leaves. A long time after the barber shop has opened, what is the probability that the third chair is occupied?

Answer 1

The probability of any chair being occupied can be calculated exactly and, for the third chair as asked for in the question, it comes to $513/1943=0.26402\ldots$. More generally, let $\lambda$ be the rate at which customers arrive multiplied by the time taken for a haircut. So, here, we have $\lambda=(10{\rm mins})^{-1}(15{\rm mins})=3/2$. Then, after a long time, the probability that the $n$th chair is occupied is $$ \begin{align} p_n=\frac{\lambda^n}{(n-1)!}\left(\sum_{k=0}^{n-1}\frac{\lambda^k}{k!}\right)^{-1}-\frac{\lambda^{n+1}}{n!}\left(\sum_{k=0}^n\frac{\lambda^k}{k!}\right)^{-1}. &&{\rm(1)} \end{align} $$ Plugging in $\lambda=3/2$ and $n=3$ gives the result $p_3=513/1943$.

To prove (1), lets start by scaling time so that a haircut takes 1 unit of time. Then, customers arrive according to a Poisson process of rate $\lambda$. Fixing an integer $n\ge1$, I'll concentrate on the number of seats out of the first $n$ which are occupied at any time. For $0\le i\le n$, let $p_{i,n}$ be the probability that $i$ of the first $n$ seats are occupied after a long time. Also, for $0\le t_1\le\cdots\le t_i\le1$, I'll use $q_{i,n}(t_1,\cdots,t_i)$ for the probability density of having $i$ customers who have taken times $t_1,\ldots,t_i$ so far on their haircuts when sorted into increasing order. That is, the probability of having $i$ of the first $n$ chairs occupied at the given time, with customers who have been there for times in the ranges $(t_1,t_1+\delta t_1)$,..., $(t_i,t_i+\delta t_i)$ is $q_{i,n}(t_1,\ldots,t_i)\delta t_1\cdots\delta t_i$ with an error of size $o(\delta t_1\cdots\delta t_i)$.

If no customers were arriving or leaving then all that would be happening is that their times would be progressing, so $q_{i,n}$ increases at rate $\frac{d}{ds}q_{i,n}(t_1-s,\cdots,t_i-s)\vert_{s=0}$. In particular, if all of the first $n$ chairs are occupied then no new customers will occupy them, and no customer leaves until $t_1=0$. So, if we are in a steady state where the probability densities are not changing in time then, $$ \begin{align} \frac{d}{ds}q_{n,n}(t_1-s,\cdots,t_n-s)\vert_{s=0}=0. &&{\rm(2)} \end{align} $$ For $1\le i\lt n$ then the number of customers changes whenever a new one arrives, which occurs at rate $\lambda$. We also arrive at the state with $i$ chairs filled from the state with $i+1$ filled when a customer has been there for one unit of time and leaves. Setting the rate of change of $q_{i,n}$ to zero gives $$ \begin{align} \frac{d}{ds}q_{i,n}(t_1-s,\cdots,t_i-s)\vert_{s=0}-\lambda q_{i,n}(t_1,\ldots,t_i)+q_{i+1,n}(t_1,\ldots,t_i,1)=0 &&{\rm(3)} \end{align} $$ for $1\le i\lt n$. We can also arrive at a state with $i$ seats filled by there being $i-1$ seats filled and a new customer arriving, which happens at rate $\lambda$. This gives the boundary condition $$ \begin{align} q_{i,n}(0,t_1,\ldots,t_{i-1}) = \lambda q_{i-1,n}(t_1,\ldots,t_{i-1}). &&{\rm(4)} \end{align} $$ To find the steady state, we need to solve the differential equation given by (2),(3),(4). However, there is a very simple solution. By inspection, you can see that they are solved by $q_{i,n}(t_1,\ldots,t_i)=c\lambda^i$ where $c$ is a constant (independent of $i$, but it can depend on $n$). It does not depend at all on the times $t_1,\ldots,t_i$ that the customers have been sat! Integrating over the probability densities gives the probability of $i$ of the first $n$ seats being occupied, $$ p_{i,n}=\idotsint\limits_{0\le t_1\lt\cdots\lt t_i\le1}c\lambda^i\,dt_1\cdots dt_i=c\frac{\lambda^i}{i!}. $$ As probabilities must sum to one, putting in $\sum_{i=0}^np_{i,n}=1$ gives the value of $c$ as $1/\sum_{i=0}^n\lambda^i/i!$. So, $$ \begin{align} p_{i,n}=\frac{\lambda^i}{i!}\left(\sum_{k=0}^n\frac{\lambda^k}{k!}\right)^{-1}. &&{\rm(5)} \end{align} $$ Now, as each customer sits for one unit of time, the probability of the $n$th chair being occupied after a long time is equal equal to the rate at which customers enter the shop and sit in the $n$th chair. They enter at rate $\lambda$, and they sit in the $n$th chair only if the first $n-1$ are occupied but the $n$th is empty (which has probability $p_{n-1,n-1}-p_{n,n}$). This gives the probability of the $n$th chair being occupied as, $$ p_n=\lambda(p_{n-1,n-1}-p_{n,n}). $$ Substituting (5) for $p_{i,n}$ gives the claimed expression (1) for the probability.

---

Above, I have identified a stationary distribution for the number of seats out of the first $n$ that are occupied, and for the set of times that the customers have been sat for. However, I didn't show that the actual distribution from any given starting point does converge to this distribution. I'll show that now using a simple coupling argument. Let $X(T)$ be the state of Hilbert's barber shop at time $T$ (with any starting state that you like). Let $Y(T)$ be the state at time $T$ starting with the stationary distribution identified above, but with the same customer arrival times as $X$. If, over any unit interval $[T-1,T]$, no customers enter the shop, then there will be no customers remaining at time $T$ and the shop is empty, regardless of the starting state. We then have $X(t)=Y(t)$ for all $t\gt T$. So, $X(T)=Y(T)$ whenever there is a unit interval in $[0,T]$ during which no customers arrive, which has a probability approaching 1 exponentially. Therefore, $\mathbb{P}(X(T)\not=Y(T))$ decays exponentially to 0, and the distribution converges exponentially to the stationary one.