Afternoon tea discussions at DTU Mathematics — discussions on non-applied mathematics.

On the probability of covering m random points with a given subset of the unit circle

Question 1: If one picks m points at random on the unit circle \mathbb{S}^1, what is the probability that they can be covered by a half circle A \subset \mathbb{S}^1?

Question 2: Let 1 \ge a \ge 0. Suppose A \subset \mathbb{S}^1 is a Borel measurable set of measure \mu(A)=a , where \mu(\mathbb{S}^1)=a . What is probability that A can cover m random points?

Question 3: Let 1 \ge a \ge 0 be given. What is the best subset A \subset \mathbb{S}^1 to choose with \mu(A)=a if we want to cover m random points?

Covering points with an interval

We consider a generalized version of Question 1. We want to find the probability P_A(m) that m points falls within an arc A of \mathbb{S}^1 of length a, where the total length of \mathbb{S}^1 is one, i.e., \mu(\mathbb{S}^1)=1 with \mu (also denoted |\cdot|) being the (probability Lebesgue) surface measure on \mathbb{S}^1.

To be more precise we need some notation. We identify \mathbb{S}^1 with \mathbb{T}^1=\mathbb{R}/\mathbb{Z} and do most of our computations in \mathbb{T}^n modulo 1. Let a \in \mathbb{R} be given such that 0 \le a \le 1, and let A=[0,a).Let X_1, \dots, X_m \in [0,1] be an independent and identically distributed (i.i.d.) sample from U(0,1) — the uniform distribution on [0,1] . Then P_A(m) = P\{(X_1, X_2, ..., X_m) \in H\}, where we set

Theorem 1. If a \le 1/2, then P_A(m)=m a^{m-1} for all m=1,2,\dots.

Proof. Notice that the complement of A + \tau is B + \tau, where B = [a, 1). Therefore the following three statements are equivalent.

• \exists \tau s.t. x_j \in A + \tau, j = 1, 2, ..., m;
• \exists k s.t. x_j \in A + x_k, j = 1, 2, ..., m;
• \exists k s.t. x_j \notin B + x_k, j = 1, 2, ..., m.

In other words, letting H_k = \{(x_1, x_2, \dots, x_n) \,\vert\, x_j \notin (x_k, x_k + a] \pmod 1, j = 1, ..., n\} , we have H = \cup H_k.

We claim that the sets H_j are essentially disjoint, in the sense that H_i \cap H_j has measure zero on T^n when i \neq j. To see this notice that if (x_k)_{k=1}^m \in H_i \cap H_j and x_i \neq x_j then the distance going counter-clockwise from x_i to x_j is at least |B| \geq \frac{1}{2}, and likewise the distance from x_j to x_i going counter-clockwise is at least \frac{1}{2}. So for (X_1, ..., X_m) to lie in H_i \cap H_j we must have that X_i and X_j either coincide or are antipodal, events with probability zero.

We can conclude that P((X_1, ..., X_m) \in H) = \sum P(H_k) = m a^{m-1}. ■

TO-DO: Extend this argument to the case a>1/2.

By Theorem 1 it follows that the probability of covering m random points by a half circle A=[0,1/2) is P_A(m)=m (1/2)^{m-1} which was the question asked in Question 1. One might wonder whether you arrive at the same probability if A consists of two quarter-circles. If the quarter-circles are diametrically opposite, e.g., A=[0,1/4) \cup [1/2,3/4) this is indeed the case. It follows from the following observation:

Remark 1. Let n \in \mathbb{N} be given. If A=A+k/n \pmod 1 for all k=1,\dots,n-1, then

Consider the three sets A=[0,1/3), B=[0,1/6) \cup [3/6,4/6), and C=[0,1/6) \cup [2/6,3/6), all of measure 1/3. By Remark 1 we see that P_A(m)=P_B(m)=m (1/3)^{m-1} hence, in paricular, the probability of catching two random points by either A or B is P_A(2)=P_B(2)=2/3. For the set C, however, we set that P_C(2)=1 since if the distance from x_1 to x_2 is less that 1/6, we can find \tau so that x_1,x_2 \in [0,1/6)+\tau \subset C+\tau. On the other hand, if the distance between x_1 and x_2 is greater than 1/6, but less that 1/2, we can find \tau so that x_1 \in [0,1/6)+\tau and x_2 \in [2/6,3/6)+\tau, hence \{x_1,x_2\}\subset C+\tau. The event that the distance between x_1 and x_2 is exactly either 1/6 or 1/2 has probability zero. We remark that the set C. in contrast to B, does not satisfy the 'symmetry' condition C=C+1/2 \pmod 1 from Remark 1.

The following result shows that sets with "similar" symmetry properties have the same covering probabilities.

Lemma 1. Let n \in \mathbb{N} and A_0 \subset T^1 be given. Define A=\cup_{l=0}^{n-1}A_0 + l/n \pmod 1 and B=nA_0 \pmod 1. If |A| =|B| = n |A_0| , then

Proof. Let M be a measurable set such that A_0 \subseteq M , |M|=1/n, and nM=[0,1] (up to sets of measure zero). Let \bar{\mu} be the uniform probability measure on M. Notice that \bar{\mu}=n \mu on M. Therefore, the \bar{\mu}-probability of X_1,\dots,X_m \in A_0 for i.i.d. X_1,\dots,X_m \in U(M), denoted P^{\bar{\mu}}_{A_0}(m), is the same as the \mu-probability of X_1,\dots,X_n \in nA_0=B for i.i.d. X_1,\dots,X_m \in U([0,1]), that is, P_B(m). On the other hand, by Remark 1, the probability P_A(m) is identical to P^{\bar{\mu}}_{A_0}(m). ■

Choosing the best possible set A

How do one construct a set A of smallest possible measure so that for any given set of m points we can find a \tau so that all m points belong to A+\tau \pmod 1. We start with a well-known fact about the Cantor set that covers the case m=2.

Theorem. Let A be the middle third Cantor set. Then for any two points \{x_1,x_2\} there exists a \tau so that \{x_1,x_2\} \subset A+\tau.

Can we extend this to m>2? The following result tells us that we can, not only catch m random points, but countably many points with a set A with arbitrarily small measure.

Theorem. Lad \epsilon > 0 være givet. Så findes A \subset R / Z med \mu(A) < \epsilon således at givet vilkårlig tællelig mængde X \subset R / Z findes \tau så X \subset A+\tau.

Bevis. Lad A være en åben og tæt delmængde af R / Z med m(A) < \epsilon. Skriv X = \{x_1, x_2,\dots\} og sæt d_i = x_{i+1} - x_1, i = 1, 2, \dots. Så er B = \cap_i (A - d_i) en fællesmængde af åbne tætte mængder, og da R / Z med standard metrik er fuldstændigt metrisk rum følger det af Baire's sætning at B er tæt i R / Z. Derfor findes b \in B.

Sæt nu \tau = x_1 - b. Da b \in A er x_1 = b + \tau et element af A + \tau. For vilkårlig i \in N har vi b + d_i med i A så A + \tau indeholder

Theorem. Der findes A \subset R / Z med m(A) = 0 således at givet en tællelig mængde X \subset R / Z findes \tau så X \subset A + \tau.

Bevis. Lad B_n være åbne tætte mængder med |B_n| < 1/n og sæt A = \cap_{n \in N} B_n. Fortsæt så som i beviset af sidste sætning og bemærk at en tællelig fællesmængde af tællelige fællesmængder er en tællelig fællesmængde. ■

Choosing the worst possible set A

Suppose now that your worst enemy can choose the set A under the restriction that \mu (A)=a for some given 1\ge a \ge 0. How should he choose it? How big will a have to be so that we always can be sure of catching m points? We start with the following observation.

Lemma 2. Let A \subseteq \mathbb{T}^1 be a (Lebesgue) measurable set. Suppose there exists points x_1, x_2 \in T^1 so that for all \tau \in T^1 it holds that x_1 and x_2 not simultaneous can be in A + \tau. Then m(A) \le 1/2.

Proof. Let d = x_2 - x_1 \in T^1. The sets A and A - d are disjoint. To see this, assume they are not. Then we can find u \in A \cap (A - d). Let \tau = x1 - u. Note that x_1-\tau=u \in A and x_2-\tau=d+u\in A, hence x_1, x_2 \in A + \tau which contradicts our assumption. Since A, it follows by translation invariance of the Lebesgue measure that

By Lemma 2 we have that if A is a arbitrary subset of \mathbb{T}^1 with |A| > 1/2, then there is a \tau so that \{x_1, x_2\} \subset A + \tau. Obviously, we cannot do better than 1/2, e.g., the set A=[0,1/2-\epsilon] cannot catch all pairs of points. Now one can ask how large the set A needs to be in order for us to always catch m random points. More precisely: What is the smallest length a such that any set A \subset \mathbb{T}^1 satisfying |A| \ge a or |A| > a, there exists a \tau so that \{x_1, \dots, x_m\} \subset A + \tau ?

TO-DO: Extend lemma to |A|=1/2 and to m points |A| = a > 1-1/m.

Extension to higher dimensions \mathbb{S}^n for n>1.

m points on an n-dimensional sphere. What holds here?

Literature

Vaguely related to the Bertrand paradox