Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$. (Simple: each pair of lines meet in a distinct point, i.e., no three lines pass through the same point.) Start a random walk at an arrangement vertex $v_0$. Choose to walk along one of the lines $L_0$ passing through $v_0$, and turn left or right with equal probability at the next vertex $v_1$. Then walk along the line $L_1$, where $v_1 = L_1 \cap L_0$. Turn at $v_2 = L_1 \cap L_2$, and so on. (Never proceed straight through; never back-up.)

          An arrangement of $25$ lines. Random walk starting at $v_0$.

Q1. As a function of $n$, which arrangements $\cal{A}_n$ of $n$ lines have the highest probability that the walk will revisit some $v_0$?

If the four cells incident to $v_0$ are two triangles and two quadrilaterals, then there should be at least a $$ \tfrac{1}{16} + \tfrac{1}{16} + \tfrac{1}{32} + \tfrac{1}{32} = \tfrac{3}{16} $$ chance of returning to $v_0$. For example, for one triangle, choose $L_0$ and a direction along $L_0$$\frac{1}{4}$, then turn left twice—$\frac{1}{2} \frac{1}{2}$; so return to $v_0$ by traversing that triangle with probability $\frac{1}{16}$.

Eventually, any walk will escape to $\infty$.

Q2. As a function of $n$, which arrangements $\cal{A}_n$ of $n$ lines lead to the quickest escapes to $\infty$, in the sense that every starting vertex $v_0$ leads to a quick escape?

In other words, let $E(v)$ be the expected number of steps for a walk starting at $v$ to escape to $\infty$. Then I seek the arrangements $\cal{A}_n$ that minimize the maximum of $E(v)$ over all $v \in \cal{A}_n$. So no $v$ is "deep" inside the arrangement.

A possible extremal configuration: Each line is tangent to a central circle.

Related MO question: "A random walk on random lines."

  • $\begingroup$ How do you get two triangles and four quadrilaterals as adjoining cells ? Gerhard "I Am Assuming No Concurrency" Paseman, 2018.10.09. $\endgroup$ – Gerhard Paseman Oct 9 '18 at 15:38
  • $\begingroup$ @GerhardPaseman: Two triangles and two quads (not four). There is an example in the figure, at about 11 o'clock. $\endgroup$ – Joseph O'Rourke Oct 9 '18 at 15:48
  • $\begingroup$ I think I can prove (assuming no concurrency) that you need at least one pentagonal figure. All the tentative examples at eleven o'clock seem to be of this form. If it is not too much to ask, could you show me wrong by shading a portion of your figure green? Gerhard "Placng A Circle Should Suffice" Paseman, 2018.10.09. $\endgroup$ – Gerhard Paseman Oct 9 '18 at 16:00
  • $\begingroup$ Using perturbations of a square grid, I get one triangle and three quadrilaterals around a vertex. If I use concurrency, I can get two adjacent triangles (and up to four triangles). Gerhard "Wants To Find Your Example" Paseman, 2018.10.09. $\endgroup$ – Gerhard Paseman Oct 9 '18 at 16:13
  • $\begingroup$ I was looking at pictures of diagonals of regular n-gons recently. Maybe a configuration can be embedded in a regular n-gon arrangement for large n? In any case, even though these arrangements have concurrency, they don't have much, and the regularity should make it easy to compute probabilities, if not evaluate them exactly. Gerhard "Work On Pretty Version First" Paseman, 2018.10.09. $\endgroup$ – Gerhard Paseman Oct 9 '18 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.