The title says it all. I am interested in the discrete time simple random walk on a path of $n$ nodes, with reflecting barriers. It's clear that the expected value for the cover time $C_n$ is $\frac{5}{4}(n-1)^2$ but is anything known about the higher moments or indeed the full distribution of $C_n$?
2
-
$\begingroup$ what's the initial position of the walk? $\endgroup$– Serguei PopovCommented Nov 4, 2016 at 14:30
-
$\begingroup$ For $k \in \{0, \ldots, n-1\}$, call $C_{n,k}$ the cover time for a random walk on the path of nodes labelled $1, 2, \ldots, n$, starting at $k+1$. I am interested in the distribution of $C_{n,k}$ for any value of $k$. $\endgroup$– emmeCommented Nov 4, 2016 at 14:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It seems that formula (5.7) of Chapter XIV of the 1st volume of Feller may be used to obtain the full distribution of $C_n$ (as distribution of sum of two independent r.v.'s with explicit distributions). Indeed, to cover the path you must visit both extremes. First, use that formula to obtain the distribution of the hitting time of $\{1,n\}$. Once you hit one of the extremes, you have to go to the other one, and the distribution of this time is the same as the distribution of hitting time of $\{-(n-1),n-1\}$ starting at $0$.
Also, see formula (4.11) of the same chapter for the expression for the generating function of the hitting time; this may help obtaining the moments of the cover time.
-
$\begingroup$ This makes sense, but I lose you towards the end of your answer: "Once you hit one of the extremes, you have to go to the other one, and the distribution of this time ..." can you clarify that part? There is no vertex 0 in the given path. There is no negative labelled vertex so what is $\{-(n-1),n-1\}$? $\endgroup$– emmeCommented Nov 4, 2016 at 15:45
-
$\begingroup$ I mean, let us suppose that your vertices are rather labeled $\{0,\ldots,n-1\}$, and you start in $0$. Now, instead of considering the random walk with reflection in $0$ (and waiting until it comes to $n-1$), you may as well consider the simple random walk on $\{-(n-1),\ldots,n-1\}$ (in fact, the reflected random walk is just its absolute value). So, the hitting time of $n-1$ for the reflected random walk is the same as the hitting time of $\{-(n-1),n-1\}$ for the "normal" random walk on $\{-(n-1),\ldots,n-1\}$. $\endgroup$ Commented Nov 4, 2016 at 16:04