# 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?

• Hint: you can ignore all the chairs beyond 3. Many of them will be full, but you want to concentrate on how often a customer leaves 3 and has not being replaced yet. Commented Sep 3, 2013 at 17:49
• @RossMillikan Agreed, and the occupation of Chair 1 is easy to work out along those lines. It seems to me that solving for Chairs 2 and 3 will have to involve rate equations that depend not just on whether chairs are occupied but also how much time remains for each person in each chair. Commented Sep 3, 2013 at 18:30
• That is correct. They will be coupled. Commented Sep 3, 2013 at 19:25
• @bhensley: I just tried doing that, writing down the differential equations, and it turns out that there is a surprisingly simple solution. Consequently, you can write down the limiting probabilities of being in any state. I'll post it as an answer later. Commented Sep 11, 2013 at 10:15
• Queue Theory !!!. Commented Sep 11, 2013 at 22:18

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.