Welcome to MathOverflow

Question

2

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

flag	asked Nov 6 2011 at 6:42 sigma_z_1980 185●1●7

1

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? – Gjergji Zaimi Nov 6 2011 at 7:02

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. – sigma_z_1980 Nov 6 2011 at 10:33

Max Alekseyev · Accepted Answer · 2011-11-06 11:38:26Z UTC

2

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.

edited Nov 6 2011 at 11:38

answered Nov 6 2011 at 11:01

Max Alekseyev
1,669●4●9

	the boundary constraint is $A(1,1)$, i.e. in the first iteration the size is 1. – sigma_z_1980 Nov 6 2011 at 21:39
	also, where does the expression for $P_{m}(x,z)$ come from? IS this some determinant? – sigma_z_1980 Nov 6 2011 at 22:45
	"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)$. – Max Alekseyev Nov 7 2011 at 5:52
	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)$. – sigma_z_1980 Nov 7 2011 at 20:36
	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}$. – Max Alekseyev Nov 8 2011 at 8:02

show 2 more comments

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.