2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Is the random walk a uniform random step between 0 and 360 degrees? $\endgroup$
    – Ralff
    Mar 3, 2021 at 15:55
  • $\begingroup$ 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. $\endgroup$ Mar 3, 2021 at 15:57
  • $\begingroup$ 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. $\endgroup$
    – Ralff
    Mar 3, 2021 at 16:03
  • $\begingroup$ @Ralff When you say you "doubt" it, you mean you think the distribution DOES make a difference right? $\endgroup$ Mar 3, 2021 at 16:19
  • $\begingroup$ Yes. I should have been more clear and not have said “doubt”.... $\endgroup$
    – Ralff
    Mar 3, 2021 at 16:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What does the $\binom{n}{2}$ represent physically in this case? $\endgroup$ Mar 3, 2021 at 16:38
  • $\begingroup$ There are $n$ chords, so there are $\binom{n}{2}$ pairs of chords. $\endgroup$
    – user133281
    Mar 3, 2021 at 16:42
  • 1
    $\begingroup$ Sorry, that was a typo. I meant the $n$. It seems you're subtracting the number of pairs of adjacent chords? $\endgroup$ Mar 3, 2021 at 16:46
  • 1
    $\begingroup$ Indeed -- there are $n$ such pairs $\endgroup$
    – user133281
    Mar 3, 2021 at 19:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .