# Solving the following recurrence relation derived from a Markov chain

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.

• 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. – Yuval Filmus Jun 16 '17 at 11:29
• 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. – Yuval Filmus Jun 16 '17 at 11:31
• 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. – Landon Carter Jun 16 '17 at 11:31
• 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. – Yuval Filmus Jun 16 '17 at 11:35
• 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. – Landon Carter Jun 16 '17 at 11:42