{"id":3442,"date":"2022-08-20T17:12:10","date_gmt":"2022-08-20T22:12:10","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3442"},"modified":"2022-08-20T22:47:37","modified_gmt":"2022-08-21T03:47:37","slug":"pill-splitting","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/pill-splitting\/","title":{"rendered":"Pill splitting"},"content":{"rendered":"<p>his week&#8217;s <a href=\"https:\/\/fivethirtyeight.com\/features\/can-you-find-your-pills\/\">Riddler classic<\/a> is about splitting pills to get the right dose.<\/p>\n<blockquote><p>\nI\u2019ve been prescribed to take 1.5 pills of a certain medication every day for 10 days, so I have a bottle with 15 pills. Each morning, I take two pills out of the bottle at random.<\/p>\n<p>On the first morning, these are guaranteed to be two full pills. I consume one of them, split the other in half using a precision blade, consume half of that second pill, and place the remaining half back into the bottle.<\/p>\n<p>On subsequent mornings when I take out two pills, there are three possibilities:<\/p>\n<ul>\n<li> I get two full pills. As on the first morning, I split one and place the unused half back into the bottle.\n<li> I get one full pill and one half-pill, both of which I consume.\n<li> I get two half-pills. In this case, I take out another pill at random. If it\u2019s a half-pill, then I consume all three halves. But if it\u2019s a full pill, I split it and place the unused half back in the bottle.\n<\/ul>\n<p>Assume that each pill \u2014 whether it is a full pill or a half-pill \u2014 is equally likely to be taken out of the bottle.<\/p>\n<p>On the 10th day, I again take out two pills and consume them. In a rush, I immediately throw the bottle in the trash before bothering to check whether I had just consumed full pills or half-pills. What\u2019s the probability that I took the full dosage, meaning I don\u2019t have to dig through the trash for a remaining half-pill?\n<\/p><\/blockquote>\n<p>My solution:<br \/>\n<a href=\"javascript:Solution('soln_splitting_pills','toggle_splitting_pills')\" id=\"toggle_splitting_pills\">[Show Solution]<\/a><\/p>\n<div id=\"soln_splitting_pills\" style=\"display: none\">\n<p>Problems of this sort may seem tedious at first glance, but there is a simple and systematic way to approach them. We can encode the pills in the bottle using <em>polynomials<\/em>. Specifically, we&#8217;ll write $x^n y^m$ when there are $n$ full pills and $m$ half-pills. Since there is an element of randomness with how the pills are picked, we will use a weighted sum of such polynomials to describe a mixture or possible states. For example, we could write:<br \/>\n\\[<br \/>\n\\tfrac{2}{3} x y + \\tfrac{1}{3} y^3<br \/>\n\\]to describe a scenario where there is a $\\frac{2}{3}$ probability that the bottle contains one full pill and one half-pill, and a $\\frac{1}{3}$ probability that the bottle contains three half-pills. Note that the coefficients sum to $1$, so exactly one of the two scenarios must occur.<\/p>\n<p>So what happens when we take our daily dose? We can consider each scenario in turn.<\/p>\n<ul>\n<li> With probability $\\frac{\\binom{n}{2}}{\\binom{n+m}{2}}$, we will pick two full pills. In this case, we cut one in half and return half to the bottle. This means the bottle now contains $x^{n-2}y^{m+1}$.\n<li> With probability $\\frac{nm}{\\binom{n+m}{2}}$, we will pick one full pill and one half-pill. In this case, we have our exact dose and the bottle now contains $x^{n-1}y^{m-1}$.\n<li> With probability $\\frac{\\binom{m}{2}}{\\binom{n+m}{2}}$, we will pick two half-pills. In this case, we must go back into the bottle and pick one more pill. There are two sub-cases here:\n<ul>\n<li> With probability $\\frac{n}{n+m-2}$, we pick one of the full pills. So we split it in half, and return half to the bottle. The jar has now lost a total of one full pill and one half-pill, so it contains $x^{n-1}y^{m-1}$.\n<li> With probability $\\frac{m-2}{n+m-2}$, we pick one of the half-pills. So we have our exact dose and the bottle now contains $x^n y^{m-3}$.\n<\/ul>\n<\/ul>\n<p>Combining all the possible cases, we find that every day, the polynomial describing the contents of the bottle change according to the mapping<br \/>\n\\begin{multline}<br \/>\nx^n y^m \\mapsto \\tfrac{n (n-1)}{(m+n) (m+n-1)}x^{n-2} y^{m+1} + \\tfrac{m n (3 m+2 n-5)}{(m+n) (m+n-1) (m+n-2)} x^{n-1} y^{m-1} \\\\<br \/>\n+ \\tfrac{m (m-1) (m-2)}{(m+n) (m+n-1) (m+n-2)} x^n y^{m-3}<br \/>\n\\end{multline}<br \/>\nThere are two nice things about this formulation. First, edge cases are taken care of automatically. For example, if the bottle contains $n=2$ full pills and $m=2$ half-pills, the third term ($x^n y^{m-3}$) in the expansion is impossible, since the bottle does not contain three half-pills. But the associated coefficient is zero, so this term cancels automatically. Similarly, if $m=0$ (the bottle only contains full pills), two of the coefficients vanish and the third becomes $1$, so we obtain $x^n \\mapsto x^{n-2} y$.<\/p>\n<p>Second, when the bottle contains a mixture of possible states (described by a polynomial whose coefficients sum to 1), we can apply the above transformation to each term of the polynomial separately, and the final result will again be a mixture of possible states. This follows because the sum of the coefficients of the mapping above sum to 1 as well.<\/p>\n<p>To compute the mixture of states after 10 days, I wrote a Mathematica script that starts at $x^{15}$ (15 full pills) and applies the above transformation recursively. Here is the Mathematica script:<\/p>\n<pre>\r\nP = x^15; (* initial polynomial *)\r\nPrint[P];\r\nFor[iter = 0, iter < 9, iter++,\r\n  Q = 0;\r\n  ML = MonomialList[P];\r\n  For[i = 1, i <= Length[ML], i++,\r\n    term = ML[[i]];\r\n    coef = term \/. {x -> 1, y -> 1};\r\n    n = Exponent[ term, x];\r\n    m = Exponent[term, y];\r\n    Q = Q + coef ((m(m-1)(m-2))\/((n+m)(n+m-1)(n+m-2)) x^n y^(m-3)\r\n          + (n m(2n+3m-5))\/((n+m)(n+m-1)(n+m-2)) x^(n-1) y^(m-1)\r\n          + (n(n-1))\/((n+m)(n+m-1)) x^(n-2) y^(m+1));\r\n   ];\r\n   P = Q \/\/ Expand;\r\n   Print[P];\r\n]\r\n<\/pre>\n<p>and here is the output from the script:<br \/>\n\\begin{gather}<br \/>\nx^{15} \\\\<br \/>\nx^{13} y\\\\<br \/>\n\\tfrac{1}{7}x^{12}+\\tfrac{6 }{7}x^{11} y^2\\\\<br \/>\n\\tfrac{36 }{91}x^{10} y+\\tfrac{55 }{91}x^9 y^3\\\\<br \/>\n\\tfrac{23 }{308}x^9+\\tfrac{2385}{4004} x^8 y^2+\\tfrac{30}{91} x^7 y^4\\\\<br \/>\n\\tfrac{4 }{13}x^7 y+\\tfrac{81}{143} x^6 y^3+\\tfrac{18}{143} x^5 y^5\\\\<br \/>\n\\tfrac{335}{4004} x^6+\\tfrac{87}{154} x^5 y^2+\\tfrac{185}{572} x^4 y^4+\\tfrac{4}{143} x^3 y^6\\\\<br \/>\n\\tfrac{22573}{56056} x^4 y+\\tfrac{42605}{84084} x^3 y^3+\\tfrac{101}{1144} x^2 y^5+\\tfrac{1}{429}x y^7\\\\<br \/>\n\\tfrac{44783}{240240} x^3+\\tfrac{362603}{560560} x^2 y^2+\\tfrac{27185}{168168} x y^4 + \\tfrac{61}{12012} y^6\\\\<br \/>\n\\tfrac{80529}{101920} x y+\\tfrac{21391}{101920} y^3\\\\<br \/>\n\\end{gather}<\/p>\n<p>Therefore, on the $10^\\text{th}$ day, there is a $\\tfrac{21391}{101920} \\approx 20.988\\%$ chance the bottle contains three half-pills, and a $\\tfrac{80529}{101920} \\approx 79.012\\%$ chance the bottle contains one full pill and one half-pill. This is the probability that the correct dosage was taken, which is what is asked in the original problem statement.<\/p>\n<h3>Large-pill limit<\/h3>\n<p>We saw that on the final day, the probability that the bottle contains one full pill and one half-pill is about $79\\%$. A natural question to ask is: what happens to this probability as we vary the number of starting pills? If we start with only 3 pills, then we <em>always<\/em> have one full pill and one half-pill on the next day. So the probability is $100\\%$. Here is a plot of what happens as we vary the number of initial pills:<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting.png\" alt=\"\" width=\"1315\" height=\"845\" class=\"aligncenter size-full wp-image-3457\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting.png 1315w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting-300x193.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting-1024x658.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting-768x494.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/08\/pill-splitting-1200x771.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>It appears that as we increase the number of initial pills, the probability of having one full pill and one half-pill on the last day decreases. I don&#8217;t have a great explanation for why this happens; if you made it this far and have any ideas, write a comment; I would love to hear it!<\/p>\n<h3>Generating functions?<\/h3>\n<p>I am well aware that the polynomials I used look a lot like <a href=\"https:\/\/en.wikipedia.org\/wiki\/Generating_function\">generating functions<\/a>. I looked for a nice way to express the pill-taking transformation as a differential operator acting on the generating function, but I was thwarted by the denominators. The numerators are easy, e.g.<br \/>\n\\[<br \/>\n\\tfrac{\\mathrm{d}^3}{\\mathrm{d}y^3}(x^n y^m) =  m(m-1)(m-2) x^n y^{m-3}<br \/>\n\\]but I couldn&#8217;t find a nice way to deal with the denominators. For the case above, the denominator should be $(n+m)(n+m-1)(n+m-2)$. If anybody found a way to solve this using the full generating function machinery, I would love to hear about it!\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>his week&#8217;s Riddler classic is about splitting pills to get the right dose. I\u2019ve been prescribed to take 1.5 pills of a certain medication every day for 10 days, so I have a bottle with 15 pills. Each morning, I take two pills out of the bottle at random. On the first morning, these are &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/pill-splitting\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Pill splitting&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3457,"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":[8,15,2],"class_list":["post-3442","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3442","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=3442"}],"version-history":[{"count":21,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3442\/revisions"}],"predecessor-version":[{"id":3465,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3442\/revisions\/3465"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3457"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}