Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I found this article which kinda does what I want to do, but I don't know how he gets to line (11) arxiv.org/pdf/quant-ph/0510136.pdf –  Jean-Sébastien Jul 26 '12 at 2:54

1 Answer 1

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} . $$

share|improve this answer
    
I'm not too familiar with network interpretations, but that's a start, Thanks –  Jean-Sébastien Jul 26 '12 at 3:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.