Hilbert's Barber Shop

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?

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.