\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

A household which drinks at most one bottle of wine a week keeps a
stock which is checked every Saturday morning.  If there is at
least one bottle in stock there is  probability $q$ that a bottle
will be consumed during the following week.  If there is no stock
then, with probability $p_j$, $j$ bottles are purchased that
morning $(j = 0, 1, 2,\ldots ).$  Sobered by the cost, the members
of the household drink no wine during the following week.

The number of bottles in stock at each check forms an infinite
Markov chain with states $0, 1, 2,\ldots$ .  Write down its
probability transition matrix.

Let $N_{j0}$ denote the number of weeks until the stock is reduced
from $j$ bottles to zero for the first time.  Let $F_j(s)$ be the
generating function for the probabilities: $$f_{j0}^{(n)} =
P\{N_{j0} = n\} \hspace{.2in} {\rm for \ \ } n = 1, 2, 3, ...;$$
that is $$F_j(s) = \sum_{n=1}^\infty f_{j0}^{(n)}s^n.$$

Prove that $$F_1(s) = \frac{qs}{1-ps}, \hspace{.2in} {\rm where\ \
} p = 1 -q.$$ By expressing $N_{j0}$  as the sum of $j$
independent, identically distributed random variables, or
otherwise, show that $$F_j(s) = \left[\frac{qs}{1 - ps}\right]^j
{\rm for\ \ \ }j = 1, 2, 3, ...$$ Show also that $$F_0(s) = s
G\left[ \frac{qs}{1-ps} \right],$$ where $G(t)$ is the probability
generating function for the distribution $\{p_j\}$ $j = 0, 1, 2,
\ldots$, that is $$G(t) = \sum_{j=0}^\infty p_jt^j.$$  Hence prove
that return to state 0 occurs with probability 1.



\newpage

{\bf Answer}

The transition matrix is $$\bordermatrix{& 0 &  1 & 2 & 3 & \cdots
\cr 0 & p_0 & p_1 & p_2 & p_3 & \cdots \cr 1 & q & 1-q & 0 & 0 &
\cdots \cr 2 & 0 & q & 1-q & 0 & \cdots \cr 3 & 0 & 0 & q & 1-q &
\cdots \cr \vdots & \vdots & \vdots }$$

Assuming the $p_i's$ are all positive, then all states
intercommunicate.

The probability that the first transition from 1 to 0 occurs in
$n$ steps is given by: $$f_{10}^{(n)} = \left\{ \begin{array}{ll}
0 & {\rm if\ }  n=0 \\ (1-q)^{n-1)} \cdot q & n = 1, 2, ...
\end{array} \right.$$

The p.g.f. is therefore \begin{eqnarray*} F_1(s) & = &
\sum_{n=1}^\infty f_{10}^{(n)}s^n \\ & = & \frac{q}{1-q}
\sum_{n=1}^\infty [(1-q)s]^n \\ & = & \frac{qs}{1-(1-q)s}
\end{eqnarray*}

Let $N_{jk}$ denote the number of steps for the first passage from
state $j$ to state $k.$  Now the only route from $j$ to 0 is

$j \to (j-1) \to (j-2) \to ...\to 1 \to 0$,

with stops possible at each stage (e.g. $1\to 1\to 1\to 0$)

So $ N_{j0} = N_{j,j-1} + N_{j-1,j-2} + ... + N_{1,0}$

Now $N_{j,j-1}$ etc have the same distribution as $N_{1,0}$ and
are independent by the Markov properly.

So the generating function for the probabilities $\ds
p_{j0}^{(n)}$ is $$F_j(s) = [F_1(s)]^j = \left( \frac{qs}{1-ps}
\right) ^j \,\, \, (p = 1-q)$$

\newpage
[ Alternatively \begin{eqnarray*} f_{j,0}^{(n)} & = &
qf_{j-1,0}^{(n-1)} + p f_{j,0}^{(n-1)} \\ F_j (s) & = &
\sum_{n=1}^\infty f_{j,0}^{(n)}s^n \\ & = & q \sum_{n=1}^\infty
f_{j-1,0}^{(n-1)}s^n + p \sum_{n=1}^\infty f_{j,0}^{(n-1)}s^n \\ &
= & qsF_{j-1}(s) + psF_j(s) \\ \\ {\rm So\ } F_j(s) & = &
\frac{qs}{1-ps} F_{j-1}(s) \\ & = & \left( \frac{qs}{1-ps}
\right)^{j-1} f_1(s) \\ & = & \left. \left( \frac{qs}{1-ps}
\right)^j \hspace{1in} \right]\end{eqnarray*}


Now\begin{eqnarray*} F_0(s) & = & \sum_{n=1}^\infty
f_{00}^{(n)}s^n \\ {\rm where\ \ } f_{(00)}^{(n)} & = & \left\{
\begin{array}{ll} p_0 & n=1 \\ \ds \sum_{j=1}^\infty p_jf_{j0}^{(n-1)}
& n = 2, 3, ... \end{array} \right. \\ {\rm so\ \ } F_0(s) & = &
p_0s + \sum_{n=2}^\infty \left( \sum_{j=1}^\infty p_j
f_{j0}^{(n-1)} \right) s^n \\ & = & p_0 s + \sum_{j=1}^\infty
\sum_{n=2}^\infty  p_j f_{j0}^{(n-1)} s^n \\ & = & p_0 s + s
\sum_{j=1}^\infty p_j \sum_{n=2}^\infty  f_{j0}^{(n-1)}  s^{(n-1)}
\\ & = & p_0 s + s \sum_{j=1}^\infty p_j \sum_{m=1}^\infty
f_{j0}^{(m)}s^m \\ & = & p_0 s + s \sum_{j=1}^\infty p_jF_j(s) \\
& = & s \sum_{j=0}^\infty p_j \left( \frac{qs}{1-ps} \right)^j \\
& = & s G\left( \frac{qs}{1-ps} \right) \end{eqnarray*} Where G is
the p.g.f. for the sequence $p_0, p_1, ...$.  The probability of
return to state 0 is

$\ds F_0(1) = G\left( \frac{q}{1-p} \right) = G(1) = 1 \,\, \, \,
(1-p=q) $

So state 0 is recurrent.



\end{document}