MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $Q=[-1/2,1/2]^2$ be a unit square and let $(\ell_n,\varepsilon_n)_{n\geq1}$ be an iid sequence of isotropic lines intersecting $Q$ (more precisely, distributed according to a Haar measure on the space of lines) and colored indepently black ($\varepsilon_n=1$) or white ($\varepsilon_n=-1$). Color the vertical boundaries of $Q$ white and its horizontal boundaries black. The line $\ell_1$ dissects $Q$ into two polygons $Q_{1,1}$ and $Q_{1,2}$ whose boundaries are also colored black and white. Furthermore a polygon $Q_{1,i}$ is deleted, if the black points form a connected component of its boundary. Now iterate this procedure (i.e. take $\ell_2$, intersect it with all (maybe just one?) of the remaining polygons and delete some of the newly created polygons according to the above rule).

Does this procedure terminate a.s. after finitely many steps?

[this problem appeared while studying a Poisson line version of confetti-percolation, but it might also have some inherent appeal]

share|cite|improve this question
My intuition says yes, since with high probability most of the regions inside the crisscrossed square will be triangles with 1/8 of them all white. There will be few if any interior regions with 4 or more sides, and they will likely survive again with probability 1/8. I have not done the computations however. Gerhard "Ask Me About System Design" Paseman, 2012.04.24 – Gerhard Paseman Apr 24 '12 at 18:55
Further reflection shows that the actual problem is not as simple as the intuitive picture above, because the order in which you color the placed lines matters. To me though, that just means even more of the regions (including the all white regions) get deleted. Perhaps the (place lines, then color them all, then delete) model will be of some help. Gerhard "Ask Me About System Design" Paseman, 2012.04.24 – Gerhard Paseman Apr 24 '12 at 19:02
Today, I have run some simulations and (to my surprise!) it seems that a.s. convergence fails even for quite unbalanced color proportions (I have tried black-white proportions up to $9:1$)... – Christian Hirsch Apr 25 '12 at 17:26
My initial impression was that there was a 50% chance that the first line placed would take out both polygons. (If not 50 then maybe 25 at least.) Is this not the case? What are the termination probabilities for n lines for small n that you are seeing? Gerhard "Ask Me About System Design" Paseman, 2012.04.25 – Gerhard Paseman Apr 25 '12 at 22:50
Here are the number of iterations for the case where black and white have equal probability (stopping after 130 iterations, 1000 simulations) \begin{tabular}{ l lllllllll } 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 &\ldots &121 &130 \\ 0.199& 0.147& 0.091& 0.070& 0.039 &0.030 &0.022 &0.014 &0.015& 0.016 &\ldots & 0.001 & 0.161 \end{tabular} – Christian Hirsch Apr 26 '12 at 15:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.