4
$\begingroup$

Suppose customers arrive in a 24hour cashier according to a Poisson process, at rate $\lambda$ (per hour), while their service time is exponential, of parameter $\alpha$ (independent from each other). Customers are served one at a time. Let $X_n$ be the number of customers in line, waiting to be served, when the $n$-th customer arrives.

1) Find the transition probabilities of $\{X_n\}$.

2) Find the limit distribution (if exists).

3) What is the probability $k$ customers wait in line at 10.00 in the morning?

Attempt.

1) Since $X_{n+1}=X_n+1-E_{n+1}$, where $E_n$ is the number of customers served between the $n-1$-th and $n$-th customer arrival, we get: $$p_{k,m}=P(E_{n+1}=k+1-m)=\left(\frac{\alpha}{\alpha+\lambda}\right)^{k+1-m}\frac{\lambda}{\alpha+\lambda}$$ for $k=0,1,2,\ldots$ and $m=0,1,\ldots,k+1.$

2) Do we seek the limit as $n\to +\infty$ of $p(X_{n}=m|X_0=k)$? If so, i am not sure how to approach this.

3) I am not sure how to approach this, either. I am having a difficulty turning the problem in terms of $X_n.$

Thanks in advance for the help.

$\endgroup$

1 Answer 1

2
$\begingroup$

I'll focus on the answers to two and three. Finding the limiting distribution directly is likely difficult, since, chances are, writing down that probability explicitly and taking the limit is not straightforward.

Thus I will take a slightly more indirect approach, that is to say, I will find the stationary distribution instead. You can argue that the limiting distribution is the same as the stationary distribution (see here).

First of all, assume that $\lambda > 0$ and $\alpha > 0$, otherwise the solution is trivial. Let $N_t$ be the number of customers in the queue at time $t$, and let $p(t,x)$ denote $P(N_t=x)$. Then the master equation (aka Kolmogorov's forward equation) says that $$\frac{d}{dt} p(t,x) = -(\lambda + \alpha)p(t,x) + \lambda p(t,x-1) + \alpha p(t,x+1), \text{ for } x\ge 1,$$ and $$\frac{d}{dt}p(t,0) = -\lambda p(t,0) + \alpha p(t,1).$$ The the stationary distribution $\pi(\cdot)$, solves the above equations when we set the time derivatives to zero. Let's start with the latter equation and "work our way up". Set the time derivative to zero, and we see that $$0 = -\lambda \pi(0) + \alpha \pi(1),$$ which implies that $$\pi(1) = \frac{\lambda}{\alpha}\pi(0).$$ Then do essentially the same thing with the first differential equation, but this time solve for $\pi(2)$. I'll let you fill in the details, but you should find that $$\pi(2) = \frac{\lambda^2}{\alpha^2} \pi(0).$$ You can keep going and solve for more values of $\pi(x)$, but the pattern becomes pretty obvious. Thus a good guess for the functional form of the stationary distribution is $$\pi(x) = \left(\frac{\lambda}{\alpha}\right)^x \pi(0), \text{ for all } x\ge 0.$$ You can verify that the above guess solves the recurrence equations (the equations we get from setting the time derivative to zero).

To find the value of $\pi(0)$, note that we should have $$\sum_{x=0}^\infty \pi(x) = 1.$$ Use the above condition to solve for $\pi(0)$, which consequently gives you the value of $\pi(x)$ for all $x$. You should find that $$\pi(0) = \frac{\alpha-\lambda}{\alpha}.$$ Also, we know that $\pi(0) >0$, so this gives us a condition for the existence of the stationary distribution, which answers one of your questions. Think about why this intuitively makes sense (if $\lambda > \alpha$, what is $\mathbb{E}[N_t]$ as $t$ goes to infinity?). And in the case when $\alpha=\lambda$, think about how the number of customers is related to an unbiased random walk (probability 1/2 of taking a right or left step).

You can use the stationary distribution to answer the last question. Since the cashier is there 24/7 and has presumably been there for a long time, the stationary distribution is highly relevant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .