I've been learning about Markov Chains for a reading course I'm doing and I've become stuck on some of the notes I was given. It defines a discrete time queuing chain for a server by $$X_{t+1}=\begin{cases} X_{t}+Y_{t+1}-1 & , X_{t}>0\\Y_{t+1} &, X_{t}=0\end{cases}$$ where $X_{t}$ is the number of job requests in the queue and $Y_{t}$ is the number of job requests that join the chain at time $t$ which follows a Poisson distribution with parameter $\lambda$. There is only one server and it can can only complete one job at each time $t$ (if there are jobs in the queue).

From this we have the transition matrix $P$ with entries defined by $P(0,y)=f(y)$ and $P(x,y)=f(y-x+1)$ where $f$ is the probability density function of $Y_{t}$, $x$ is the current state, and $y$ is the future state.

My issue is that the notes claim that if we have some distribution $q(i)$ defined for integer $i\geq0$ that satisfies $qP=q$ then the probability generating function of $q$ is given by $$\Phi_{q}(s)=\frac{q(0)\Phi_{Y}(s)(s-1)}{s-\Phi_{Y}(s)}$$ where $\Phi_{Y}(s)$ is the probability generating function of $Y_{t}$.

I have no idea how to even derive this expression. I tried using the basic pgf formula of $\Phi_{q}(s)=E\left(s^{q}\right)=\sum_{i} q(i)s^{i}$ and then substitute in the relationship given, but this doesn't appear to help. Could anyone please explain either how to derive this expression, or give me a large shove in the right direction please?


Here's the shove. We can agree that the number of job requests $Y_t$ has probability generating function (pgf) $\Phi_Y(s)$ regardless of $t$, right? Then obtain $\Phi_{q,t+1}(s)=\text{E}[s^{X_{t+1}}]$, the pgf of the number of jobs in the queue at $t+1$ as follows using the system equations you provide, where it is understood that $\Phi_{q,t}(0)=\text{Prob}[X_t=0]$, \begin{align} \Phi_{q,t+1}(s)=\text{E}[s^{X_{t+1}}] & = \text{E}[s^{X_{t+1}}| X_{t}>0] \text{Prob}[X_t>0] + \text{E}[s^{X_{t+1}}| X_{t}=0] \text{Prob}[X_t=0]\\ & = \text{E}[s^{X_t+Y_{t+1}-1}| X_{t}>0] (1-\Phi_{q,t}(0)) + \text{E}[s^{Y_{t+1}}| X_{t}=0] \Phi_{q,t}(0)\\ & = \Phi_Y(s)\frac{1}{s}\text{E}[s^{X_t}| X_{t}>0] (1-\Phi_{q,t}(0)) + \Phi_Y(s) \Phi_{q,t}(0) \end{align} where the independence between $Y_{t+1}$ and $X_t$ was used in both terms. The implicit assumption is made that the queue reaches an equilibrium as $t\to\infty$ which means that the distribution of the number of jobs in the queue no longer changes with time. In other words, after some time we have that $\Phi_{q,t+1}(s) = \Phi_{q,t}(s) = \Phi_{q}(s)$. Now see what you get if you substitute that in the above relation.

  • $\begingroup$ Thanks for the shove! It really helps and I think I've got it now. $\endgroup$ – Jonathan.Lidcombe Oct 15 '17 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.