{"id":26551,"date":"2017-12-20T21:42:49","date_gmt":"2017-12-20T16:12:49","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26551"},"modified":"2017-12-20T21:42:49","modified_gmt":"2017-12-20T16:12:49","slug":"randomized-algorithms-mathematical-background-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/randomized-algorithms-mathematical-background-2\/","title":{"rendered":"Randomized Algorithms | Set 0 (Mathematical Background)"},"content":{"rendered":"

Conditional Probability<\/strong><\/center>Conditional probability P(A | B) indicates the probability of even \u2018A\u2019 happening given that the even B happened. <\/span>
\n\"cond1\"<\/a>
\nWe can easily understand above formula using below diagram. Since B has already happened, the sample space reduces to B. So the probability of A happening becomes P(A \u2229 B) divided by P(B)<\/p>\n

\"Randomized<\/p>\n

Below is Bayes\u2019s formula<\/a> for conditional probability.
\n\"bays1\"<\/a>
\nThe formula provides relationship between P(A|B) and P(B|A). It is mainly derived form conditional probability formula discussed in the previous post<\/a>.<\/p>\n

Consider the below forrmulas for conditional probabilities P(A|B) and P(B|A)
\n\"bays\"<\/a><\/p>\n

Since P(B \u2229 A) = P(A \u2229 B), we can replace P(A \u2229 B) in first formula with P(B|A)P(A)
\nAfter replacing, we get the given formula. Refer this<\/a> for examples of Bayes\u2019s formula.<\/p>\n[ad type=”banner”]\n

Random Variables:<\/strong>
\nA random variable is actually a function that maps outcome of a random event (like coin toss) to a real value.<\/center>Example :<\/p>\n
Coin tossing game : \r\nA player pays 50 bucks if result of coin\r\ntoss is \"Head\" \r\n\r\nThe person gets 50 bucks if the result is\r\nTail. \r\n\r\nA random variable profit for person can \r\nbe defined as below : \r\n\r\nProfit = +50 if Head\r\n         -50 if Tail  \r\n\r\nGenerally gambling games are not fair for players, \r\nthe organizer takes a share of profit for all \r\narrangements. So expected profit is negative for \r\na player in gambling and positive for the organizer. \r\nThat is how organizers make money.<\/pre>\n
Expected Value of Random Variable :<\/strong>
\nExpected value of a random variable R can be defined as following<\/center><\/p>\n
    E[R] = r1*p1 + r2*p2 + ... rk*pk \r\n    \r\n    ri ==> Value of R with probability pi<\/pre>\n
Expected value is basically sum of product of following two terms (for all possible events)
\na) Probability of an event.
\nb) Value of R at that even<\/p>\n[ad type=”banner”]\n
Example 1:<\/strong>\r\nIn above example of coin toss,\r\nExpected value of profit = 50 * (1\/2) + \r\n                          (-50) * (1\/2)\r\n                         = 0\r\n\r\nExample 2:<\/strong>\r\nExpected value of six faced dice throw is \r\n  = 1*(1\/6) + 2*(1\/6) + .... + 6*(1\/6)\r\n  = 3.5<\/pre>\n
Linearity of Expectation:<\/strong>
\nLet R1<\/sub> and R2<\/sub> be two discrete random variables on some probability space, then<\/center><\/p>\n
     E[R1<\/sub> + R2<\/sub>] = E[R1<\/sub>] + E[R2<\/sub>]<\/pre>\n
For example, expected value of sum for 3 dice throws is = 3 * 7\/2 = 7<\/p>\n
Refer this for more detailed explanation and examples.<\/p>\n
Expected Number of Trials until Success<\/strong><\/center>
\nIf probability of success is p in every trial, then expected number of trials until success is 1\/p. For example, consider 6 faced fair dice is thrown until a \u20185\u2019 is seen as result of dice throw. The expected number of throws before seeing a 5 is 6. Note that 1\/6 is probability of getting a 5 in every trial. So number of trials is 1\/(1\/6) = 6.
\nAs another example, consider a QuickSort version that keeps on looking for pivots until one of the middle n\/2 elements is picked. The expected time number of trials for finding middle pivot would be 2 as probability of picking one of the middle n\/2 elements is 1\/2. This example is discussed in more detail in Set 1.
\nRefer this for more detailed explanation and examples.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Since B has already happened, the sample space reduces to B. So the probability of A happening becomes P(A \u2229 B) divided by P(B)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83569,83617],"tags":[78696,79120,78685,78681,78679,78686,78695,79119,78694,79121,78807,79118,78680,78684,78683],"class_list":["post-26551","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-polygon","category-randomized-algorithms-2","tag-application-of-randomized-algorithm","tag-las-vegas-algorithm-for-search","tag-las-vegas-randomized-algorithm","tag-randomized-algorithm-example","tag-randomized-algorithm-in-daa","tag-randomized-algorithms-geeksforgeeks","tag-randomized-algorithms-lecture-notes","tag-randomized-algorithms-motwani-raghavan-pdf","tag-randomized-algorithms-pdf","tag-randomized-algorithms-ppt","tag-randomized-algorithms-tutorial","tag-randomized-quicksort","tag-randomized-quicksort-algorithm","tag-randomized-quicksort-in-c","tag-types-of-randomized-algorithms"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26551","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=26551"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26551\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26551"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26551"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26551"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}