Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I think this may be a hard problem for general $p$ and $q$. If $p$ and $q$ were to depend on $n$ as well as $x$ then the problem is open, even in the case of a linear dependency on $n$ and $x$; that case is research problem 6.94 in Concrete Mathematics. If you give some more information about the specific $p$ and $q$ you're interested in you might have a better chance at a good answer. – Mike Spivey Nov 3 '11 at 5:36
OK< I looked it up in Woodbury(1949), Rutherford(1954) and Gani(2006), but still at loss. I think for constnt $p,q$ this is called Kolmogorov backward-forward equation – sigma.z.1980 Nov 3 '11 at 5:49
I mean yes, I can bound both $p$ and $q$, but this would be less interesting – sigma.z.1980 Nov 3 '11 at 5:51
$Mike: shouldn't it be some determinant of eigenmatrix or something? – sigma.z.1980 Nov 3 '11 at 5:51
Care to accept an answer? – Did Jan 10 '12 at 22:33
up vote 1 down vote accepted

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




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

share|cite|improve this answer
this sounds reasonable, but could you give a little bit more details on how to do this conversion. In Migdal(2010) the solution is in the form of the product of diagonal entries of the eigenmatrix – sigma.z.1980 Nov 22 '11 at 22:18

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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