0
$\begingroup$

How to solve the following 2D recurrence relation?

$$F(n_1, n_2)=a\bigl[F(n_1-1, n_2)+F(n_1+1, n_2)+F(n_1, n_2-1)+F(n_1, n_2+1)\big]$$ with $1\leq n_1\leq L_1,\ 1\leq n_2\leq L_2$. a is a positive real number. Boundary condition: $F(m_1, m_2)=1$.

*$n_1$ and $n_2$ are the coordinate indices and ($m_1$, $m_2$) is a point in the lattice.

I checked similar questions on this topic and I tried to use the Generating function method as explained Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$ The difficulty is the boundary condition.

The problem I'm considering is the first passage time of a particle searching for a target in 2-D lattice of size $L_1 \times L_2$. Here $(n_1, n_2)$ is the position of a particle at time t=0 and $(m_1, m_2)$ is the position of the target. $F(n_1, n_2)=F(n_1, n_2,s)$ is the Laplace transform (s is the Laplace variable) of the first passage time probability.

$\endgroup$
6
  • $\begingroup$ Please use latex conventions. For example $n$ indexed by $1$ is rendered by : dollar sign followed by letter a followed by underscore symbol followed by digit 1 followed by dollar sign. $\endgroup$
    – Jean Marie
    Commented Jun 27, 2017 at 18:06
  • $\begingroup$ I am afraid that there is no other solution than the zero function. $\endgroup$
    – Jean Marie
    Commented Jun 27, 2017 at 18:19
  • $\begingroup$ boundary condition is corrected. $\endgroup$
    – Jaeoh Shin
    Commented Jun 27, 2017 at 22:58
  • $\begingroup$ Hint: find when $\lambda_1^{n_1}\lambda_2^{n_2}$ satisfies the recurrence relation. Linear combinations give the general solution. $\endgroup$
    – J.G.
    Commented Jun 27, 2017 at 22:59
  • $\begingroup$ @J.G. Thanks for your advice. The problem is while there is only one recursion relation, there are two undetermined variables $\lambda_1$ and $\lambda_2$. $\endgroup$
    – Jaeoh Shin
    Commented Jun 28, 2017 at 0:03

1 Answer 1

1
$\begingroup$

Following a suggestion in my comment, we attempt $F=\lambda_1^{n_1}\lambda_2^{n_2}$ so $\frac{1}{a}=\frac{1}{\lambda_1}+\lambda_1+\frac{1}{\lambda_2}+\lambda_2$. Define $\mu_i:=\lambda_i+\frac{1}{\lambda_i}$ so $\lambda_i=\frac{\mu_i\pm\sqrt{\mu_i^2-4}}{2}$ and $\mu_2=\frac{1}{a}-\mu_1$. The most general solution is a linear combination over choices of $\mu_1$, an integral rather than a sum. The result is$$\int_Sd\mu_1\left(a_1^+\left(\mu_1\right)\left(\frac{\mu_1+\sqrt{\mu_1^2-4}}{2}\right)^n+a_1^-\left(\mu_1\right)\left(\frac{\mu_1-\sqrt{\mu_1^2-4}}{2}\right)^n+a_2^+\left(\mu_1\right)\left(\frac{\frac{1}{a}-\mu_1+\sqrt{\left(\frac{1}{a}-\mu_1\right)^2-4}}{2}\right)^n+a_2^-\left(\mu_1\right)\left(\frac{\frac{1}{a}-\mu_1-\sqrt{\left(\frac{1}{a}-\mu_1\right)^2-4}}{2}\right)^n\right)$$for arbitrary functions $a_i^\pm$. The integration range $S$ is an exercise for the reader, and so is finding a solution satisfying the desired boundary condition. It's constrained by the fact that constraints on the $\lambda_i$ constrain the $\mu_i$ (and may in some cases cause one of the values for a $\lambda_i$ consistent with a given $\mu_i$ consistent with that range to be outside it, meaning a coefficient has to be $0$).

$\endgroup$
1
  • $\begingroup$ Thanks! it seems promising. $\endgroup$
    – Jaeoh Shin
    Commented Jun 28, 2017 at 22:05

You must log in to answer this question.

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