MathForum.MathForum History
Show minor edits - Show changes to output
Added lines 103-117:
----
[[#nD]]
!! Extension to higher dimensions {$\mathbb{S}^n$} for n>1.
''{$m$} points on an {$n$}-dimensional sphere''. What holds here?
----
[[#ref]]
!! Literature
Vaguely related to the [[http://en.wikipedia.org/w/index.php?title=Bertrand_paradox_%28probability%29 | Bertrand paradox]]
Changed lines 88-102 from:
----
to:
----
[[#worst]]
!! 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
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. ■ $$}
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$}.
[[#worst]]
!! 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
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. ■ $$}
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$}.
Added lines 62-88:
[[#best]]
!! 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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
■
'''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 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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
■
'''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.
■
----
Added lines 49-61:
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
{$$ P_A(m) = P_B(m) \text{ for all } m \in \mathbb{N}_0. $$}
''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)$}.
■
----
Added lines 34-48:
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
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod{\frac1n} $$}
Added lines 19-33:
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
{$$ H = \{(x_1,\dots,x_m)\in \mathbb{T}^m \,\vert\, \exists \tau \text{ s.t. } x_j \in A+\tau \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
'''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$}.
Deleted lines 18-122:
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
{$$ H = \{(x_1,\dots,x_m)\in \mathbb{T}^m \,\vert\, \exists \tau \text{ s.t. } x_j \in A+\tau \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
'''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
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod{\frac1n} $$}
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
{$$ P_A(m) = P_B(m) \text{ for all } m \in \mathbb{N}_0. $$}
''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)$}.
■
----
[[#best]]
!! 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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
■
'''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.
■
----
[[#worst]]
!! 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
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. ■ $$}
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$}.
----
[[#nD]]
!! Extension to higher dimensions {$\mathbb{S}^n$} for n>1.
''{$m$} points on an {$n$}-dimensional sphere''. What holds here?
----
[[#ref]]
!! Literature
Vaguely related to the [[http://en.wikipedia.org/w/index.php?title=Bertrand_paradox_%28probability%29 | Bertrand paradox]]
>>comment<<
Det er klart at a=1 er en løsning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo både med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] dækker 3 equidistante punkter.
>><<
Changed line 50 from:
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.
to:
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.
Changed lines 73-80 from:
'''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 Avæ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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
''Bevis''. Lad A
{$b + d_i$} med i {$A$}
to:
'''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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
''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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
Changed lines 83-85 from:
'''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.
''Bevis''. Lad {$B_n$}
to:
'''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.
''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.
Changed line 122 from:
Det er klart at a=1 er en loesning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo baade med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] daekker 3 equidistante punkter.
to:
Det er klart at a=1 er en løsning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo både med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] dækker 3 equidistante punkter.
Changed line 122 from:
Det er klart at a=1 er en løsning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo både med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] dækker 3 equidistante punkter.
to:
Det er klart at a=1 er en loesning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo baade med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] daekker 3 equidistante punkter.
Changed line 85 from:
''Bevis''. Lad {$B_n$} være åbne tætte mængder med {$|B_n| < 1/n$} og sæt {$A = \cap 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.
to:
''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.
Changed line 79 from:
{$b + d_i$} med i {$A$} så {$A + \tau$} indeholder {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}$$}.
to:
{$b + d_i$} med i {$A$} så {$A + \tau$} indeholder {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.$$}
Changed lines 78-80 from:
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 b + d_i + tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.
Altså er x_i in A + tau for alle i = 1, 2, 3,...
b + d_i med i A så A + tau indeholder b + d_i + tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.
Altså er x_i in A + tau for alle i = 1, 2, 3,
to:
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 {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}$$}.
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
■
{$b + d_i$} med i {$A$} så {$A + \tau$} indeholder {$$b + d_i + \tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}$$}.
Altså er {$x_i \in A + \tau$} for alle {$i = 1, 2, 3, \dots$}
■
Added lines 83-86:
'''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 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.
■
''Bevis''. Lad {$B_n$} være åbne tætte mængder med {$|B_n| < 1/n$} og sæt {$A = \cap 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.
■
Added lines 65-66:
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$}.
Changed lines 68-82 from:
'''TO-DO:''' Construct a set {$A$} of smallest possible measure (zero?) 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$}. Start with {$m=2$}.
to:
'''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 b + d_i + tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.
Altså er x_i in A + tau for alle i = 1, 2, 3, ...
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 b + d_i + tau = b + (x_{i+1} - x_1) + x_1 - b = x_{i+1}.
Altså er x_i in A + tau for alle i = 1, 2, 3, ...
Changed line 57 from:
''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 a 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)$}.
to:
''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)$}.
Changed lines 57-58 from:
''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 a 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)$} is identical to the {$$}-probability of {$X_1,\dots,X_n \in nA_0$} for i.i.d. {$X_1,\dots,X_m \in U([0,1])$}, that is, {$P_{nA_0}(m)$}
to:
''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 a 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)$}.
■
■
Changed lines 48-49 from:
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod \frac1n $$}
to:
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod{\frac1n} $$}
Changed lines 57-60 from:
''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 a probability measure on {$M$}.
to:
''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 a 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)$} is identical to the {$\mu$}-probability of {$X_1,\dots,X_n \in nA_0$} for i.i.d. {$X_1,\dots,X_m \in U([0,1])$}, that is, {$P_{nA_0}(m)$}
Changed lines 50-51 from:
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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
to:
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.
Changed line 57 from:
''Proof''. TO-DO
to:
''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 a probability measure on {$M$}.
Changed line 54 from:
'''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$}. If {$|A| =|B| = n |A_0| $}, then
to:
'''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
Changed lines 54-55 from:
'''Lemma 1'''. Let {$A_0 \subset T^1$} be given. Define {$A=\cup_{l=0}^{n-1} \pmod 1$} and {$B=nA_0$}
to:
'''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$}. If {$|A| =|B| = n |A_0| $}, then
{$$ P_A(m) = P_B(m) \text{ for all } m \in \mathbb{N}_0. $$}
''Proof''. TO-DO
{$$ P_A(m) = P_B(m) \text{ for all } m \in \mathbb{N}_0. $$}
''Proof''. TO-DO
Changed line 50 from:
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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
to:
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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
Changed lines 45-50 from:
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 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 {$B=B+k/n \pmod 1$} for all {$k=1,\dots,n-1$}, then
{$$ \{x_i\} \subsetB + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset B + \tau \pmod \frac1n $$}
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 oflength {$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 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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
'''Remark 1'''
{$$ \{x_i\} \subset
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
to:
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
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod \frac1n $$}
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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
The following result shows that sets with "similar" symmetry properties have the same covering probabilities.
'''Lemma 1'''. Let {$A_0 \subset T^1$} be given. Define {$A=\cup_{l=0}^{n-1} \pmod 1$} and {$B=nA_0$}
'''Remark 1'''. Let {$n \in \mathbb{N}$} be given. If {$A=A+k/n \pmod 1$} for all {$k=1,\dots,n-1$}, then
{$$ \{x_i\} \subset A + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset A + \tau \pmod \frac1n $$}
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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
The following result shows that sets with "similar" symmetry properties have the same covering probabilities.
'''Lemma 1'''. Let {$A_0 \subset T^1$} be given. Define {$A=\cup_{l=0}^{n-1} \pmod 1$} and {$B=nA_0$}
Changed line 50 from:
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 length {$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 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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
to:
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 length {$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 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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
Changed lines 50-51 from:
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 length {$1/3$}. By Remark 1, {$P_A(m)=P_B(m)=m (1/3)^{m-1}$}, hence in paricular, the probability of catching two random points 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$}.
The "symmetry" condition {$B=B+k/n \pmod 1$} is necessary, in the sense,
to:
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 length {$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 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 [0,1/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$} does ''not'' satisfy the "symmetry" condition {$C=C+k/n \pmod 1$} from Remark 1.
Added lines 50-51:
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 length {$1/3$}. By Remark 1, {$P_A(m)=P_B(m)=m (1/3)^{m-1}$}, hence in paricular, the probability of catching two random points 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$}.
The "symmetry" condition {$B=B+k/n \pmod 1$} is necessary, in the sense,
The "symmetry" condition {$B=B+k/n \pmod 1$} is necessary, in the sense,
Added lines 46-49:
'''Remark 1''': Let {$n \in \mathbb{N}$} be given. If {$B=B+k/n \pmod 1$} for all {$k=1,\dots,n-1$}, then
{$$ \{x_i\} \subset B + \tau \pmod 1 \Leftrightarrow \{x_i\} \subset B + \tau \pmod \frac1n $$}
Changed line 45 from:
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''. We might wonder whether one arrives at the same probability if {$A$} consists of two quarter-circles. If the quarter-circles diametrically opposite, e.g., {$A=[0,1/4) \cup [1/2,3/4)$}
to:
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 diametrically opposite, e.g., {$A=[0,1/4) \cup [1/2,3/4)$} this is indeed the case. It follows from the following observation:
Changed line 45 from:
By Theorem 1 we have 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''. We might wonder whether one arrives at the same probability if {$A$} consists of two quarter-circles. If the quarter-circles diametrically opposite, e.g., {$A=[0,1/4) \cup [1/2,3/4)$}
to:
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''. We might wonder whether one arrives at the same probability if {$A$} consists of two quarter-circles. If the quarter-circles diametrically opposite, e.g., {$A=[0,1/4) \cup [1/2,3/4)$}
Changed line 20 from:
To be more precise we need some notation. We identify {$\mathbb{S}^1$} with {$\mathbb{T}^1=\mathbb{R}/\mathbb{Z}$}. 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
to:
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
Changed line 45 from:
By Theorem 1 we have 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''.
to:
By Theorem 1 we have 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''. We might wonder whether one arrives at the same probability if {$A$} consists of two quarter-circles. If the quarter-circles diametrically opposite, e.g., {$A=[0,1/4) \cup [1/2,3/4)$}
Changed lines 24-25 from:
'''Theorem'''. If {$a \le 1/2$}, then {$P_A(m)=m a^{m-1}$} for all {$m=1,2,\dots$}.
to:
'''Theorem 1'''. If {$a \le 1/2$}, then {$P_A(m)=m a^{m-1}$} for all {$m=1,2,\dots$}.
Added lines 44-45:
By Theorem 1 we have 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''.
Changed lines 63-66 from:
By the lemma 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$}, 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 {$P=1-1/m$}.
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$}
'''TO-DO:''' Extend lemma to {
to:
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$}.
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$}.
Changed line 20 from:
To be more precise we need some notation. We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. 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
to:
To be more precise we need some notation. We identify {$\mathbb{S}^1$} with {$\mathbb{T}^1=\mathbb{R}/\mathbb{Z}$}. 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
Changed lines 22-23 from:
{$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in A+\tau=[\tau,\tau+a) \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
to:
{$$ H = \{(x_1,\dots,x_m)\in \mathbb{T}^m \,\vert\, \exists \tau \text{ s.t. } x_j \in A+\tau \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
Changed lines 36-38 from:
{$(x)\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.
and {$x_i
to:
{$(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.
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.
Changed line 40 from:
{$P(X_1, ..., X_m \in H) = \sum P(H_k) = m a^{m-1}$}.
to:
{$P((X_1, ..., X_m) \in H) = \sum P(H_k) = m a^{m-1}$}.
Changed line 58 from:
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \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$}.
to:
'''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$}.
Changed line 63 from:
By the lemma we have that if {$A$} is a arbitrary subset of {$\mathbb{T}^1$} with {$|A| \ge 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
to:
By the lemma 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
Changed line 58 from:
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \mathbb{T}^1 $} be a (Lebesgue) measurable set. Suppose there exists points {$x1, x2 \in T^1$} so that for all {$\tau \in T^1$} it holds that {$x1$} and {$x2$} not simultaneous can be in {$A + \tau$}. Then {$m(A) \le 1/2$}.
to:
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \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$}.
Changed line 18 from:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc 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:
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$}.
Deleted lines 80-84:
!! Misc./Notes
Christian: Ikke-lig-med tegn kan laves således:
{$a\not=b \neq b$}
Changed line 22 from:
{$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in [\tau,\tau+a) \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
to:
{$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in A+\tau=[\tau,\tau+a) \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
Changed line 21 from:
{$P_m(a) = P\{(X_1, X_2, ..., X_m) \in H\}$}, where we set
to:
{$P_A(m) = P\{(X_1, X_2, ..., X_m) \in H\}$}, where we set
Changed lines 24-25 from:
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=1,2,\dots$}.
to:
'''Theorem'''. If {$a \le 1/2$}, then {$P_A(m)=m a^{m-1}$} for all {$m=1,2,\dots$}.
Changed line 32 from:
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
to:
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
Changed line 60 from:
''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
to:
''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
Changed lines 18-19 from:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc 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:
We consider a generalized version of Question 1. We want to find the probability {$P(m)=P_a(m)$} that {$m$} points falls within an arc 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$}.
Changed line 22 from:
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}, that is,
to:
'''Theorem 1'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}, that is,
Changed lines 32-34 from:
'''TO-DO:''' Extend this argument to the case {$a>1/2$}.
to:
'''TO-DO:''' Extend this argument to the case {$a>1/2$} and to (symmetric) unions of intervals.
'''Example 1'''. If {$A=[0,1/6) \cup [2/6,3/6)$}, then the (extension) of Theorem 1 tells us that {$P(2)=2 (1/3)^1 = 2/3$}. However, if we change {$A$} to a non-symmetric version, e.g., {$A=[0,1/6) \cup [2/6,3/6)$}, then {$P(2)=1$}. Hence, Theorem 1 cannot be extended to non-symmetric sets.
'''Example 1'''. If {$A=[0,1/6) \cup [2/6,3/6)$}, then the (extension) of Theorem 1 tells us that {$P(2)=2 (1/3)^1 = 2/3$}. However, if we change {$A$} to a non-symmetric version, e.g., {$A=[0,1/6) \cup [2/6,3/6)$}, then {$P(2)=1$}. Hence, Theorem 1 cannot be extended to non-symmetric sets.
Changed line 55 from:
'''TO-DO:''' Prove P=1-1/m.
to:
'''TO-DO:''' Extend lemma to {$|A|=1/2$} and to {$m$} points {$P=1-1/m$}.
Changed lines 47-48 from:
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \mathbb{T}^1 $} be a (Lebesgue) measurable set. Suppose there exists points {$x1, x2 \in T^1$} so that for all {$tau \in T^1$} it holds that {$x1$} and {$x2$} not simultaneous can be in {$A + \tau$}. Then {$m(A) \le 1/2$}.
to:
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \mathbb{T}^1 $} be a (Lebesgue) measurable set. Suppose there exists points {$x1, x2 \in T^1$} so that for all {$\tau \in T^1$} it holds that {$x1$} and {$x2$} not simultaneous can be in {$A + \tau$}. Then {$m(A) \le 1/2$}.
Changed line 52 from:
By the lemma we have that if {$A$} is a arbitrary subset of {$\mathbb{T}^1$} with {$|A| \ge 1/2$}, then there is a {$\tau$} so that {$x1, x2 \in 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
to:
By the lemma we have that if {$A$} is a arbitrary subset of {$\mathbb{T}^1$} with {$|A| \ge 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
Changed line 5 from:
! On the probability of catching {$m$} random points with a given subset of the unit circle
to:
! On the probability of covering {$m$} random points with a given subset of the unit circle
Added line 36:
[[#best]]
Added line 43:
[[#best]]
Added line 59:
[[#nD]]
Added line 66:
[[#ref]]
Changed lines 43-44 from:
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.
to:
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.
Changed line 59 from:
''{$m$} on an {$n$}-dimensional sphere''. What holds here?
to:
''{$m$} points on an {$n$}-dimensional sphere''. What holds here?
Changed lines 48-49 from:
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. $$} ■
to:
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. ■ $$}
Added lines 60-65:
----
!! Literature
Vaguely related to the [[http://en.wikipedia.org/w/index.php?title=Bertrand_paradox_%28probability%29 | Bertrand paradox]]
Changed lines 18-19 from:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc 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$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
to:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc 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$}.
Changed lines 55-59 from:
- will be updated soon -
to:
----
!! Extension to higher dimensions {$\mathbb{S}^n$} for n>1.
''{$m$} on an {$n$}-dimensional sphere''. What holds here?
!! Extension to higher dimensions {$\mathbb{S}^n$} for n>1.
''{$m$} on an {$n$}-dimensional sphere''. What holds here?
Changed lines 51-56 from:
Nu kan man spørge om hvor stor mængden A skal være før at vi altid kan fange m punkter. Mere præcist:
Hvor lille kan man vælge a således at for en vilkårlig mængde A
to:
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$}, there exists a {$\tau$} so that {$ \{x_1, \dots, x_m\} \subset A + \tau $}?
'''TO-DO:''' Prove P=1-1/m.
- will be updated soon -
>>comment<<
'''TO-DO:''' Prove P=1-1/m.
- will be updated soon -
>>comment<<
Changed lines 59-60 from:
to:
>><<
Changed lines 30-31 from:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}.
to:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. ■
Changed lines 48-50 from:
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. $$}
Så nu ved vi at hvis A er en vilkårlig delmængde af T^1 med |A|ge 1/2, så eksisterer der et \tau så {x1, x2} \subset A + \tau. Det er åbenlyst at vi ikke kan gøre det bedre end 1/2, fx, vil A=[0,1/2-\epsilon] ikke kunne fange alle par af punkter. Nu kan man spørge om hvor stor mængden A skal være før at vi altid kan fange m punkter. Mere præcist:
Så nu ved vi at hvis A er en vilkårlig delmængde af T^1 med |A|
to:
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. $$} ■
By the lemma we have that if {$A$} is a arbitrary subset of {$\mathbb{T}^1$} with {$|A| \ge 1/2$}, then there is a {$\tau$} so that {$x1, x2 \in 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
Nu kan man spørge om hvor stor mængden A skal være før at vi altid kan fange m punkter. Mere præcist:
By the lemma we have that if {$A$} is a arbitrary subset of {$\mathbb{T}^1$} with {$|A| \ge 1/2$}, then there is a {$\tau$} so that {$x1, x2 \in 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
Nu kan man spørge om hvor stor mængden A skal være før at vi altid kan fange m punkter. Mere præcist:
Changed lines 38-39 from:
'''TO-DO:''' Construct a set {$A$} of smallest possible measure (zero?) 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$}. Start with {$m=2$}.
to:
'''TO-DO:''' Construct a set {$A$} of smallest possible measure (zero?) 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$}. Start with {$m=2$}.
Changed lines 43-44 from:
Suppose now that your worst enemy can choose the set {$A$} under the restriction that {$ \mu(A)=a $} for some given {$1\le a \le 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.
to:
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.
Changed lines 47-48 from:
''Proof''. Let {$d = x_2 - x_1 \in T^1$}. Der må gælde at {$A$} og {$A - d$} er disjunkte, for ellers findes {$u \in A \cap (A - d)$}, vi kan sætte {$tau = x1 - u$} og bemærker at både {$x1$} og {$x2$} ligger i {$A + \tau$}. Da de to mængder er disjunkte og Lebesgue målet er translationsinvariant har vi
{$$2 m(A) = m(A) + m(A - d) <= m(T^1) = 1 $$}
{$$2 m(A) = m(
to:
''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
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. $$}
{$$2 m(A) = m(A) + m(A - d) \le m(\mathbb{T}^1) = 1. $$}
Changed line 27 from:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) \in H $}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$ \mathbb{S}^1 $}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}. \\
to:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) \in H $}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$ \mathbb{S}^1 $}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}.
Added lines 34-35:
----
Added lines 40-41:
----
Changed lines 43-47 from:
Suppose now that your worst enemy can choose the set {$A$} under the restriction that {$ \mu(A)=a $} for some given {$1\le a \le 0$}. How should he choose it? How big will {$a$} have to be so that we always can be sure of catching {$m$} points?
'''Lemma'''. Lad {$A \subseteq T^1 := R / Z} være en (Lebesgue) målelig mængde. Hvis der findes punkter {$x1, x2 \in T^1$} så til alle {$tau \in T^1$} gælder at ikke både {$x1$} og {$x2$} er indeholdt i {$A + \tau$, da er {$m(A) <= 1/2$}.
Bevis. Sætd = x2 - x1 \in T^1$}. Der må gælde at {$A$} og {$A - d$} er disjunkte, for ellers findes {$u \in A \cap (A - d)$}, vi kan sætte {$tau = x1 - u$} og bemærker at både {$x1$} og {$x2$} ligger i {$A + \tau$}. Da de to mængder er disjunkte og Lebesgue målet er translationsinvariant har vi
'''Lemma'''. Lad {$A \subseteq T^1 := R / Z
Bevis. Sæt
to:
Suppose now that your worst enemy can choose the set {$A$} under the restriction that {$ \mu(A)=a $} for some given {$1\le a \le 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'''. Let {$A \subseteq \mathbb{S}^1 \cong \mathbb{T}^1 $} be a (Lebesgue) measurable set. Suppose there exists points {$x1, x2 \in T^1$} so that for all {$tau \in T^1$} it holds that {$x1$} and {$x2$} not simultaneous can be in {$A + \tau$}. Then {$m(A) \le 1/2$}.
''Proof''. Let {$d = x_2 - x_1 \in T^1$}. Der må gælde at {$A$} og {$A - d$} er disjunkte, for ellers findes {$u \in A \cap (A - d)$}, vi kan sætte {$tau = x1 - u$} og bemærker at både {$x1$} og {$x2$} ligger i {$A + \tau$}. Da de to mængder er disjunkte og Lebesgue målet er translationsinvariant har vi
'''Lemma'''. Let {$A \subseteq \mathbb{S}^1 \cong \mathbb{T}^1 $} be a (Lebesgue) measurable set. Suppose there exists points {$x1, x2 \in T^1$} so that for all {$tau \in T^1$} it holds that {$x1$} and {$x2$} not simultaneous can be in {$A + \tau$}. Then {$m(A) \le 1/2$}.
''Proof''. Let {$d = x_2 - x_1 \in T^1$}. Der må gælde at {$A$} og {$A - d$} er disjunkte, for ellers findes {$u \in A \cap (A - d)$}, vi kan sætte {$tau = x1 - u$} og bemærker at både {$x1$} og {$x2$} ligger i {$A + \tau$}. Da de to mængder er disjunkte og Lebesgue målet er translationsinvariant har vi
Changed line 29 from:
{$$P((X_1, \dots, X_m) \in H) = \sum_k P((X_1, ..., X_m) \in H_k).$}
to:
{$$P((X_1, \dots, X_m) \in H) = \sum_k P((X_1, ..., X_m) \in H_k).$$}
Changed lines 27-28 from:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) \in H $}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$ \mathbb{S}^1 $}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}.
to:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) \in H $}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$ \mathbb{S}^1 $}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}. \\
Changed lines 30-33 from:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\box$}
TO-DO: Extend this argument to the case {$a>1/2$}.
TO-DO: Extend this argument to the case {$a>1/2$}.
to:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}.
'''TO-DO:''' Extend this argument to the case {$a>1/2$}.
'''TO-DO:''' Extend this argument to the case {$a>1/2$}.
Changed lines 36-38 from:
TO-DO: Construct a set {$A$} of smallest possible measure (zero?) so that for any given set of {$m$} points we can find a $\tau$ so that
to:
'''TO-DO:''' Construct a set {$A$} of smallest possible measure (zero?) 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$}. Start with {$m=2$}.
!! 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\le a \le 0$}. How should he choose it? How big will {$a$} have to be so that we always can be sure of catching {$m$} points?
!! 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\le a \le 0$}. How should he choose it? How big will {$a$} have to be so that we always can be sure of catching {$m$} points?
Changed line 31 from:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\Box$}
to:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\box$}
Changed line 31 from:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\qed$}
to:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\Box$}
Changed lines 14-15 from:
to:
----
Changed lines 31-38 from:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}.
Hvis a > 1/2 er H_k'erne ikke disjunkte og
P((X_, ..., X_n) \in H) < \sum_k P((X_1, ..., X_n) \in H_K), så
P_a(n) < n a^{n-1} .
I dette tilfælde ser problemet sværere ud...
Hvis a > 1/2 er H_k'erne ikke disjunkte og
P((X_
P_a(n) < n a^{n-1} .
I dette tilfælde ser problemet sværere ud...
to:
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}. {$\qed$}
TO-DO: Extend this argument to the case {$a>1/2$}.
!! Choosing the best possible set {$A$}
TO-DO: Construct a set {$A$} of smallest possible measure (zero?) so that for any given set of {$m$} points we can find a $\tau$ so that
!!
TO-DO: Extend this argument to the case {$a>1/2$}.
!! Choosing the best possible set {$A$}
TO-DO: Construct a set {$A$} of smallest possible measure (zero?) so that for any given set of {$m$} points we can find a $\tau$ so that
!!
Changed line 27 from:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) in H$}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$\mathbb{S}^1$}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}.
to:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) \in H $}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$ \mathbb{S}^1 $}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}.
Changed line 20 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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] $}.
Changed lines 18-19 from:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc of length {$a$} of \mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
to:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc 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$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
Changed lines 29-34 from:
P((X_1,
P(
Og da vi summerer over n ens termer får vi
P_
to:
The sets {$H_k$} are disjoint if (and only if) {$a \le 1/2$}. Hence,
{$$P((X_1, \dots, X_m) \in H) = \sum_k P((X_1, ..., X_m) \in H_k).$}
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}.
{$$P((X_1, \dots, X_m) \in H) = \sum_k P((X_1, ..., X_m) \in H_k).$}
Since {$(X_1, \dots, X_m)$} are i.i.d. uniformly, we have that {$P(X_1, ..., X_m) = a^{m-1}$}. By the above equation, we arrive at {$P_a(m) = m a^{m-1}$}.
Changed lines 27-30 from:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) in H$}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive
for if r hvis der findesså (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
for if r hvis der findes
to:
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) in H$}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive direction on {$\mathbb{S}^1$}. Now, clearly {$x=(x_j) \in H_k$}. On the other hand, if there exists a {$k$} so that {$(x_j) \in H_k$}, then pick {$K=x_k$} and hence {$x=(x_j) \in H_k$}.
Changed lines 26-29 from:
For k = 1, ..., n, sæt
H_k = {x_1, x_2, ..., x_n | x_j \in [x_k; x_k modulo 1, j = 1, ..., n} . Det er klart at der gælder
H = \cup_k H_k
for hvis der findes k så (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
for
to:
For {$k = 1, \dots, n$} define
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) in H$}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive
for if r hvis der findes k så (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
{$ H_k = \{x_1, x_2, \dots, x_n \,\vert\, x_j \in [x_k, x_k + a[ \pmod 1, j = 1, ..., n\} $}. We claim that {$ H = \cup_k H_k $}. To see this claim note that if {$x = (x_j) in H$}, then pick the first {$x_k$} after {$K$} (w.r.t. the positive
for if r hvis der findes k så (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
Changed lines 18-19 from:
We consider a generalized version of Question 1. We want to find the probability {$P(m)=P_a(m)$} that {$m$} points falls within an arc of length {$a$} of {$\mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
to:
We consider a generalized version of Question 1. We want to find the probability {$P_a(m)$} that {$m$} points falls within an arc of length {$a$} of {$\mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
Added lines 26-41:
For k = 1, ..., n, sæt
H_k = {x_1, x_2, ..., x_n | x_j \in [x_k; x_k + a[ modulo 1, j = 1, ..., n} . Det er klart at der gælder
H = \cup_k H_k
for hvis der findes k så (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
Hvis (og kun hvis) a <= 1/2 gælder at mængderne H_k er parvis disjunkte. Derfor har vi
P((X_1, ..., X_n) \in H) = \sum_k P((X_1, ..., X_n) \in H_k).
Pga uniform fordeling og uafhængighed gælder
P(X_1, ..., X_n) = a^{n-1}
Og da vi summerer over n ens termer får vi
P_a(n) = n a^{n-1} .
Hvis a > 1/2 er H_k'erne ikke disjunkte og
P((X_1, ..., X_n) \in H) < \sum_k P((X_1, ..., X_n) \in H_K), så
P_a(n) < n a^{n-1} .
I dette tilfælde ser problemet sværere ud...
H_k = {x_1, x_2, ..., x_n | x_j \in [x_k; x_k + a[ modulo 1, j = 1, ..., n} . Det er klart at der gælder
H = \cup_k H_k
for hvis der findes k så (x_j) \in H_k kan vi vælge K = x_k og ser (x_j) \in H . Omvendt hvis (x_j) \in H findes et (og muligvis flere) første x_k der ligger efter K eller er lig med K, med hensyn den ordning der svarer til positiv omløbsretning på cirklen. Nu er (x_j) \in H_k .
Hvis (og kun hvis) a <= 1/2 gælder at mængderne H_k er parvis disjunkte. Derfor har vi
P((X_1, ..., X_n) \in H) = \sum_k P((X_1, ..., X_n) \in H_k).
Pga uniform fordeling og uafhængighed gælder
P(X_1, ..., X_n) = a^{n-1}
Og da vi summerer over n ens termer får vi
P_a(n) = n a^{n-1} .
Hvis a > 1/2 er H_k'erne ikke disjunkte og
P((X_1, ..., X_n) \in H) < \sum_k P((X_1, ..., X_n) \in H_K), så
P_a(n) < n a^{n-1} .
I dette tilfælde ser problemet sværere ud...
Changed line 10 from:
'''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?
to:
'''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?
Deleted line 24:
Added lines 26-37:
'''Lemma'''. Lad {$A \subseteq T^1 := R / Z$} være en (Lebesgue) målelig mængde. Hvis der findes punkter {$x1, x2 \in T^1$} så til alle {$tau \in T^1$} gælder at ikke både {$x1$} og {$x2$} er indeholdt i {$A + \tau$}, da er {$m(A) <= 1/2$}.
Bevis. Sæt {$d = x2 - x1 \in T^1$}. Der må gælde at {$A$} og {$A - d$} er disjunkte, for ellers findes {$u \in A \cap (A - d)$}, vi kan sætte {$tau = x1 - u$} og bemærker at både {$x1$} og {$x2$} ligger i {$A + \tau$}. Da de to mængder er disjunkte og Lebesgue målet er translationsinvariant har vi
{$$2 m(A) = m(A) + m(A - d) <= m(T^1) = 1 $$}
Så nu ved vi at hvis A er en vilkårlig delmængde af T^1 med |A| \ge 1/2, så eksisterer der et \tau så {x1, x2} \subset A + \tau. Det er åbenlyst at vi ikke kan gøre det bedre end 1/2, fx, vil A=[0,1/2-\epsilon] ikke kunne fange alle par af punkter. Nu kan man spørge om hvor stor mængden A skal være før at vi altid kan fange m punkter. Mere præcist:
Hvor lille kan man vælge a således at for en vilkårlig mængde A \subset T^1 med |A| \ge a, så eksisterer der et \tau så {x1, ..., xm} \subset A + \tau?
Det er klart at a=1 er en løsning, men kan vi finde et mindre a? Et (vildt) gæt ville være a=1-1/m. Det passer jo både med m=1 og m=2 :). For m=3, vil så |A|=2/3, hvilket også virker rimelig i worst-case-scenario: A=[0,2/3] dækker 3 equidistante punkter.
Changed line 23 from:
{$P(\{X_1,\dots,X_m\} \in H)=m a^{m-1}$}, where {$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in [\tau,\tau+a] \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
to:
{$P((X_1,\dots,X_m) \in H)=m a^{m-1}$}, where {$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in [\tau,\tau+a] \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
Changed line 23 from:
to:
{$P(\{X_1,\dots,X_m\} \in H)=m a^{m-1}$}, where {$$ H = \{(x_1,\dots,x_m) \,\vert\, \exists \tau \text{ s.t. } x_j \in [\tau,\tau+a] \pmod 1 \text{ for all } j=1,\dots, m\}.$$}
Changed lines 28-50 from:
(:latex:)
\begin{equation}
\prod_{n=2}^N\frac{n}{n-1} = N
\end{equation}
(:latexend:)
(:latex displaycode+=true verbose=true forcerender=true paperwidth='5' ::eqncounter++:)
\begin{equation}
\prod_{n=2}^N\frac{n}{n-1} = N
\end{equation}
(:latexend:)
(:latex [DisplayCode[+] = true|false]
[Verbose = true|false]
[ForceRender = true|false]
[ClearCache = true|false]
[... template parameters ...] :)
\section{One} We identify $\mathbb{S}^1$ with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
(:latexend)
to:
- will be updated soon -
Added lines 36-42:
(:latex displaycode+=true verbose=true forcerender=true paperwidth='5' ::eqncounter++:)
\begin{equation}
\prod_{n=2}^N\frac{n}{n-1} = N
\end{equation}
(:latexend:)
Added lines 31-36:
(:latex:)
\begin{equation}
\prod_{n=2}^N\frac{n}{n-1} = N
\end{equation}
(:latexend:)
\begin{equation}
\prod_{n=2}^N\frac{n}{n-1} = N
\end{equation}
(:latexend:)
Changed lines 42-43 from:
section{One} We identify $\mathbb{S}^1$ with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
to:
\section{One} We identify $\mathbb{S}^1$ with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
Changed lines 20-25 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}.
- will be updated soon-
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}
- will be updated soon
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}, that is,
''Proof''.
- will be updated soon -
(:latex [DisplayCode[+] = true|false]
[Verbose = true|false]
[ForceRender = true|false]
[ClearCache = true|false]
[... template parameters ...] :)
section{One} We identify $\mathbb{S}^1$ with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
(:latexend)
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}, that is,
''Proof''.
- will be updated soon -
(:latex [DisplayCode[+] = true|false]
[Verbose = true|false]
[ForceRender = true|false]
[ClearCache = true|false]
[... template parameters ...] :)
section{One} We identify $\mathbb{S}^1$ with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
(:latexend)
Changed line 20 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. Let {$\{X_1, \dots, X_m \in [0,1)$} be independent and identically distributed (i.i.d.) uniformly distributed points.
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. 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]$}.
Changed line 10 from:
'''Question 2''': Let {$1 \ge a \ge 0$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
to:
'''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?
Changed line 5 from:
! On the probability of catching {$m$} random points with a subset of the unit circle
to:
! On the probability of catching {$m$} random points with a given subset of the unit circle
Changed line 5 from:
! On the probability of catching {$m$} random points on the unit circle
to:
! On the probability of catching {$m$} random points with a subset of the unit circle
Changed lines 1-2 from:
'''''Afternoon tea discussions at DTU Mathematics'''''
to:
'''''Afternoon tea discussions at DTU Mathematics''''' — discussions on non-applied mathematics.
Changed lines 20-23 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}.
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}. Let {$\{X_1, \dots, X_m \in [0,1)$} be independent and identically distributed (i.i.d.) uniformly distributed points.
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}.
'''Theorem'''. If {$a \le 1/2$}, then {$P_a(m)=m a^{m-1}$} for all {$m=0,1,\dots$}.
Changed line 20 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau (\mod 1)$}.
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau \pmod 1$}.
Changed lines 18-20 from:
We consider a generalized version of Question 1. We want to find the probability {$P(m)=P_a(m)$ that {$m$} points falls within an arc of length {$a$} of {$\mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (Lebesgue) surface measure on {$\mathbb{S}^1$}.
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists $\tau \in [0,1)$ such that the m random points belong to $A+\tau (\mod 1)$.
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists $\tau \in [0,1)$ such that the m random points belong to $A+\tau (\mod 1)$.
to:
We consider a generalized version of Question 1. We want to find the probability {$P(m)=P_a(m)$} that {$m$} points falls within an arc of length {$a$} of {$\mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (probability Lebesgue) surface measure on {$\mathbb{S}^1$}.
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau (\mod 1)$}.
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists {$\tau \in [0,1)$} such that the m random points belong to {$A+\tau (\mod 1)$}.
Changed lines 20-22 from:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}.
to:
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}. We are then asking whether there exists $\tau \in [0,1)$ such that the m random points belong to $A+\tau (\mod 1)$.
Changed lines 18-22 from:
to:
We consider a generalized version of Question 1. We want to find the probability {$P(m)=P_a(m)$ that {$m$} points falls within an arc of length {$a$} of {$\mathbb{S}^1$}, where the total length of {$\mathbb{S}^1$} is one, i.e., {$\mu(\mathbb{S}^1)=1$} with {$\mu$} being the (Lebesgue) surface measure on {$\mathbb{S}^1$}.
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}.
We are then asking
We identify {$\mathbb{S}^1$} with {$\mathbb{R}/\mathbb{Z}$}. Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}.
We are then asking
Changed line 1 from:
'''''Afternoon tea discussions at DTU Math'''''
to:
'''''Afternoon tea discussions at DTU Mathematics'''''
Changed line 5 from:
! On the probability of cacthing {$m$} random points on the unit circle
to:
! On the probability of catching {$m$} random points on the unit circle
Changed line 5 from:
! On the probability of covering {$m$} random points on the unit circle
to:
! On the probability of cacthing {$m$} random points on the unit circle
Changed line 12 from:
'''Question 2''': 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?
to:
'''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?
Changed lines 10-13 from:
'''Question 2''': Let {$1 \ge a \ge 0$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
to:
'''Question 2''': Let {$1 \ge a \ge 0$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
'''Question 2''': 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?
'''Question 2''': 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?
Changed lines 8-10 from:
'''Question 2''': Let {$0 \ge a \ge 1$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
to:
'''Question 2''': Let {$1 \ge a \ge 0$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
Changed line 13 from:
Let {$a \in \mathbb{R} $} be given such that {$0 \ge a \ge 1$}, and let {$A=[0,a)$}.
to:
Let {$a \in \mathbb{R} $} be given such that {$0 \le a \le 1$}, and let {$A=[0,a)$}.
Added lines 8-10:
'''Question 2''': Let {$0 \ge a \ge 1$}. Suppose {$A \subset \mathbb{S}^1$} is a Borel measurable set of measure {$\mu(A)=a$}. What is probability that {$A$} can cover {$m$} random points?
Added line 13:
Let {$a \in \mathbb{R} $} be given such that {$0 \ge a \ge 1$}, and let {$A=[0,a)$}.
Changed line 6 from:
'''Question 1''': If one picks {$m$} points at random on the unit circle {$\mattbb{S}^1$}, what is the probability that they can be covered by a half circle {$A \subset \mattbb{S}^1$}?
to:
'''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$}?
Changed lines 6-7 from:
'''Question 1''': If one picks {$m$} points at random on the unit circle, what is the probability that they can be covered by a half circle?
to:
'''Question 1''': If one picks {$m$} points at random on the unit circle {$\mattbb{S}^1$}, what is the probability that they can be covered by a half circle {$A \subset \mattbb{S}^1$}?
Changed line 11 from:
- will be updated soon -
to:
- will be updated soon -
Added lines 5-6:
'''Question 1''': If one picks {$m$} points at random on the unit circle, what is the probability that they can be covered by a half circle?
Changed line 1 from:
to:
'''''Afternoon tea discussions at DTU Math'''''
Changed lines 2-6 from:
to:
! On the probability of covering {$m$} random points on the unit circle
-> by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.
- will be updated soon -
-> by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.
- will be updated soon -
Changed line 2 from:
-< by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.
to:
-> by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.
Changed lines 1-2 from:
! Math Discussions
to:
! Afternoon tea discussions at DTU Math
-< by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.
-< by Christian Henriksen, Jakob Lemvig, and Johan Sebastian Rosenkilde Nielsen.