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.

Suppose we have a circumference divided in N arcs of the same length. A particle can move on the circumference jumping from an arc to the adjacent, with probability $P_{k \to k-1}=P_{k\to k+1}=\frac{1}{2}$. I have some difficulty to find the probability that the particle fulfilled at least one complete turn on the circumference after $M$ jumps with $M\gt N$. Thanks

share|improve this question
    
Are you asking about the first time when the particle visited at least once every arc? –  Did Jul 12 '12 at 13:41
    
@did: yes the interpretetion is correct –  Riccardo.Alestra Jul 12 '12 at 15:54

1 Answer 1

up vote 5 down vote accepted

The time needed to visit at least once each vertex of a graph is called the cover time of the graph. Let $C_n$ denote the cover time of the discrete circle of size $n$. Then $\mathrm E(C_n)=\frac12n(n-1)$. The expression of the distribution of $C_n$ for any fixed $n$ is cumbersome but a result due to Jean-Pierre Imhof in 1985 describes the asymptotics as follows: when $n\to\infty$, $n^{-2}C_n\to C$ in distribution, where the distribution of $C$ has density $$ \sqrt{\frac{8}{\pi t^3}}\cdot\sum_{k=1}^{+\infty}(-1)^{k-1}k^2\mathrm e^{-k^2/(2t)}\cdot[t\gt0]. $$ A different, equivalent, expression of the limit distribution is in Amine Shihi's PhD thesis.

A related (and somewhat counterintuitive) result might be worth mentioning: for every $n\geqslant2$, the last vertex visited, that is, the position of the particle at time $C_n$ is uniformly distributed on the $n-1$ vertices which are not the starting one.

share|improve this answer

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.