recurrent events-Probability of even number of successes

Question

Let E be the event of an even number of successes.

$u_n$:Probability of E occurring at the nth trial not necessarily for the first time

$f_n$:Probability of E occurring at the nth trial for the first time

Let U(x) and F(x) be the corresponding probability generating functions and from that we have the equation $$U(x)=1/(1-F(x))$$ I first wrote a recurrence formula $u_n=p(1-u_{n-1})+qu_{n-1}$

By solving this I got $$U(x)=px/[(1-x)(1-(q-p)x)]$$

Intuitively I feel $F(x)$ should be $p^2x^2/(1-qx)^2$ since this event can be taken as the sum of two geometric random variables. However this is not what I get from the $U(x)$ that I have computed. Did I do something wrong? Any assistance will be very helpful to me. Thanks alot

EDIT: In an answer I saw $u_n$ taken as $[1-(q-p)^{n-1}]p$ which gives results in the $F(x)$ of sum of two random geometric variables but I do not know how this $u_n$ was constructed

Answer 1

Here's a way to do by using a Markov chain:

\begin{align*} A &= \begin{pmatrix} q & p & 0 \\ 0 & q & p \\ q & p & 0 \end{pmatrix} \end{align*}

Answer will be the third column of the first row in $A^n$, and the generating function for all entries can be obtained directly from the matrix by computing \begin{align*} \left(I-x\, A\right)^{-1} \end{align*}

Thus, the gf for the required entry is: \begin{align*} G(x) &= -\frac{p^{2} x^{2}}{{\left(p^{2} - q^{2}\right)} x^{2} + 2 \, q x - 1} \end{align*} and by partial fractions, \begin{align*} G(x) &= \frac{p^2}{q-p}+\frac{p}{2}\left(\frac{1}{1-x}-\frac{1}{\left(q-p\right)\left(1-(q-p)\, x\right)}\right) \end{align*} Hence, the solution for $u_n$ is given by $[x^n]$, which is \begin{align*} u_n &= \frac{p}{2}\left(1-(q-p)^{n-1}\right) \end{align*}

Update

We can obtain the recurrence using the markov chain as:

\begin{align*} u_n &= p\, v_{n-1} \\ v_n &= p\, \left(u_{n-1}+w_{n-1}\right)+q\, v_{n-1} \\ w_n &= q\, \left(u_{n-1}+w_{n-1}\right) \\ u_1 &= 0 \\ v_1 &= p \\ w_1 &= q \\ u_2 &= p^2 \\ v_2 &= 2pq \\ w_2 &= q^2 \\ \end{align*} $u_n$ is the required answer.

$w_n$ gives the probability of even number of successes, but not exactly at the $n^{th}$ trial.

$v_n$ is for the odd number of successes.

Answer 2

Let $u_n$ be the probability that $n$ Bernoulli trials result in an even number of successes. This occurs if an initial failure is followed by an even number of successes, or an initial success is followed by an odd number of successes. Therefore $u_0=1$ and for $n\geq 1$ $$u_n=q u_{n-1}+p(1-u_{n-1}).$$ Multiplying by $s^n$ and adding over $n$ we see that the generating function satisfies $$U(s)=1+qsU(s)+ps(1-s)^{-1}-psU(s)$$ or $$2U(s)=[1-s]^{-1}+[1-(q-p)s]^{-1}.$$ Expanding the right hand side using geometric series we find that the coefficients satisfy $$u_n={1\over 2}+{(q-p)^n\over 2}.$$

Reference: This answer is taken practically verbatim from Chapter XI, section 4, page 277 of An introduction to probability theory and its applications (1st edition) by William Feller.