"Mathematical Expectation" is one of those few topics that is rarely discussed in details in any curriculum, but is nevertheless very important. This tutorial attempts to throw some light on this topic by discussing few related mathematical and programming problems. Show TheoryMathematical Expectation is an important concept in Probability Theory. Mathematically, for a discrete variable X with probability function P(X), the expected value E[X] is given by Σ xiP(xi) the summation runs over all the distinct values xi that the variable can take. For example, for a dice-throw experiment, the set of discrete outcomes is { 1,2,3,4,5,6} and each of this outcome has the same probability 1/6. Hence, the expected value of this experiment will be 1/6*(1+2+3+4+5+6) = 21/6 = 3.5. For a continuous variable X with probability density function P(x) , the expected value E[X] is given by ∫ xP(x)dx. It is important to understand that "expected value" is not same as "most probable value" - rather, it need not even be one of the probable values. For example, in a dice-throw experiment, the expected value, viz 3.5 is not one of the possible outcomes at all. The rule of "linearity of of the expectation" says that E[x1+x2] = E[x1] + E[x2]. Tutorials Problems1. What is the expected number of coin flips for getting a head? Ans: Let the expected number of coin flips be x. Then we can write an equation for it - The expected value x is the sum of the expected values of these two cases. Using the rule of linerairty of the expectation and the definition of Expected value, we get x = (1/2)(1) + (1/2) (1+x) Thus the expected number of coin flips for getting a head is 2. Q2. What is the expected number of coin flips for getting two consecutive heads? Adding, the equation that we get is - Solving, we get x = 6. Thus, the expected number of coin flips for getting two consecutive heads is 6. Q3. (Generalization) What is the expected number of coin flips for getting N consecutive heads, given N? a) If we get 1st, 2nd, 3rd,...,n'th tail as the first tail in the experiment, then we have to start all over again. For the 1st flip as tail, the part of the
equation is (1/2)(x+1) Adding, x = (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k) + .. + (1/(2^N))(x+N) + (1/(2^N))(N) Solving this equation is left as an exercise to the reader. The entire equation can be very easily reduced to the following form: x = 2N+1-2 Thus, the expected number of coin flips for getting N consecutive heads is (2N+1 - 2). Q4. Candidates are appearing for interview one after other. Probability of each candidate getting selected is 0.16. What is the expected number of candidates that you will need to interview to make sure that you select somebody? x = 0.16 + (1-0.16)*(x+1) Solving, x = 1/0.16, i.e. x = 6.25 Q5. (Generalized version of Q4) - The queen of a honey bee nest produces offsprings one-after-other till she produces a male offspring. The probability of produing a male offspring is p. What is the expected number of offsprings required to be produced to produce a male offspring? x = p + (1-p)*(x+1) Thus, observe that in the problems where there are two events, where one event is desirable and other is undesirable, and the probability of desirable event is p, then the expected number of trials done to get the desirable event is 1/p Generalizing on the number of events - If there are K events, where one event is desirable and all others are undesirable, and the probability of desirable event is p, then also the expected number of trials done to get the desirable event is 1/p The next question uses this generalization - Q6. what is the expected number of dice throws required to get a "four"? Q7.Candidates are appearing for interview one after other. Probability of k-th candidate getting selected is 1/(k+1). What is the expected number of candidates that you will need to interview to make sure that you select somebody? case-1: First candidate gets selected. The probability of this event is 1/2 and the number of interviews is 1. [ Note that similar to problem 4, here we can't just say - if the first candidate is rejected, then we will start the whole process again. This is not correct, because the probabilty of each candidate depends on it's sequence number. Hence sub-experiments are not same as the parent experiment. This means that
all the cases must be explicitly considered.]
Q8: A random permutation P of [1...n] needs to be sorted in ascending order. To do this, at every step you will randomly choose a pair (i,j) where i < j but P[i] > P[j], and swap P[i] with P[j]. What is the expected number of swaps needed to sort permutation in ascending order. (Idea: Topcoder) This is a programming question, and the idea is simple - since each swap has same probability of getting selected, the total number of expected swaps for a permutation P is E[P] = ( 1/cnt ) * Σ (E[Ps] + 1) where cnt is the total number of swaps possible in permutation P, and Ps is the permutation generated by doing swap 's'. Since all swaps are equiprobable, we simply sum up the expected values of the resultant permutations (of course add 1 to each to account for the swap done already) and divide the result by the total number of permutations. The base case will be for the array that has been already sorted - and the expected number of permutations for a sorted array is 0. Coding this is left as a (trivial) exercise to the reader. Q9. A fair coin flip
experiment is carried out N times. What is the expected number of heads? ai = if the i'th experiment gave head then 1 else 0. Hence we have: Since ai corresponds to a coin-toss experiment, the value of E[ai] is 0.5 for each i. Adding this n times, the expected number of heads in Z comes out to be n/2. Q10: (Bernaulli Trials) n students are asked to choose a number from 1 to 100 inclusive. What is the expected number of students that would choose a single digit number? This question is based on the concept of bernaulli trials.An experiment is called a bernaulli trial if it has exactly two outcomes, one of which is desired. For example - flipping a coin, selecting a number from 1 to 100 to get a prime, rolling a dice to get 4 etc. The result of a bernaulli trial can typically be represented as "yes/no" or "success/failure". We have seen in Q5 above that if the probability of success of a bernaulli trial is p then the expected number of trials to get a success is 1/p. is This question is based on yet another result related to bernaulli trials - If the probability of a success in a bernaulli trial is p then the expected number of successes in n trials is n*p. The proof is simple - The number of successes in n trials = (if 1st trial is success then 1 else 0) + ... + (if nth trial is success then 1 else 0) In the current case, "success" is defined as the experiment that chooses a single digit number. Since all choices are equiprobable, the probability of success is 9/100. (There are 9 single digit numbers in 1 to 100). Since there are n students, the expected number of students that would contribute to success (i.e the expected number of successes) is n*9/100 Q11. What is the expected number of coin flips to ensure that there are atleast N heads? N heads = if 1st flip is a head then N-1 more heads, else N more heads. E[N] = (1/2)(E[N-1]+1)+ (1/2)(E[N] + 1) The base case is when N = 1 : Simplifying the recursive case, Since E[1] = 2, E[2] = 4, E[3] = 6,..., in general E[N] = 2N. Thus, the expected number of coin flips to ensure that there are atleast N heads in 2N. The next problem discusses a generalization : Q12. What is the expected number of bernaulli trials to ensure that there are atleast N successes, if the probability of each success is p? E[N] = p(E[N-1]+1)+ (1- p)(E[N] + 1) Solving, E[N]-E[N-1] = p. Writing a total of N-1 equations: E[N]-E[N-1] = 1/p Adding them all, E[N] - E[1] = (n-1)/p. But E[1] is 1/p (lemma -1). Hence E[N] = n/p. Moral: If probability of success in a bernaulli trial is p, then the expected number of trials to guaranttee N successes is N/p. This completes the discussion on problems on Mathematical Expectation. Exercises:Note: Some of these are non-trivial and require concepts not discussed in this tutorial. If you are interested you could read about probability distribution basics, more advanced topics such as joint and bivariate distributions and transformations and a tutorial on permutations and combinations 1. A game involves you choosing one number (between 1 to 6 inclusive) and then throwing three fair dice simultaneously. If none of the dice shows up the number that you have chosen, you lose $1. If exactly one, two or three dice show up the number that you have chosen, you win $1, $3 or $5 respectively. What is your expected gain? 2. There are 10 flowers in a garden, exactly one of which is poisonous. A dog starts eating all these flowers one by one at random. whenever he eats the posionous flower he will die. What is the expected number of flowers he will eat before he will die? 3. A bag contains 64 balls of eight different colours, with eight of each colour. What is the expected number of balls you would have to pick (without looking) to select three balls of the same color? 4. In a game of fair dice throw, what is the expected number of throws to make sure that all 6 outcomes appear atleast once? 5. What is the expected number of bernaulli trials for getting N consecutive successes, given N, if the probability of each success is p? Just in case someone needs to brush up their Probability Theory, you might find these tutorials useful. Specially, with Data Science gaining so much importance, probability and statistics are important for Computer and Data Scientists. A very basic introduction to probability and its applications Basic Probability Definitions, Random Variables Probability Distributions Joint Probability and Bivariate Distributions What is the probability of getting at most 1 head in 2 coin tosses?When a coin is tossed two times. Therefore, the probability of getting at most one head is 3/4.
What is the probability of getting 1 head?Since there are 4 possible outcomes with one head only, the probability is 4/16 = 1/4.
What is the probability of getting at least 1 head in tossing 2 coins *?Hence, P(Getting atleast one head) =34.
|