{"id":26208,"date":"2017-10-26T20:27:20","date_gmt":"2017-10-26T14:57:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26208"},"modified":"2017-10-26T20:27:20","modified_gmt":"2017-10-26T14:57:20","slug":"linearity-of-expectation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/linearity-of-expectation\/","title":{"rendered":"Linearity of Expectation"},"content":{"rendered":"

This post is about mathematical concepts like expectation, linearity of expectation. It covers one of the required topics to understand Randomized Algorithms.<\/p>\n

Let us consider the following simple problem.<\/span><\/p>\n

Given a fair dice with 6 faces, the dice is thrown n times, find expected value of sum of all results.<\/p>\n

For example, if n = 2, there are total 36 possible outcomes.<\/p>\n

(1, 1), (1, 2), .... (1, 6)\r\n(2, 1), (2, 2), .... (2, 6)\r\n................\r\n................\r\n(6, 1), (6, 2), ..... (6, 6)<\/pre>\n
Expected value<\/strong> of a discrete random variable is R defined as following. Suppose R can take value r1<\/sub> with probability p1<\/sub>, value r2<\/sub> with probability p2<\/sub>, and so on, up to value rk<\/sub> with probability pk<\/sub>. Then the expectation of this random variable R is defined as<\/p>\n
    E[R] = r1<\/sub>*p1<\/sub> + r2<\/sub>*p2<\/sub> + ... rk<\/sub>*pk<\/sub><\/pre>\n
Let us calculate expected value for the above example.<\/p>\n
Expected Value of sum = 2*1\/36 + 3*1\/6 + .... + 7*1\/36 + \r\nof two dice throws      3*1\/36 + 4*1\/6 + .... + 8*1\/36 + \r\n                        ........................\r\n                        .........................\r\n                        7*1\/36 + 8*1\/6 + .... + 12*1\/36     \r\n                  \r\n                      =  7<\/pre>\n
The above way to solve the problem becomes difficult when there are more dice throws.<\/p>\n
If we know about linearity of expectation, then we can quickly solve the above problem for any number of throws.<\/p>\n[ad type=”banner”]\n
Linearity of Expectation:<\/a> <\/strong>Let R1<\/sub> and R2<\/sub> be two discrete random variables on some probability space, then<\/p>\n
     E[R1<\/sub> + R2<\/sub>] = E[R1<\/sub>] + E[R2<\/sub>]<\/pre>\n
Using the above formula, we can quickly solve the dice problem.<\/p>\n
Expected Value of sum of 2 dice throws = 2*(Expected value of one dice throw)\r\n                                       = 2*(1\/6 + 2\/6 + .... 6\/6)\r\n                                       = 2*7\/2\r\n                                       = 7 \r\n\r\nExpected value of sum for n dice throws is = n * 7\/2 = 3.5 * n<\/pre>\n
Some interesting facts about Linearly of Expectation:
\n1) Linearity of expectation holds for both dependent and independent events. On the other hand the rule E[R1<\/sub>R2<\/sub>] = E[R1<\/sub>]*E[R2<\/sub>] is true only for independent events.<\/p>\n
2) Linearity of expectation holds for any number of random variables on some probability space. Let R1<\/sub>, R2<\/sub>, R3<\/sub>, \u2026 Rk<\/sub> be k random variables, then
\nE[R1<\/sub> + R2<\/sub> + R3<\/sub> + \u2026 + Rk<\/sub>] = E[R1<\/sub>] + E[R2<\/sub>] + E[R3<\/sub>] + \u2026 + E[Rk<\/sub>]\n[ad type=”banner”]\n
Another example that can be easily solved with linearity of expectation:<\/strong>
\nHat-Check Problem: Let there be group of n men where every man has one hat. The hats are redistributed and every man gets a random hat back. What is the expected number of men that get their original hat back.<\/p>\n
Solution: Let Ri<\/sub> be a random variable, the value of random variable is 1 if i\u2019th man gets the same hat back, otherwise 0.<\/p>\n
So the expected number of men to get the right hat back is\r\n  = E[R1<\/sub>] + E[R2<\/sub>]  +  .. + E[Rn<\/sub>] \r\n  = P(R1<\/sub> = 1) + P(R2<\/sub> = 1) + .... + P(Rn<\/sub> = 1) \r\n  [Here P(Ri<\/sub> = 1)  indicates probability that Ri<\/sub> is 1]\r\n  = 1\/n + 1\/n + ... + 1\/n \r\n  = 1\r\n<\/pre>\n
So on average 1 person gets the right hat back.<\/p>\n
Exercise:<\/strong>
\n1) Given a fair coin, what is the expected number of heads when coin is tossed n times.<\/p>\n
2) Balls and Bins: Suppose we have m balls, labeled i = 1, \u2026 , m and n bins, labeled j = 1, .. ,n. Each ball is thrown into one of the bin independently and uniformly at random.
\na) What is the expected number of balls in every bin
\nb) What is the expected number of empty bins.<\/p>\n
3) Coupon Collector: Suppose 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.<\/p>\n
Linearity of expectation is useful in algorithms. For example, expected time complexity of random algorithms like randomized quick sort is evaluated using linearity of expectation (See this <\/a>for reference).<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Linearity of Expectation Randomized Algorithms – This post is about mathematical concepts like expectation linearity of expectation It covers  required topic<\/p>\n","protected":false},"author":1,"featured_media":26215,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,83617],"tags":[77843,77836,77839,77840,77842,77837,77829,77835,77833,77828,77827,77832,77830,77834,77838,77831,77841],"class_list":["post-26208","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-coding","category-randomized-algorithms-2","tag-expectation-of-indicator-random-variable","tag-expectation-of-sum-is-sum-of-expectation","tag-expectation-of-sum-of-dependent-random-variables","tag-law-of-total-expectation-proof","tag-law-of-total-expectation-proof-in-continuous-case","tag-linearity-of-conditional-expectation","tag-linearity-of-expectation-dependent","tag-linearity-of-expectation-examples","tag-linearity-of-expectation-khan-academy","tag-linearity-of-expectation-problems","tag-linearity-of-expectation-proof","tag-linearity-of-expectation-proof-continuous","tag-linearity-of-expectation-variance","tag-linearity-of-expectation-wiki","tag-linearity-of-expectation-wikipedia","tag-linearity-of-variance","tag-properties-of-expectation-of-a-random-variable"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26208","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=26208"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26208\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/26215"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
See following for solution of Coupon Collector.
\nExpected Number of Trials until Success<\/a><\/p>\n