I have the following system of recursive relations on $y_{i,j}$ that are derived from a Markov chain and that I am having difficulty in solving. For $i\ge 1$ and $j \ge 1$, we have

$$y_{i,j} \times (p_i+q_j+2)=y_{i-1,j} \times p_i+y_{i,j-1} \times q_j+2y_{i+1,j+1}.$$

Also we have

$$\begin{align*} y_{1,0} \times (p_1+q_0+2) &=2y_{2,1}\\ y_{0,1} \times (p_0+q_1+2) &=2y_{1,2} \end{align*}$$

Here $p_i=ai+b$ and $q_j=cj+d$.

I want to solve this infinite system of linear equations. Ideally, I'd like a closed form for $y_{i,j}$, as an expression in terms of $i,j,a,b,c,d$. At least I would like to understand how the system evolves, such as the asymptotic behavior of $y_{i,j}$ as a function of $i,j$.

I observed a few things: for all $j$, $y_{0,j}$ and $y_{j,0}$ are independent. Also, $y_{1,1}$ is an independent variable. That's all I could do, nothing more. Help is appreciated.

  • $\begingroup$ Have you tried solving is symbolically for small $i,j$ and identifying a pattern? By solving symbolically I mean solving with $a,b,c,d$ being parameters. $\endgroup$ Commented Jun 16, 2017 at 11:29
  • $\begingroup$ This is not really a recurrence relation, due to the $(0,0)$ issue as well as the appearance of $y_{i+1,j+1}$; and additionally, $y_{j,0},y_{0,j}$ are not "defined" at all. It is an infinite linear system, which probably comes from analyzing some Markov chain. I suggest not hiding such facts. $\endgroup$ Commented Jun 16, 2017 at 11:31
  • $\begingroup$ Yes I tried. That's how I found $y_{0,j},y_{j,0}$ have to be independent (probably I'm correct). I have a feeling the $y_{i,j}$ are unbounded although I couldn't prove it. I could not find any pattern. $\endgroup$ Commented Jun 16, 2017 at 11:31
  • $\begingroup$ Can you solve it when $a=c=0$? Try the particular case $p_i=q_j=1$. Perhaps the general case reduces to this case by using a clever substitution. $\endgroup$ Commented Jun 16, 2017 at 11:35
  • $\begingroup$ With $p_i$ and $q_j$ linear in $i$ and $j$ resp., one animal approach is to use generating function which will immediately yield you the solution (if the recurrence indeed gives a power series). But then one gets partial derivatives of recurrence relations and I am too scared to even look at the gigantic form. I'll check the $p_i=q_j=1$ case and inform here. $\endgroup$ Commented Jun 16, 2017 at 11:42


Your Answer

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

Browse other questions tagged or ask your own question.