{"id":2632,"date":"2019-04-19T16:30:47","date_gmt":"2019-04-19T21:30:47","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2632"},"modified":"2019-04-19T17:36:57","modified_gmt":"2019-04-19T22:36:57","slug":"circular-conundrum","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/circular-conundrum\/","title":{"rendered":"Circular conundrum"},"content":{"rendered":"

This week’s Riddler<\/a> problem is short and sweet:<\/p>\n

\nIf N points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points are on only one side of the newly halved circle?<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

Label the points $\\{1,2,\\dots,N\\}$. Given one of the points $i$ on the perimeter, we’ll call this point a clockwise split<\/em> if all remaining points lie on the semi-circle starting from point $i$ in the clockwise direction. For example, in the figure below, Point 1 is not<\/em> a clockwise split because Point 4 is outside the semicircle that starts at Point 1. We can also observe that Points 2 and 3 are not clockwise splits, but Point 4 is.<\/p>\n

\"\"<\/a><\/p>\n

If all $N$ points are located on the same half-circle, then exactly one of these points will be a clockwise split (almost surely<\/a>). Meanwhile, if there exists no diameter that puts all the points on the same half-circle, then no point will be a clockwise split. Define the random variable $X_i$ as follows.
\n\\[
\nX_i = \\begin{cases}1 & \\text{Point }i\\text{ is a clockwise split} \\\\ 0 & \\text{otherwise}\\end{cases}
\n\\]Based on the observations above, the probability that there exists a diameter such that all the points are one side of the newly halved circle (let’s call this probability $P$) is given by:
\n\\begin{align}
\nP &= \\text{Prob}(\\text{one of the points is a clockwise split}) \\\\
\n &= \\text{Expected total number of clockwise splits} \\\\
\n &= \\mathbb{E}\\left( \\sum_{i=1}^N X_i \\right) \\\\
\n &= \\sum_{i=1}^N \\mathbb{E}(X_i)
\n\\end{align}By symmetry, $\\mathbb{E}(X_i)$ is the same for each $i$, and it’s equal to $\\frac{1}{2^{N-1}}$, since once we’ve fixed point $i$, there are $N-1$ remaining points and each one has a probability of $\\tfrac{1}{2}$ of being in the correct half of the circle. Therefore, the probability we seek is:<\/p>\n

$\\displaystyle
\nP = \\frac{N}{2^{N-1}}
\n$<\/span><\/p>\n

The last step in the derivation relies on linearity of expectation<\/a>. Even though the $X_i$’s are not independent (far from it, since at most one of them can be $1$), linearity of expectation still holds, and it allows us to make short work of what would otherwise be a complicated calculation.<\/p>\n

Note:<\/strong> There are many ways to solve this problem. In fact, Derek commented that a previous Riddler problem<\/a> is quite similar to this one, and in his comments suggested two different ways of solving the present problem, one year ago!\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler problem is short and sweet: If N points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points are on only one side of the newly halved circle? Here is my solution: [Show Solution] Label … Continue reading “Circular conundrum”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2635,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[18,8],"class_list":["post-2632","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-linearity-of-expectation","tag-probability"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2632","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2632"}],"version-history":[{"count":8,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2632\/revisions"}],"predecessor-version":[{"id":2641,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2632\/revisions\/2641"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2635"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}