Skip to main content
Image links broken; now fixed. Additional minor edits.
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpgr10

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpgalt 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!. Permit me to take the liberty of editorializing. First, it is immensely satisfying to see five respondents (as shown by Didier, Hugh, George, Anthony, and fedja) effectively collaborate over the course of a day to reach such a clear resolution. I am especially grateful at how instructive is their collective discussion. Second, to meAlthough I find Pólya's recurrence is surprising but (perhaps because I've grown used to it) quite believable., But thatthat this segment-walk sweeps the plane is somehow more remarkable, even if it relies (as fedja's exposition shows) on roughly the same logic.

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
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!. Permit me to take the liberty of editorializing. First, it is immensely satisfying to see five respondents (Didier, Hugh, George, Anthony, fedja) effectively collaborate over the course of a day to reach such a clear resolution. I am especially grateful at how instructive is their collective discussion. Second, to me Pólya's recurrence is surprising but (perhaps because I've grown used to it) quite believable. But 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.

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.

Addendum, thanks, editorializing.
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
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!. Permit me to take the liberty of editorializing. First, it is immensely satisfying to see five respondents (Didier, Hugh, George, Anthony, fedja) effectively collaborate over the course of a day to reach such a clear resolution. I am especially grateful at how instructive is their collective discussion. Second, to me Pólya's recurrence is surprising but (perhaps because I've grown used to it) quite believable. But 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.

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
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!

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
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!. Permit me to take the liberty of editorializing. First, it is immensely satisfying to see five respondents (Didier, Hugh, George, Anthony, fedja) effectively collaborate over the course of a day to reach such a clear resolution. I am especially grateful at how instructive is their collective discussion. Second, to me Pólya's recurrence is surprising but (perhaps because I've grown used to it) quite believable. But 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.

Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Sweep-segment bot: Will this random walk sweep the plane?

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

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 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
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!