Recurrence $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

Question

What is the general approach to solving this recurrent equation given that $p(x)$ and $q(x)$ are not constant and do not depend on $n$ and $p(x)+q(x) \neq 1$. Please just give me some hints, don't solve it for me. I know this is similar to Binomial probability of $x$ successes in $n$ trials with a changing probability of success and solved using generating functions or z-transforms.

$p(x)$ can be seen as a probability of success after $n-1$ trials and $x-1$ successes and $q(x)$ as a probability of failure after $n-1$ trials and $x$ successes.

Answer 1

You didn't specify the initial conditions which is a big problem. (And $x$ for an integer index is not a variable choice that makes me happy.) I will assume that $A(n,k)$ is zero if $k$ is negative or bigger than $n$. I will assume that the recurrence holds for all $n\ge1$ and all $x$.

Under this assumptions, let $A_k(z)=\sum\limits_{n=0}^{\infty}A(n,k)t^n$, convert the recurrence to a functional equation and this gives you a product formula for the generating function.

If you sum the recurrence, you get

$$A_k(t)=p(k)A_{k-1}(t)t+q(k)A_k(t)t,$$

so

$$A_k(t)=\frac{p(k)t}{1-q(k)t}A_{k-1}(t).$$

In particular, this works for binomial coefficients and Stirling numbers.

Answer 2

Here is a probabilistic interpretation.

Let $r(x)=p(x)+q(x)$. Consider the random walk $(X_n)_{n\geqslant0}$ on the integer line which, when at $x$, stays at $x$ with probability $p(x)/r(x)$ and moves to $x-1$ with probability $q(x)/r(x)$. Then, writing $\mathbb E_x$ for the expectation when $X_0=x$, one has, for every $n\geqslant0$ and every $x$, $$ \color{blue}{A(n,x)=\mathbb E_x\left(A(0,X_n)\cdot\prod\limits_{k=0}^{n-1}r(X_k)\right)}. $$ Proof: If $X_0=x$ almost surely, the Markov chain $(X_{k+1})_{k\geqslant0}$ is distributed like $(X_{k})_{k\geqslant0}$ for a random $X_0$ with distribution $r(x)^{-1}(p(x)\delta_x+q(x)\delta_{x-1})$. $\ \Box$

To go further, one could want to specify the initial condition $(A(0,x))_x$.