# The independence of all sub-paths between adjacent returns to origin in random walks

In random walks, a path may return to origin for the $r$-th time in $n$-th step ($r$ is given but $n$ is not given), and under this condition, these $n$ steps can be split into $r$ sections where each section ends with an $i$-th return ($i=0,1,\ldots,r$). We denote the length of each section as $l_1,l_2,\ldots,l_r$ ($l_1+l_2+\ldots+l_r=n$).

What I concern is the independence between $l_1,l_2,\ldots,l_r$.

In the obvious sense the random walk starts from scratch every time when the path returns to the origin. Thus one may draw a conclusion that they are independent of each other. But the following excerpt from Feller's book (on page 91) tells us an unexpected different story (Because if they are independent, $n/r$ will be irrelevant to $r$ instead of being proportional to $r$).

The result in the above words totally comes from calculation.

My question is: What key point that we ignored led us to the intuitive but wrong conclusion?

I don't have a copy of the book so I can't see the full context, but I suspect the issue is with your statement "if they are independent, $n$ will be of the order of magnitude $r$". I imagine you are thinking that $l_1+\cdots+l_r$ will typically be about $r$ times the expectation of $l_1$.

This doesn't work, because for a simple symmetric random walk, the expectation of $l_1$ is infinite. As $r$ increases, the average of $r$ independent copies will therefore almost surely tend to infinity (so an order of $r^2$ for the sum is plausible - but note that this is not the expectation of the sum, but a typical value).

• The link to the copy of the book is written in the question, which is: sanghv.com/download/soft/… – Daniel Aug 29 '17 at 9:27
• Why is it not the order of $r$, which is more intuitive? – Daniel Aug 29 '17 at 9:29
• It can't be of the order of $r$, since that would imply that the expected time between returns to the origin is finite, which it isn't. – Especially Lime Aug 29 '17 at 9:55
• I'm sorry I didn't make what I'm confused with clear. If it is of the order of $r^2$, the expected time between returns to the origin will be the order of $r$. I want to know why it is still relevant to $r$? Although it should be infinite, but it should not be relevant to $r$, is it? – Daniel Aug 29 '17 at 10:09
• No, the expected time between returns is infinite, so the expectation of $l_1+...+l_r$ is infinite. But $l_1+...+l_r$ is always actually finite we can still ask what the typical value of it is (think of the median, rather than the mean). Feller seems to be saying that what affects the value is the largest $l_i$, and it's likely that one of the $l_i$ will be about $r^2$, but it's not likely that it would be much larger than that. – Especially Lime Aug 29 '17 at 10:23

Thanks to @Especially Lime's reminder of the difference between the median and the mean (in probability, the equivalents are quantile and expectation). And now I think this is exactly the key point leading to the seemingly wrong intuition (also under the misleading of Feller:(). Actually we can see from Feller's first paragraph in the picture and equation (7.7) that what he was really talking about is the quantile instead of the expectation. But in Feller's second paragraph in the picture, it seems he mixed up the two concepts (he used $r^2$ to prove the average increases roughly in proportion to $r$, but this should be some quantile such as median instead of the average). And this can mislead readers (like me).

And when it comes to the average/expectation, the expectation of $\frac{n}{r}$ actually equals the expectation of $l_1$ (in the sense of infinity of the same order), and this is exactly our intuition. But when it comes to the quantile such as the median, actually it is not clear intuitively whether the median of $n$ is proportional to $r$. And thus we need to calculate.

Now we have figured out what's wrong with our first intuition, it is for the expectation/mean/average instead of the quantile such as the median. And by the way, $l_1,l_2,\ldots,l_r$ are truly independent of each other.

Fully understanding a problem is so satisfying, and it feels really great :)