Inspired by Bill Bradley's post, I've decided to lower bound the probability of an intersection which (using the method suggested in Bill's post) gives a slightly less weak upper bound for the expected length of a random walk.

Using Bill's picture and rescaling so that angles are measured as nonnegative fractions of 2pi, we see one domain of self intersection is when $\alpha \lt \beta$ and $\alpha + 2\beta \lt 1/2$. This region is a triangle of base 1/4, and height 1/6, with an area of 1/48. Missing the measure 0 set where $\alpha=\beta$, we reflect across that line, and then once more across the line $\alpha+\beta=1$ to get the other three regions having an intersection, giving the probability of self intersection of three-step paths to be 4/48=1/12.

Now let's extend this to paths with four steps. The number of cases to determine the probability exactly is more than I care to tackle, so I will cheat and underestimate it. I do this by considering just two cases: that an intersection occurs in the first three steps, or that it does not but occurs in the last three steps.

If we considered these cases as disjoint, we would get a probability of 1/12 + 1/12 = 1/6. They aren't, so we will consider the case that $\beta \leq 1/4$ and $\alpha \gt 1/4$ or more visibly use 3/4 of the chance that the last three steps self-intersect. This gives a lower bound of (1/12) times (1+3/4), or 7/48, which gives 1/7 as a weak lower bound.

Using this and Bills estimating method gives 1 + 7*(4-1)=22 as a weak upper bound on the number of steps needed to self-intersect. If we could improve the lower bound from 1/7 to 1/6 for self intersection of a four step path, this would lead to an upper bound of 19 instead of 22.

But if we can cheat once, we can cheat again. The first cheat went from two neighboring angles to three, so we will go from three to five and lower bound the crossing probability of six segments as (7/4) times the probability of four segments. We share the middle angle so that we can nicely separate the domains of the middle angle turning sharp left or sharp right. We do a similar cut and trim and end up with a lower bound of 49/192 =1/4+1/192 for the probability of 6 segments crossing. This gives a slightly better upper bound of 1 +4*5 or 21 for the step length of a walk that does not cross itself.

To justify the cheat, one has to do a lot more work to make sure that the probability grows by 7/4 at this step. However, I won't do that. I use the cheat instead to motivate the idea that 22 is an upper bound that can be improved with a simple argument, and hope to inspire someone to come up with a simple and more honest and precise estimate.

Gerhard "Long As It's Not Graded" Paseman, 2019.03.20.

Inspired by Bill Bradley's post, I've decided to lower bound the probability of an intersection which (using the method suggested in Bill's post) gives a slightly less weak upper bound for the expected length of a random walk.

Using Bill's picture and rescaling so that angles are measured as nonnegative fractions of 2pi, we see one domain of self intersection is when $\alpha \lt \beta$ and $\alpha + 2\beta \lt 1/2$. This region is a triangle of base 1/4, and height 1/6, with an area of 1/48. Missing the measure 0 set where $\alpha=\beta$, we reflect across that line, and then once more across the line $\alpha+\beta=1$ to get the other three regions having an intersection, giving the probability of self intersection of three-step paths to be 4/48=1/12.

Now let's extend this to paths with four steps. The number of cases to determine the probability exactly is more than I care to tackle, so I will cheat and underestimate it. I do this by considering just two cases: that an intersection occurs in the first three steps, or that it does not but occurs in the last three steps.

If we considered these cases as disjoint, we would get a probability of 1/12 + 1/12 = 1/6. They aren't, so we will consider the case that $\beta \leq 1/4$ and $\alpha \gt 1/4$ or more visibly use 3/4 of the chance that the last three steps self-intersect. This gives a lower bound of (1/12) times (1+3/4), or 7/48, which gives 1/7 as a weak lower bound.

Using this and Bill's estimating method gives 1 + 7*(4-1)=22 as a weak upper bound on the number of steps needed to self-intersect. If we could improve the lower bound from 1/7 to 1/6 for self intersection of a four step path, this would lead to an upper bound of 19 instead of 22.

But if we can cheat once, we can cheat again. The first cheat went from two neighboring angles to three, so we will go from three to five and lower bound the crossing probability of six segments as (7/4) times the (lower bound of the) probability of four segments. We share the middle angle so that we can nicely separate the domains of the middle angle turning sharp left or sharp right. We do a similar cut and trim and end up with a lower bound of 49/192 =1/4+1/192 for the probability of 6 segments crossing. This gives a slightly better upper bound of 1 +4*5 or 21 for the step length of a walk that does not cross itself.

To justify the cheat, one has to do a lot more work to make sure that the probability grows by 7/4 at this step. However, I won't do that. I use the second cheat instead to motivate the idea that 22 is an upper bound that can be improved with a simple argument, and hope to inspire someone to come up with a simple and more honest and precise estimate.

Gerhard "Long As It's Not Graded" Paseman, 2019.03.20.

Inspired by Bill Bradley's post, I've decided to lower bound the probability of an intersection which (using the method suggested in Bill's post) gives a slightly less weak upper bound for the expected length of a random walk.

Using Bill's picture and rescaling so that angles are measured as nonnegative fractions of 2pi, we see one domain of self intersection is when $\alpha \lt \beta$ and $2\alpha + \beta \lt 1/2$. This region is a triangle of base 1/4, and height 1/6, with an area of 1/48. Missing the measure 0 set where $\alpha=\beta$, we reflect across that line, and then once more across the line $\alpha+\beta=1$ to get the other three regions having an intersection, giving the probability of self intersection of three-step paths to be 4/48=1/12.

Now let's extend this to paths with four steps. The number of cases to determine the probability exactly is more than I care to tackle, so I will cheat and underestimate it. I do this by considering just two cases: that an intersection occurs in the first three steps, or that it does not but occurs in the last three steps.

If we considered these cases as disjoint, we would get a probability of 1/12 + 1/12 = 1/6. They aren't, so we will consider the case that $\beta \leq 1/4$ and $\alpha \gt 1/4$ or more visibly use 3/4 of the chance that the last three steps self-intersect. This gives a lower bound of (1/12) times (1+3/4), or 7/48, which gives 1/7 as a weak lower bound.

Using this and Bills estimating method gives 1 + 7*(4-1)=22 as a weak upper bound on the number of steps needed to self-intersect. If we could improve the lower bound from 1/7 to 1/6 for self intersection of a four step path, this would lead to an upper bound of 19 instead of 22.

But if we can cheat once, we can cheat again. The first cheat went from two neighboring angles to three, so we will go from three to five and lower bound the crossing probability of six segments as (7/4) times the probability of four segments. We share the middle angle so that we can nicely separate the domains of the middle angle turning sharp left or sharp right. We do a similar cut and trim and end up with a lower bound of 49/192 =1/4+1/192 for the probability of 6 segments crossing. This gives a slightly better upper bound of 1 +4*5 or 21 for the step length of a walk that does not cross itself.

To justify the cheat, one has to do a lot more work to make sure that the probability grows by 7/4 at this step. However, I won't do that. I use the cheat instead to motivate the idea that 22 is an upper bound that can be improved with a simple argument, and hope to inspire someone to come up with a simple and more honest and precise estimate.

Gerhard "Long As It's Not Graded" Paseman, 2019.03.20.

Inspired by Bill Bradley's post, I've decided to lower bound the probability of an intersection which (using the method suggested in Bill's post) gives a slightly less weak upper bound for the expected length of a random walk.

Using Bill's picture and rescaling so that angles are measured as nonnegative fractions of 2pi, we see one domain of self intersection is when $\alpha \lt \beta$ and $\alpha + 2\beta \lt 1/2$. This region is a triangle of base 1/4, and height 1/6, with an area of 1/48. Missing the measure 0 set where $\alpha=\beta$, we reflect across that line, and then once more across the line $\alpha+\beta=1$ to get the other three regions having an intersection, giving the probability of self intersection of three-step paths to be 4/48=1/12.

Now let's extend this to paths with four steps. The number of cases to determine the probability exactly is more than I care to tackle, so I will cheat and underestimate it. I do this by considering just two cases: that an intersection occurs in the first three steps, or that it does not but occurs in the last three steps.

If we considered these cases as disjoint, we would get a probability of 1/12 + 1/12 = 1/6. They aren't, so we will consider the case that $\beta \leq 1/4$ and $\alpha \gt 1/4$ or more visibly use 3/4 of the chance that the last three steps self-intersect. This gives a lower bound of (1/12) times (1+3/4), or 7/48, which gives 1/7 as a weak lower bound.

Using this and Bills estimating method gives 1 + 7*(4-1)=22 as a weak upper bound on the number of steps needed to self-intersect. If we could improve the lower bound from 1/7 to 1/6 for self intersection of a four step path, this would lead to an upper bound of 19 instead of 22.

But if we can cheat once, we can cheat again. The first cheat went from two neighboring angles to three, so we will go from three to five and lower bound the crossing probability of six segments as (7/4) times the probability of four segments. We share the middle angle so that we can nicely separate the domains of the middle angle turning sharp left or sharp right. We do a similar cut and trim and end up with a lower bound of 49/192 =1/4+1/192 for the probability of 6 segments crossing. This gives a slightly better upper bound of 1 +4*5 or 21 for the step length of a walk that does not cross itself.

To justify the cheat, one has to do a lot more work to make sure that the probability grows by 7/4 at this step. However, I won't do that. I use the cheat instead to motivate the idea that 22 is an upper bound that can be improved with a simple argument, and hope to inspire someone to come up with a simple and more honest and precise estimate.

Gerhard "Long As It's Not Graded" Paseman, 2019.03.20.