How to solve $h(i) = \frac{i^2}{(n-i)^2+i^2}h(i-1) + \frac{(n-i)^2}{(n-i)^2+i^2}h(i+1)$

Question

$h(i) = $P(reach n eventually| the initial state = i)

$h(0) = 0$

$h(n) = 1$

0 and n are stopping time.

For $ 0 < i < n$,

$$h(i) = \frac{i^2}{(n-i)^2+i^2}h(i-1) + \frac{(n-i)^2}{(n-i)^2+i^2}h(i+1)$$

How to solve for $h(i)$?

Answer 1

Try to write $h(i+1)-h(i)$ in terms of $h(i)-h(i-1)$
I think you get $${n-1\choose i}^2(h(i+1)-h(i))=h(1)-h(0)$$

Answer 2

Let's assume that $h(i) = k^i$ for an arbitrary k. So the problem changes to

$$k^i = \dfrac{i^2}{(n-i)^2 +i^2}k^{i-1}+\dfrac{(n-i)^2}{(n-i)^2+i^2}k^{i+1}$$

assuming that $k \neq 0$ we have

$$\dfrac{(n-i)^2}{(n-i)^2+i^2}k^{2}-k+\dfrac{i^2}{(n-i)^2 +i^2}= 0$$

so

$$k= \dfrac{1 \pm \sqrt{1-4\dfrac{(n-i)^2i^2}{((n-i)^2+i^2)^2}}}{\dfrac{2(n-i)^2}{(n-i)^2+i^2}}$$

Now assume that the solution is a lineal combination from the previous answers ($k_1$ and $k_2$) so

$$h(i) = m_1k_1^i + m_2k^i_2$$

replace on your original equation , solve the $m_i$ terms and conclude.

---

Edit: I just noticed that $k$ may be reduced:

$$k= \dfrac{1 \pm \sqrt{1-4\dfrac{(n-i)^2i^2}{((n-i)^2+i^2)^2}}}{\dfrac{2(n-i)^2}{(n-i)^2+i^2}} =\dfrac{((n-i)^2+i^2)\pm((n-i)^2-i^2)}{2(n-i)^2}$$

so

$$k_1 =\dfrac{2(n-i)^2}{2(n-i)^2}= 1 \land k_2 = \dfrac{i^2}{(n-i)^2}$$

Answer 3

It is a matrix equation:

$$ \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ \frac{1^2}{(n-1)^2+1^2} & 0 & \frac{(n-1)^2}{(n-1)^2+1^2} & 0 & \cdots & 0 & 0 & 0 \\ 0 & \frac{2^2}{(n-2)^2+2^2} & 0 & \frac{(n-2)^2}{(n-2)^2+2^2} & \cdots & 0 & 0 & 0 \\ 0 & 0 & \frac{3^2}{(n-3)^2+3^2} & 0 & \cdots & 0 & 0& 0 \\ 0 & 0 & 0 & \frac{4^2}{(n-4)^2+4^2} & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & ...& \frac{3^2}{3^2+(n-3)^2} & 0 & 0 \\ 0 & 0 & 0 & 0 & ...& 0 & \frac{2^2}{2^2+(n-2)^2} & 0 \\ 0 & 0 & 0 & 0 & ...& \frac{(n-1)^2}{1^2+(n-1)^2} & 0 & \frac{1^2}{1^2+(n-1)^2} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} h_0=0 \\ h_1 \\ h_2 \\ h_3 \\ h_4 \\ \vdots \\ h_{n-3} \\ h_{n-2} \\ h_{n-1} \\ h_n=1 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ h_1 \\ h_2 \\ h_3 \\ h_4 \\ \vdots \\ h_{n-3} \\ h_{n-2} \\ h_{n-1} \\ h_n=1 \end{bmatrix} $$

Removing $h_0$ and $h_n$ and bringing all other $h_i$ to left hand side:

$$ \begin{bmatrix} -1 & \frac{(n-1)^2}{(n-1)^2+1^2} & 0 & \cdots & 0 & 0 \\ \frac{2^2}{(n-2)^2+2^2} & -1 & \frac{(n-2)^2}{(n-2)^2+2^2} & \cdots & 0 & \\ 0 & \frac{3^2}{(n-3)^2+3^2} & -1 & \cdots & 0 & 0 \\ 0 & 0 & \frac{4^2}{(n-4)^2+4^2} & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & ...& \frac{3^2}{3^2+(n-3)^2} & 0 \\ 0 & 0 & 0 & ...& -1 & \frac{2^2}{2^2+(n-2)^2} \\ 0 & 0 & 0 & ...& \frac{(n-1)^2}{1^2+(n-1)^2} & -1 \\ \end{bmatrix} \times \begin{bmatrix} h_1 \\ h_2 \\ h_3 \\ h_4 \\ \vdots \\ h_{n-3} \\ h_{n-2} \\ h_{n-1} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \\ -\frac{1^2}{1^2+(n-1)^2} \\ \end{bmatrix} $$

You only need one more step to solve a matrix equation to obtain $h_1$, $h_2$, ... ,$h_{n-1}$