# Probability Generating Functions and Discrete Time Queuing Chains

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.