17
$\begingroup$

This model is inspired by the random behavior of the Roomba sweeping robot.

Let a unit segment $ab$ in the plane be placed initially with $a=(0,0)$ and $b=(1,0)$. The segment is first rotated a random angle $\theta_1$ about $a$, $\theta_1 \in (-\pi,+\pi)$, sweeping out a sector of angle $\theta_1$ centered on $a$. Then it is rotated a random angle $\theta_2$ about $b$, sweeping out a sector of angle $\theta_2$ centered on $b$. Odd steps rotate about $a$, even about $b$, each with $\theta_i \in (-\pi,+\pi)$; each sector sweeps $< \pi$.

An example is shown below. The first, darker sector sweeps $\theta_1=114^\circ$ (ccw), the second sweeps $\theta_2=-140^\circ$ (cw), and the sequence continues $$\theta_3,\ldots = 104^\circ,-112^\circ,-93^\circ,-156^\circ,15^\circ,-97^\circ,-37^\circ,72^\circ \;.$$
r10

Q. Does the described random walk of this segment eventually sweep every point of the plane with probability 1? That is, will the union of the sectors cover the plane?

My guess is: 'Yes,' because of the analogy with Pólya's recurrence theorem for random walks on a 2D lattice. Indeed if the random angle is discretized to $\theta_i \in \{ -\pi, -\pi/2, +\pi/2, +\pi \}$, then the segment midpoint executes a random walk on a lattice. On the other hand, it seems remarkable that this process would actually sweep the whole plane. Here is the same example extended to 10,000 steps:
alt text
Despite the similarities, I don't see how to directly reduce this model to a conventional random walk to answer the posed question. If anyone does, I would appreciate suggestions. Even just your intuitions are welcomed. Thanks!

Addendum. The answer to my question is a clear Yes!, as shown by Didier, Hugh, George, Anthony, and fedja. Although I find Pólya's recurrence surprising, that this segment-walk sweeps the plane is somehow more remarkable, even if it relies (as fedja's exposition shows) on roughly the same logic.

$\endgroup$
5
  • 1
    $\begingroup$ Sweet problem! Are the random angles $\theta_i$ independent and uniform on the interval $(-\pi,+\pi)$? $\endgroup$
    – Did
    Dec 10, 2010 at 18:47
  • 2
    $\begingroup$ When $\theta_i$ is $+\pi/2$ or $-\pi/2$ or $\pi$ ($-\pi$ being superfluous), the successive positions of the midpoint do not perform a simple random walk in the classical sense. To wit, the legal steps at time $n+1$ depend on the step performed at time $n$. For instance, after a $(+1,0)$ step, the next step can be $(+1,0)$, $(+1/2,+1/2)$ and $(+1/2,-1/2)$ only. More generally, the set of all possible steps ever has size $8$ but only $3$ of them are possible after each given one. This looks more like an odd kind of reinforced random walk to me (and these are notoriously difficult to analyze). $\endgroup$
    – Did
    Dec 10, 2010 at 19:07
  • $\begingroup$ @Didier: Yes, angles uniform and independent. Good point about the discretized version being a biased walk. Perhaps if the angle is one of $-\pi/2,0,\pi/2$ ... I will investigate reinforced random walks, a new term to me. Thanks for your interest! $\endgroup$ Dec 10, 2010 at 19:13
  • 1
    $\begingroup$ @Joseph: It will sweep the plane, but not very efficiently. How long would it take to sweep a circle of radius $R^2$ (asymptotically as $R\to\infty$)? I've no idea, but I expect it takes much longer than $O(R^2)$. $\endgroup$ Dec 10, 2010 at 22:57
  • 1
    $\begingroup$ @George: You mean there is not much commercial promise here to undercut Roomba? :-) $\endgroup$ Dec 11, 2010 at 0:02

4 Answers 4

9
$\begingroup$

Once Didier touched it, let me comment that we do not need the full $[-\pi,\pi]$ swing here. Any fixed non-degenerate sectors for $A$ and $B$ rotations would do the job perfectly well.

As Didier proposed, we consider any "reinforced random walk with translation and circular symmetry" that operates like that: at each moment, we have a point $x_k$ (with $x_0=0$, for definiteness) and a rotation $R_k$ ($R_0$ can be anything). Each step consists of adding to $x_k$ the vector $R_k w_k$ and multiplying $R_k$ by $S_k$ to get $x_{k+1}$ and $R_{k+1}$ respectively where $(w_k,S_k)$ are i.i.d. pairs with some joint distribution satisfying some natural assumptions (we do not need much here: to know that $w_k$ are bounded and that the joint density is bounded is more than enough and our process falls under those assumptions if we agree to view 10 steps as one)

The proof starts the same way as Polya's recurrence argument: if the probability fof $x$ to return to some neighborhood of the origin is less than $1$, then, for any bounded region $U$, the probability for $x$ to visit $U$ more than $k$ times decays exponentially with $k$, so all moments of the number of visits are finite, etc.

Now, cover the plane by unit disks in some nice way. Two cases are possible: A) The probability to ever visit the disk $Q$ decays to $0$ as the distance from $Q$ to the origin tends to $0$. B) There are arbitrarily far disks $Q$ (depending on $R_0$, of course) that are hit with probability at least $q$ for some fixed $q>0$.

We'll show that both (A) and (B) imply recurrence.

In case (A), notice that the expectation $E|x_k|^2\le Cn$ for $k\le n$ (just estimate scalar products of increments $(R_kw_k,R_mw_m)$. they decay exponentially with $|k-m|$) , so if we denote by $v(Q)$ the number of visits to $Q$ after $n$ steps, we'll have $E\sum_Q v(Q)d(Q)^2\le Cn^2$ where $d(Q)$ is the distance from $Q$ to the origin. Thus, the sum of $v(Q)$ over the disks with $d(Q)<C\sqrt n$ is at least $n/2$.

On the other hand, under the non-recurrence assumption, $E\sum_{Q:d(Q)\le C\sqrt n}v(Q)^2\le C_1 n$ (each term is bounded). It follows that, after $n$ steps, the number of visited unit disks with $d(Q)\le C\sqrt n$ is at least $cn$ with noticeable probability. But the assumption (A) immediately implies that the expected number of disks with that property that we ever visit is $o(n)$ - Contradiction.

In case (B), we note first that if $Q_0$ is hit with probability $\ge q$ by the process starting with some $R_0$, then $CQ_0$ is hit with probability $\ge q/2$ starting with any $R_0$ if $C$ is big enough. Indeed, if the initial rotations are close enough, we have some small difference in the first increments but then we can use the representations of these 2 processes in which all other increments are the same outside a very small probability event. To pass from the small differences to everything, it is enough to note that it is highly unlikely not to have $R_k$ in any given open set at least once during the first $M$ steps if $M$ is big enough no matter what rotation we start with. But the first $M$ steps can shift us by $CM$ at most and we can compensate for that by expanding the disk.

The moral now is that every disk $CQ$ at the same distance as $CQ_0$ from the origin is hit with probability $\ge q/2$ no matter what rotation we start with. Then every disk $2CQ$ whose distance from the origin is not bigger than twice that of $CQ_0$ is hit with probability $\ge q^2/4$. Since the distance $d(Q_0)$ could be taken arbitrarily large, we eventually hit every disk of radius $2C$ with fixed positive probability no matter how we start. This is the same as recurrence for the processes under consideration.

Of course, this all is well-known in much higher generality but it was easier to present this (sketch of a) proof than to dig through the literature. Now it just remains to prove that I'm a human being (Grrrr... That captcha really acts on my nerves).

$\endgroup$
13
$\begingroup$

Let us call $[A_n,B_n]$ the segment at time $n$. Then, for all $n \ge 1$:

1) $A_n$ is chosen uniformly on the circle of radius $1$ centred at $A_{n-1}$ (independently of the past).

2) $B_n=A_{n-1}$.

Therefore $A_n$ performs a simple random walk.

$\endgroup$
4
  • $\begingroup$ @Hugh: By "sphere" do you mean "circle"? $\endgroup$ Dec 10, 2010 at 20:43
  • $\begingroup$ @Joesph : yes, circle. $\endgroup$
    – Hugh J
    Dec 10, 2010 at 21:00
  • $\begingroup$ Yes, this definitely shows that it will sweep the plane. $\endgroup$ Dec 10, 2010 at 22:42
  • 1
    $\begingroup$ Alternatively, let $B(t)$ be a 2d Brownian motion. $T_0$ = 0 and $T_{n+1}$ is the first time after $T_n$ that $\Vert B(t)-B(T_n)\Vert=1$. Then, $B(T_n)$ has the same dynamics as $A_n$ described above. As 2D Brownian motion is recurrent, this shows that $A_n$ is recurrent. $\endgroup$ Dec 10, 2010 at 22:47
7
$\begingroup$

Call $[A_n,A_n+V_n]$ the segment at time $n$ assuming that $A_n$ is the end of the segment around which it rotates between times $n$ and $n+1$. Thus $A_n$ and $V_n$ are complex numbers, $A_0=1=V_0$, and $V_n$ has modulus $1$ for every $n$. Then (I believe that) for every $n\ge0$, $$ A_{n+1}=A_n+U_{n+1}V_n,\qquad V_{n+1}=-U_{n+1}V_n,$$ where $(U_n)_{n\ge0}$ is an i.i.d. sequence with a given distribution on the unit circle.

This shows that $(A_n)_n$ is not a Markov chain in general except for the case you said you were interested in, where the random variables $U_n$ are uniform on the unit circle, that $(A_n,V_n)_n$ is always a Markov chain, and that $$ V_n=(-U_1)\cdots(-U_n),\qquad A_n=1-\sum_{k=1}^n(-U_1)\cdots(-U_k). $$ We seem to be back to some known territory here...

$\endgroup$
4
  • $\begingroup$ @Didier: Nice idea to interpret the rotations as complex-number multiplications! Not sure I yet see the consequences of your analysis... $\endgroup$ Dec 10, 2010 at 20:46
  • 3
    $\begingroup$ OK, I am stupid: $U_{n+1}$ is uniform on the circle and independent of $(A_n,V_n)$, hence $U_{n+1}V_n$ is also uniform on the circle and also independent of $(A_n,V_n)$. The dynamics of $(A_n)_n$ is simply $A_{n+1}=A_n+W_n$ with $(W_n)_n$ i.i.d. and uniform on the circle. This is a random walk in the plane with uniformly bounded increments hence it is recurrent, at least in the sense that $|A_n|$ does not converge to infinity and probably also in the sense that $(A_n)_n$ visits infinitely often every ball of positive radius--which should be enough to show that the whole plane is sweeped. $\endgroup$
    – Did
    Dec 10, 2010 at 21:05
  • $\begingroup$ Didn't notice when leaving the comment to Hugh J's answer: that one and this are essentially the same. The points $A_n$ just follow a random walk on the plane. $\endgroup$ Dec 10, 2010 at 22:52
  • 1
    $\begingroup$ @Didier: By Theorem 9.1 and 9.2 of Kallenberg (Foundations of Modern Probability), any random walk whose increments have finite variance is recurrent. That is, its set of cluster points forms a closed additive subgroup of $\mathbb{R}^2$. In this case, the support of the possible steps of $A_n$ spans all of $\mathbb{R}^2$, so its set of cluster points is $\mathbb{R}^2$. $\endgroup$ Dec 10, 2010 at 23:24
3
$\begingroup$

I buy Hugh's answer (but can't fit this into a comment on it). Consider the sequence of most recently updated endpoints. As argued above, each one is a point a distance one from the last endpoint. Therefore this is just a random walk where the random jumps are vectors of length 1.

Since the jump distribution is in L^2 and the random walk lives in two dimensions, Spitzer's book implies that the r.w. is recurrent. Thus it returns to an epsilon-neighbourhood of the origin infinitely many times.

Now if you have a favourite delta-ball in the plane there is a finite sequence of moves so that if you make this any sequence of moves that agrees with the given finite sequence up to some eta-tolerance, you are guaranteed to cover the delta-ball assuming you started in the original epsilon-ball. Making a sequence of moves of this type has a fixed positive probability each time you return to the epsilon-ball at the origin.

Now you are done by Borel-Cantelli. Each time you come back to the epsilon-ball (there are infinitely many) you get a new chance to cover your delta-ball.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.