3
$\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

$\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$ 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$ Nov 6, 2011 at 10:33

1 Answer 1

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.

$\endgroup$
7
  • $\begingroup$ the boundary constraint is $A(1,1)$, i.e. in the first iteration the size is 1. $\endgroup$ Nov 6, 2011 at 21:39
  • $\begingroup$ also, where does the expression for $P_{m}(x,z)$ come from? IS this some determinant? $\endgroup$ 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$ 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$ 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$ Nov 8, 2011 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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