2

Consider a circle. We perform random walks on the boundary of this circle. Without loss of generality, consider the circle to be centered at the origin, and our random walk starts $0^{\circ}$. You return to the starting point after $n$ steps.

We will make $n$ total steps. Each step you randomly traverse to some point on the boundary. There is a straight line that connects the points for each step. So for example, if you traverse to $90^{\circ}$ on the first step, there will be a straight line going from $0^{\circ}$ to $90^{\circ}$, and then if you go to $155^{\circ}$ afterwards, there will then be another line going from $90^{\circ}$ to $155^{\circ}$.

What is the expected number of intersections created by these line segments?

I think this question may be somewhat similar to Expected number of intersection points when $n$ random chords are drawn in a circle, but here all the $n$ line segments are connected. Which means two consecutive line segments cannot intersect one another. So this reduces the maximum number of intersections from $\frac{n(n-1)}{2}$ to $\frac{(n-1)(n-2)}{2}$, I believe. The probability of an intersection between these pairs is still $1/3$.

So does the solution simply just become $\frac{1}{6}(n-1)(n-2)$? I saw some discussions offline that it could be $\frac{1}{6}n(n-3)$.

user5965026
  • 677
  • Is the random walk a uniform random step between 0 and 360 degrees? – Ralff Mar 03 '21 at 15:55
  • I'm not sure, but let's assume that. Also when I think about it, does it actually matter how it's distributed as long as each position has a non-zero probability? I was thinking that, by symmetry, it does not matter. – user5965026 Mar 03 '21 at 15:57
  • I doubt it. Imagine the step is log-normally distributed. You will most likely have a minimum number of steps before an intersection likely. Because with small steps, you don’t have possibility of an intersection. Also, with log-normal you will have non zero probability of stepping to any point on the circle. – Ralff Mar 03 '21 at 16:03
  • @Ralff When you say you "doubt" it, you mean you think the distribution DOES make a difference right? – user5965026 Mar 03 '21 at 16:19
  • Yes. I should have been more clear and not have said “doubt”.... – Ralff Mar 03 '21 at 16:22

1 Answers1

2

Because you end at the starting point, there are $$\binom{n}{2} - n = \frac{n(n-3)}{2}$$ pairs of non-adjacent chords, and each pair of these chords intersects with probability $\frac13$ (here you use that the points are sampled uniformly, as in Expected number of intersection points when $n$ random chords are drawn in a circle). By linearity of expectation, the total expected number of intersections is $\frac{n(n-3)}{6}$ (coinciding intersections, i.e., three or more chords passing through the same point, happen with probability $0$).

Your formula $\frac{(n-1)(n-2)}{6}$ would be correct if the walk would not necessarily end at the starting point. Note that for $n=3$ your formula gives $\frac13$, whereas the answer should be $0$ because the walk ends at the starting point.

user133281
  • 16,073