Consider a Brownian motion in three dimensional space. What is the largest number of points on the path described by the motion which form an arithmetic progression? (Namely, , so that all are equal.)

A 2-D picture; In two dimension the answer is [infinity: oops my mistake] that there is an AP of arbitrary large length almost surely. Source: Raissa D’Souza

Actually a 3d brownian motion will intersect itself but a 4d (or higher) brownian motion will not. For discrete random walks there are still macroscopic self-intersections in 4d (but not higher dimensions), but they are very sparse and disappear in the limit.

I answered 6, based on the following heuristic – of which I am completely unsure, and would love to know whether holds any water.

A Brownian motion from time 0 to t might(?) be modeled by a random walk of m^2*t steps on 1/m*Z^3, that is a grid of cubes with side length 1/m, as m goes to infinity. Blowing this picture up by a factor of m for simplicity, this path would be (roughly) contained in a cube of side length C*m*sqrt(t); so a random point chosen in the cube would have probability P = 1 / (C^3 * m * sqrt(t)) of being a part of the path. We now pretend that the events A_q = “the point q in the cube is a part of the path” can be modeled as all having probability P (which might be very wrong, as the probabilities should be denser near the center, but maybe not significantly so), and being roughly independent (which seems patently wrong for very close points, but maybe OK for far away points).

Now choose two random points on the path, and ask – what is the probability that these points are endpoints of a an A.P. with length exactly k inside the path? Well, this defines a unique A.P., and we can compute what the other k-2 points in the interior are, and the question is whether they all belong to the path (they will not always belong to the cube; but the probability that they will is a constant depending only on k). There are m^4*t^2/2 choices of pairs of points on the path, and the majority of these would not be particularly close to each other – and thus also the k-2 intermediate points are not close to each other – so by the heuristic, the probability that the A.P. is contained in the path is ~ P^{k-2}. Plugging in the value of P, we find that the expected number of such A.P.s is a constant times (m * sqrt(t))^{6 – k}.

So, for k < 6 we see that as m and t go to infinity, the expected number is infinite, and we expect to find many, many A.P.s of size 6, the expected number goes to 0 as m,t go to infinity, so we should not expect to find any at all; and for k=6, the expected number is always a positive constant independent of m and t. I feel that this implies that there should actually be infinitely many such A.P.s, but they should also be rather “rare” (i.e. perhaps only very few up to any given time t).

—

The independence on t is actually very natural – because the motion (as a process) is of course self similar at different resolutions. This clearly implies a 0-infinity law: The expected number of A.P.s of length k between 0 and t must be either 0 or infinity, depending only on k (the independence on t follows from the self-similarity; but on the other hand the expected number between 0 and 2 must be at least the expected number between 0 and 1 and the expected number between 1 and 2). A similar argument shows that between 0 and t there are either almost surely no A.P.s of length k, or almost surely infinitely many such A.P.s. So, the heuristic above clearly fails for k=6, in one direction or the other, and I’m not sure now which. Perhaps my answer should have been 5…

A short part near the beginning of the third paragraph was swallowed up as html tags. The beginning of the paragraph should read:
“So, for k less than 6 we see that as m and t go to infinity, the expected number is infinite, and we expect to find many, many A.P.s of size less than 6. For k greater than 6, the expected number goes to 0…”

By the time and space reflection symmetries of Brownian motion, the probability that is the midpoint of a 3-AP is the probability that two independent Brownian motions started at $x_t$ intersect, where the first is run to time and the other for infinite time. As noted by Tom above, this occurs with positive probability (which increases with )

Different times aren’t independent, but it seems that this should show that almost surely there are 3-APs.

I am guessing the self-intersection probability of 3d Brownian motion is zero.

Actually a 3d brownian motion will intersect itself but a 4d (or higher) brownian motion will not. For discrete random walks there are still macroscopic self-intersections in 4d (but not higher dimensions), but they are very sparse and disappear in the limit.

And,… happy birthday, Lior!

Thanks to both of you!

I answered 6, based on the following heuristic – of which I am completely unsure, and would love to know whether holds any water.

A Brownian motion from time 0 to t might(?) be modeled by a random walk of m^2*t steps on 1/m*Z^3, that is a grid of cubes with side length 1/m, as m goes to infinity. Blowing this picture up by a factor of m for simplicity, this path would be (roughly) contained in a cube of side length C*m*sqrt(t); so a random point chosen in the cube would have probability P = 1 / (C^3 * m * sqrt(t)) of being a part of the path. We now pretend that the events A_q = “the point q in the cube is a part of the path” can be modeled as all having probability P (which might be very wrong, as the probabilities should be denser near the center, but maybe not significantly so), and being roughly independent (which seems patently wrong for very close points, but maybe OK for far away points).

Now choose two random points on the path, and ask – what is the probability that these points are endpoints of a an A.P. with length exactly k inside the path? Well, this defines a unique A.P., and we can compute what the other k-2 points in the interior are, and the question is whether they all belong to the path (they will not always belong to the cube; but the probability that they will is a constant depending only on k). There are m^4*t^2/2 choices of pairs of points on the path, and the majority of these would not be particularly close to each other – and thus also the k-2 intermediate points are not close to each other – so by the heuristic, the probability that the A.P. is contained in the path is ~ P^{k-2}. Plugging in the value of P, we find that the expected number of such A.P.s is a constant times (m * sqrt(t))^{6 – k}.

So, for k < 6 we see that as m and t go to infinity, the expected number is infinite, and we expect to find many, many A.P.s of size 6, the expected number goes to 0 as m,t go to infinity, so we should not expect to find any at all; and for k=6, the expected number is always a positive constant independent of m and t. I feel that this implies that there should actually be infinitely many such A.P.s, but they should also be rather “rare” (i.e. perhaps only very few up to any given time t).

—

The independence on t is actually very natural – because the motion (as a process) is of course self similar at different resolutions. This clearly implies a 0-infinity law: The expected number of A.P.s of length k between 0 and t must be either 0 or infinity, depending only on k (the independence on t follows from the self-similarity; but on the other hand the expected number between 0 and 2 must be at least the expected number between 0 and 1 and the expected number between 1 and 2). A similar argument shows that between 0 and t there are either almost surely no A.P.s of length k, or almost surely infinitely many such A.P.s. So, the heuristic above clearly fails for k=6, in one direction or the other, and I’m not sure now which. Perhaps my answer should have been 5…

A short part near the beginning of the third paragraph was swallowed up as html tags. The beginning of the paragraph should read:

“So, for k less than 6 we see that as m and t go to infinity, the expected number is infinite, and we expect to find many, many A.P.s of size less than 6. For k greater than 6, the expected number goes to 0…”

By the time and space reflection symmetries of Brownian motion, the probability that is the midpoint of a 3-AP is the probability that two independent Brownian motions started at $x_t$ intersect, where the first is run to time and the other for infinite time. As noted by Tom above, this occurs with positive probability (which increases with )

Different times aren’t independent, but it seems that this should show that almost surely there are 3-APs.

Pingback: Answer to TYI 37: Arithmetic Progressions in 3D Brownian Motion | Combinatorics and more