1

I have n recurrence relations of the following form:

For $i=1$:

$v_1(t) = \frac{1}{2}v_1(t-1) + \frac{1}{2}v_2(t-1)$

for $1<i<n$:

$v_i(t) = \frac{1}{2}v_{i-1}(t-1) + \frac{1}{2}v_{i+1}(t-1)$

For $i=n$:

$v_n(t) = \frac{1}{2}v_{n-1}(t-1) + \frac{1}{2}v_n(t-1)$

Additionally, for all $i$:

$v_i(0) = x_i$, a variable representing an initial value.

Does anyone know how to solve this?

Jannik
  • 355
  • Are you looking for a closed form of each $v_i(t)$? Is $t$ a real number or an integer? What have you tried? – Bill O'Haran Apr 25 '18 at 12:49
  • t is an integer, sorry for the confusion. I can solve the problem with a transition matrix. For $n=3$, the transition matrix is \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 \ \frac{1}{2} & 0 & \frac{1}{2} \ 0 & \frac{1}{2} & \frac{1}{2} \\end{bmatrix} and get the result by multiplying the t-th power of the matrix with my initial values. As the matrix is also the transition matrix of a irreducible and aperiodic Markov chain I can calculate the exact result. However, I look for different solutions to get a closed formula. – Jannik Apr 25 '18 at 14:33

1 Answers1

0

$$ v_{i,t} = \frac{1}{2}\left(v_{i-1,t-1}+v_{i+1,t-1}\right) $$

Making $v_{i,t} = \alpha^i\beta^t$ and substituting we get

$$ \alpha + \alpha^{-1} = 2\beta\Rightarrow \alpha = \beta \pm \sqrt{\beta^2-1} $$

or

$$ v_{i,t} = C_1\alpha_1(\beta)^i\beta^t + C_2\alpha_2(\beta)^i\beta^t $$

etc.

Cesareo
  • 33,252
  • is this somehow a standard trick you play here? I do not really understand how I can use the information about $\alpha$ and $\beta$ to finally solve the equation. – Jannik Apr 25 '18 at 15:49
  • This is not a trick. This is the standard solution for $v_{i,t}$ – Cesareo Apr 25 '18 at 16:01
  • Apparently, I am not familiar with these solutions. Could you link some literature explaining your approach? thanks in advance – Jannik Apr 25 '18 at 16:04
  • In the net there is a lot of publications handling this type of problem. As for example https://www.stat.washington.edu/peter/491/diff.pdf – Cesareo Apr 25 '18 at 16:10
  • so my general solution is $v_{i,t} = (\beta \pm \sqrt{\beta^2 -1})^i \cdot \beta^t$ for a constant $\beta$? – Jannik Apr 25 '18 at 16:34
  • Yes, It seems to be that. Follow the initial conditions. – Cesareo Apr 25 '18 at 17:04