4
$\begingroup$

I asked this question on MSE, but didn't get enough information. If it is a violation of some norms, let me know, I'll delete it.

I'm having problem solving this difference equation. Initially I thought it should be quite easy to solve using generating functions (e.g. like in Migdal(2010), Woodbury(1949) or Gani(2006), but have made no progress so far.

The intuition behind it is that each iteration population either increases by 1 species (with probability $p(x)$ or stays the same w.p. $q(x)$, so $A(n,x)$ can be seen as the expected size of the population at iteration $n$.

It seems pretty straightforward, but I couldn't move along. I know the solution involves Casoratian and finding some product $\Pi_{x=1}^{m}p(x)$, but apart form that I couldn'd do much.

Also, if it happens to be some well-known problem, please don't solve it for me, just point in the right direction

MSE link

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Do you just want to see a formal solution, or do you have some information on the boundary values which might help give a prettier approximate answer? $\endgroup$
    – Gjergji Zaimi
    Commented Nov 6, 2011 at 7:02
  • $\begingroup$ The boundary value is $A(1,1)$, i.e. the population is size 1 at $i=1$. I would appreciate any help, be it some closed form or approximation. $\endgroup$
    – sigma_z_1980
    Commented Nov 6, 2011 at 10:33

2 Answers 2

Reset to default
3
$\begingroup$

Let $$P_m(x,z) = \prod_{k=0}^{m-1} (p(x-k)+q(x-k)z)$$ and $$\mathcal{A_n}(x,z) = \sum_{k=0}^{\infty} A(n,x-k) z^k.$$

Then unrolling the given recurrence $m$ times, we get that $A(n,x)$ equals the coefficient of $z^m$ in $$P_m(x,z)\cdot \mathcal{A}_{n-m}(x,z).$$ In particular, for $A(n,x)$ equals the coefficient of $z^n$ in $$P_n(x,z)\cdot \mathcal{A}_{0}(x,z).$$

More could be said if the boundary constraints were given.

Improve this answer
$\endgroup$
7
  • $\begingroup$ the boundary constraint is $A(1,1)$, i.e. in the first iteration the size is 1. $\endgroup$
    – sigma_z_1980
    Commented Nov 6, 2011 at 21:39
  • $\begingroup$ also, where does the expression for $P_{m}(x,z)$ come from? IS this some determinant? $\endgroup$
    – sigma_z_1980
    Commented Nov 6, 2011 at 22:45
  • $\begingroup$ "the boundary constraint is A(1,1)" - and what is its value? And what's about $A(1,x)$ for $x$ not equal 1? To express $A(n,x)$ in terms of $A(1,x)$, take $m=n-1$. $P_m(x,z)$ is a polynomial defined via given $p(x)$ and $q(x)$. $\endgroup$
    – Max Alekseyev
    Commented Nov 7, 2011 at 5:52
  • $\begingroup$ OK, it's not very good notation then. The boundary value would be $A(1)=1$, i.e. in the first iteration the size of population is 1. Each iteration the size either increases by 1 w.p. $p(x), x$ being the size of the population in the previous turn, or stays the same w.p. $q(x)$. $\endgroup$
    – sigma_z_1980
    Commented Nov 7, 2011 at 20:36
  • $\begingroup$ So $A(n,x)$ is the probability that in the $n$-th iteration the size of population equals $x$. Then $A(1,x) = \delta_{x1}$ (Kronecker's delta). Correspondingly, $\mathcal{A_1}(x,z) = z^{x-1}$. $\endgroup$
    – Max Alekseyev
    Commented Nov 8, 2011 at 8:02
0
$\begingroup$

I can also suggest another approach to this partial difference equation. We will solve it using the Method of Separation of Variables.

We search for the solution in the form

$$f(n, x) = U(n)V(x)$$

Substitute it in the equation:

$$U(n)V(x) = p(x)U(n-1)V(x-1) + q(x)U(n-1)V(x)$$

Then separate the variables:

$$\frac{U(n)}{U(n-1)} = \frac{p(x)V(x-1)+q(x)V(x)}{V(x)} = \alpha = const$$

Therefore, we obtain two linear difference equations:

$$U(n)=\alpha U(n-1)$$

and

$$V(x) = \frac{p(x)}{\alpha - q(x)} V(x-1)$$

By simple induction we get

$$U(n) = \alpha^{n}U(0)$$ and $$V(x) = V(0)\cdot\prod_{j=0}^{x-1}\frac{p(j)}{\alpha-q(j)}, \; x \geq 0$$ $$V(x) = V(0)\cdot\prod_{j=x+1}^{0}\frac{\alpha-q(j)}{p(j)}, \; x < 0$$

So, for particular $\alpha$ we obtained the functions $U_{\alpha}(n)$, $V_{\alpha}(x)$

General solution to this difference equation is obtained by summing over all $\alpha$:

$$f(n, x) = \sum_{\alpha} c(\alpha) U_{\alpha}(n)V_{\alpha}(x)$$

where $c(\alpha)$ is an arbitrary function.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .