{"id":26403,"date":"2017-10-26T21:53:06","date_gmt":"2017-10-26T16:23:06","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26403"},"modified":"2017-10-26T21:53:06","modified_gmt":"2017-10-26T16:23:06","slug":"expected-number-trials-success","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/expected-number-trials-success\/","title":{"rendered":"Expected Number of Trials until Success"},"content":{"rendered":"
\n

Consider the following famous puzzle.<\/h4>\n<\/header>\n
\n

In a country, all families want a boy. They keep having babies till a boy is born. What is the expected ratio of boys and girls in the country?<\/em><\/span><\/p>\n

This puzzle can be easily solved if we know following interesting result in probability and expectation.<\/p>\n

If probability of success is p in every trial, then expected number of trials until success is 1\/p<\/strong><\/p>\n

Proof:<\/strong> Let R be a random variable that indicates number of trials until success.<\/p>\n

The expected value of R is sum of following infinite series\r\nE[R] = 1*p + 2*(1-p)*p + 3*(1-p)2<\/sup>*p + 4*(1-p)3<\/sup>*p + ........ \r\n\r\nTaking 'p' out\r\nE[R] = p[1 + 2*(1-p) + 3*(1-p)2<\/sup> + 4*(1-p)3<\/sup> + .......] ---->(1)\r\n\r\nMultiplying both sides with '(1-p)' and subtracting \r\n(1-p)*E[R] = p[1*(1-p) + 2*(1-p)2<\/sup> + 3*(1-p)3<\/sup> + .......] --->(2)\r\n\r\nSubtracting (2) from (1), we get\r\n\r\np*E[R] = p[1 + (1-p) + (1-p)2<\/sup> + (1-p)3<\/sup> + ........] \r\n\r\nCanceling p from both sides\r\nE[R] = [1 + (1-p) + (1-p)2<\/sup> + (1-p)3<\/sup> + ........] \r\n\r\nAbove is an  infinite geometric  progression with ratio (1-p). \r\nSince (1-p) is less than, we can apply sum formula.\r\n  E[R] = 1\/[1 - (1-p)]\r\n       = 1\/p\r\n<\/pre>\n
Solution of Boys\/Girls ratio puzzle:<\/strong><\/em>
\nLet us use the above result to solve the puzzle. In the given puzzle, probability of success in every trial is 1\/2 (assuming that girls and boys are equally likely).<\/p>\n
Let p be probability of having a baby boy.\r\nNumber of kids until a baby boy is born = 1\/p \r\n                                        = 1\/(1\/2)\r\n                                        = 2 \r\nSince expected number of kids in a family is 2,\r\nratio of boys and girls is 50:50.<\/pre>\n
Let us discuss another problem that uses above result.<\/p>\n[ad type=”banner”]\n
Coupon Collector Problem:<\/strong>
\nSuppose there are n types of coupons in a lottery and each lot contains one coupon (with probability 1 = n each). How many lots have to be bought (in expectation) until we have at least one coupon of each type.<\/em><\/p>\n
The solution of this problem is also based on above result.<\/p>\n
Let Xi<\/sub> be the number of lots bought before i\u2019th new coupon is collected.<\/p>\n
Note that X1<\/sub> is 1 as the first coupon is always a new coupon (not collected before).<\/p>\n
Let \u2018p\u2019 be probability that 2nd coupon is collected in next buy. The value of p is (n-1)\/n. So the number of trials needed before 2nd new coupon is picked is 1\/p which means n\/(n-1). [This is where we use above result]\n
Similarly, the number of trials needed before 3rd new coupon is collected is n\/(n-2)<\/p>\n
Using Linearity of expectation<\/a>, \r\nwe can say that the total number of expected trials = \r\n                  1 + n\/(n-1) + n\/(n-2) + n\/(n-3) + .... + n\/2 + n\/1\r\n               = n[1\/n + 1\/(n-1) + 1\/(n-2) + 1\/(n-3) + ....+ 1\/2 + 1\/1]\r\n               = n * Hn<\/sub>\r\nHere Hn<\/sub> is n-th Harmonic number<\/a>\r\n\r\nSince Logn <= Hn<\/sub> <= Logn + 1, we need to buy around \r\nnLogn lots to collect all n coupons.<\/pre>\n<\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Expected Number of Trials until Success- Randomized Algorithms If probability of success is p in every trial, then expected number of trials until success.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,77748],"tags":[77945,77948,77950,77946,77943,77949,77947,77944],"class_list":["post-26403","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-randomized-algorithms","tag-expected-number-of-successes-in-n-trials","tag-expected-number-of-trials-calculator","tag-number-of-trials-in-experiment","tag-number-of-trials-to-first-success-calculator","tag-number-of-trials-until-k-successes","tag-probability-of-success-after-n-trials","tag-probability-of-success-in-n-trials","tag-probability-of-success-on-nth-trial"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26403"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26403\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}