Label the points $\\{1,2,\\dots,N\\}$. Given one of the points $i$ on the perimeter, we\u2019ll 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

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\u2019s 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\u2019s equal to $\\frac{1}{2^{N-1}}$, since once we\u2019ve 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$\u2019s 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<\/p><\/div>\n

<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"

This week\u2019s 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":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t