{"id":110,"date":"2022-11-04T22:02:05","date_gmt":"2022-11-04T22:02:05","guid":{"rendered":"https:\/\/blog.wordgeeks.net\/?p=110"},"modified":"2022-11-06T18:06:29","modified_gmt":"2022-11-06T18:06:29","slug":"removing-gacha-i-a-probability-problem","status":"publish","type":"post","link":"https:\/\/blog.wordgeeks.net\/?p=110","title":{"rendered":"Removing Gacha: I, a probability problem"},"content":{"rendered":"\n<p>The actual problem is <a href=\"https:\/\/atcoder.jp\/contests\/arc150\/tasks\/arc150_d\">here on atcoder<\/a>. I&#8217;ll build a solution from the bottom up. So here we go.<\/p>\n\n\n\n<p>Let&#8217;s say we have N balls (numbered 1 to N) from a box, and we do the following:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Take one ball from the box uniformly randomly\n<ul class=\"wp-block-list\">\n<li>If the ball taken has the smallest number among all the remaining balls, throw it away; otherwise put it back to the box<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>If every ball from 1 to N-1 has been taken at least once, stop; otherwise repeat step 1.<\/li>\n<\/ol>\n\n\n\n<p>And by the time the process is stopped, what&#8217;s the probability that the N-th ball has been taken at least once?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">First attempt<\/h3>\n\n\n\n<p>Since the balls are taken uniformly randomly, is it so that we are equally likely to have either taken or not taken ball N?<\/p>\n\n\n\n<p>Well, a quick simulation suggests otherwise. I&#8217;ll leave more rigorous calculations later, but intuitively, it&#8217;s similar to the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Birthday_problem\">birthday paradox<\/a>, as the probability of NOT picking ball N at each step multiplies, the overall probability of NOT picking ball N diminishes quickly. (Consider a modified version: uniformly randomly pick a ball for K times and always put the ball back, the probability of ball N NOT picked is ((N-1)\/N)^K).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">In search of an explanation with the answer<\/h3>\n\n\n\n<p>From simulation, it&#8217;s obvious the answer is (N-1)\/N.<\/p>\n\n\n\n<p>One explanation I came up with: If we change the condition &#8220;<em>If the ball taken has the smallest number among all the remaining balls, throw it away; otherwise put it back to the box<\/em>&#8221; to &#8220;<em>always put the ball back to the box<\/em>&#8220;, it doesn&#8217;t change the the probability of whether the N-th ball get picked at all. (But it does change the value of something else, which is the topic of next post.) Convince yourself: if we pick up ball 1, put it back, and later pick it up again, we can just <em>pretend<\/em> this step doesn&#8217;t happen. Then graphically:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"677\" height=\"456\" src=\"https:\/\/blog.wordgeeks.net\/wp-content\/uploads\/2022\/11\/probability-last-picked-always-put-back.png\" alt=\"\" class=\"wp-image-114\" srcset=\"https:\/\/blog.wordgeeks.net\/wp-content\/uploads\/2022\/11\/probability-last-picked-always-put-back.png 677w, https:\/\/blog.wordgeeks.net\/wp-content\/uploads\/2022\/11\/probability-last-picked-always-put-back-300x202.png 300w\" sizes=\"auto, (max-width: 677px) 100vw, 677px\" \/><\/figure>\n\n\n\n<p>Regardless of the the values on those self-pointing arrows, the <strong>ratio<\/strong> on the other two outgoing arrows stay the same, and if we go to infinity, we get the resulting probability.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">A failed algebraic approach<\/h3>\n\n\n\n<p>I also tried to solve it algebraically or with induction. But to decide the property of the N-th ball, it depends on the (N-1)-th ball, then the property of this pair depends on the (N-2)-th, then the property of this triple depends on the (N-3)-th, etc. The formula just keeps growing.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The actual problem is here on atcoder. I&#8217;ll build a solution from the bottom up. So here we go. Let&#8217;s say we have N balls (numbered 1 to N) from a box, and we do the following: And by the time the process is stopped, what&#8217;s the probability that the N-th ball has been taken&hellip; <a class=\"more-link\" href=\"https:\/\/blog.wordgeeks.net\/?p=110\">Continue reading <span class=\"screen-reader-text\">Removing Gacha: I, a probability problem<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[11,21,22,3],"class_list":["post-110","post","type-post","status-publish","format-standard","hentry","category-competitive","tag-competitive","tag-mathematics","tag-probability","tag-programming","entry"],"_links":{"self":[{"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/posts\/110","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=110"}],"version-history":[{"count":4,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/posts\/110\/revisions"}],"predecessor-version":[{"id":121,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=\/wp\/v2\/posts\/110\/revisions\/121"}],"wp:attachment":[{"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=110"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=110"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.wordgeeks.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=110"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}