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 ($1$$1$) http://arxiv.org/pd$f$/quant-ph/0510136.pd$f$2012-07-26

1 Answers 1

3

If you just want the answer, your problem is Exercise 10.5 in Markov Chains and Mixing Times by Levin, Peres, and Wilmer. The book is available online here.

The expected time to go from $(0,\dots,0)$ to $(1,\dots,1)$ is
$\sum_{k=1}^m \left[k{m\choose k}\right]^{-1} \cdot \sum_{k=1}^m k{m\choose k} =2^{m-1} \sum_{k=1}^m {m-1\choose k-1}^{-1}={m\over 2}\sum_{k=1}^m{2^k\over k} . $

  • 0
    I'm not too familiar with network interpretations, but that's a start, Thanks2012-07-26