3
$\begingroup$

I am trying to solve the following recurrent relation $$ T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0 $$

Where $0\leq n\leq m$ and $m$ is a fixed integer. I have written the relation as a difference equation as it is often a way to solve these, and so for $D(n)=T(n)-T(n+1)$ I get $$ D(n)=\frac{n}{m-n}D(n-1)+\frac{m}{m-n}. $$ Now I want to sum on both side to telescop the sum and use the fact that $T(m)=0$ but my problem is that on the right side, $D(-1)$ is not defined.

The goal of this problem is to find the hitting time from (0,...0) to (1,...,1) for a simple random walk on the $m$-dimensional hypercube and so $T(n)$ represents this (expected) hitting time.

Thanks

  • 0
    I found this article which kinda does what I want to do, but I don't know how he gets to line (11) http://arxiv.org/pdf/quant-ph/0510136.pdf2012-07-26

1 Answers 1