Hard | Probability |

There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them.

Hint

Linearity of expectation

Solution

Let I_i be a indicator random variable which takes

1) value 1 if ith letter ends up in ith envelope.

2) value 0, otherwise

let I be r.v which indicates the number of letters which ended up in their respective envelopes.

Now, I= I_1 +I_2+....+I_n

E[I_i] = 1/n. for all i

Using Linearity of Expectations E[I]= 1/n + 1/n +...+1/n = 1.

1) value 1 if ith letter ends up in ith envelope.

2) value 0, otherwise

let I be r.v which indicates the number of letters which ended up in their respective envelopes.

Now, I= I_1 +I_2+....+I_n

E[I_i] = 1/n. for all i

Using Linearity of Expectations E[I]= 1/n + 1/n +...+1/n = 1.

Source: CSEblog

Enable Like and Comment Hard | Probability |

A soda company is holding a contest where everyone who collects one each of N different coupons wins some prize. You get a coupon with each purchase of a soda, and each coupon is equally likely. What’s the expected number of soda bottles you have to buy in order to collect all the coupons?

Hint

Linearity of expectation

Solution

Divide the whole process in to stages. Each stage ends with collecting a coupon which is new ( different from the coupons we already have )

Let C_i be the random variable which denotes the number of coupons we buy in the stage i.

Let C be the random variable which denotes the number of coupons we buy in order to get all n coupons

Now,

C= C_1 + C_2 + ... + C_n

Note C_1 = 1;

In general, while we are during stage i , we already have with us (i-1) different coupons. So, the probability of getting a new coupon is p_i = n-(i-1)/n. Also note that each C_i is a Geometrically distributed random variable with success probability equal to p_i. So, E(C_i) = 1/p_i = n/(n-i+1).

By using Linearity of Expectations,

E(C) = E(C_1) +E(C_2) + ...+E(C_n)

= n(1/n + 1/(n-1)+ ... +1)

~ nlogn.

Let C_i be the random variable which denotes the number of coupons we buy in the stage i.

Let C be the random variable which denotes the number of coupons we buy in order to get all n coupons

Now,

C= C_1 + C_2 + ... + C_n

Note C_1 = 1;

In general, while we are during stage i , we already have with us (i-1) different coupons. So, the probability of getting a new coupon is p_i = n-(i-1)/n. Also note that each C_i is a Geometrically distributed random variable with success probability equal to p_i. So, E(C_i) = 1/p_i = n/(n-i+1).

By using Linearity of Expectations,

E(C) = E(C_1) +E(C_2) + ...+E(C_n)

= n(1/n + 1/(n-1)+ ... +1)

~ nlogn.

Source: Quant Interview

Enable Like and Comment Hard | Probability |

You have 100 noodles in your soup bowl. You are told to take two ends of some noodles (each end on any noodle has the same probability of being chosen) in your bowl and connect them. You continue until there are no free ends. What is the expected number of loops? What is the probability of making one large loop which includes every noodle?

Hint

Expected number of noodles come from linearity of expectation. Probability comes from multiplying independent probabilities.

Solution

First calculate expected number of loops:

Denote X1 = identity variable, which takes value 1 every time a (long) noodle becomes a loop by connecting to its end, (if its own end is connected to some other noodle, then that other noodle's end will be considered). Thus, number of loops = X1 +...+ X100, thus, expected number of loops = E(X1) + ... + E(X100). This will give answer = 1/(2N-1) + 1/(2N-3) + ... + 1/3 + 1

where N = 100. This formula can also be proved using induction.

Calculating Probability of single large loop:

If you followed last result, this one is simple, this time all the identitiy variables are zero except last one. Thus probability is [1 - 1/(2N-1)]*[ 1 - 1/(2N-3)]* ... *[1-1/3]

= Product ( i = 2 to N) [ (2i-2) / (2i-1)]

Denote X1 = identity variable, which takes value 1 every time a (long) noodle becomes a loop by connecting to its end, (if its own end is connected to some other noodle, then that other noodle's end will be considered). Thus, number of loops = X1 +...+ X100, thus, expected number of loops = E(X1) + ... + E(X100). This will give answer = 1/(2N-1) + 1/(2N-3) + ... + 1/3 + 1

where N = 100. This formula can also be proved using induction.

Calculating Probability of single large loop:

If you followed last result, this one is simple, this time all the identitiy variables are zero except last one. Thus probability is [1 - 1/(2N-1)]*[ 1 - 1/(2N-3)]* ... *[1-1/3]

= Product ( i = 2 to N) [ (2i-2) / (2i-1)]

Hard | Probability |

Given the set of numbers from 1 to n: { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?

Hint

Linearity of expectation

Answer

E(n) = n[1-(1-1/n)^n]

Solution

Notice that number of distinct points in the produced set is same as number of distinct points selected from the given set {1..n} . For that we denote indicator function Si, that is, Si = 1 if the interger i is taken into produced set.

Let S denote the number of distinct points selected, S = S1+..+Sn

E(S) = E(S1) +...+ E(Sn)

and E(Si) = 1*P(Si) = 1 - (Probability that 'i' is not chosen in any draw)

= 1 - ( Prob that is i is not chosen in one 1st draw)^n = 1 - ( 1 - 1/n )^n

Thus E(S) = n * ( 1 - ( (n-1) / n)^n )

Let S denote the number of distinct points selected, S = S1+..+Sn

E(S) = E(S1) +...+ E(Sn)

and E(Si) = 1*P(Si) = 1 - (Probability that 'i' is not chosen in any draw)

= 1 - ( Prob that is i is not chosen in one 1st draw)^n = 1 - ( 1 - 1/n )^n

Thus E(S) = n * ( 1 - ( (n-1) / n)^n )

Source: CSEblog

Enable Like and Comment Hard | Probability |

What is the expected number of cards that need to be turned over in a regular 52-card deck in order to see the first ace?

Hint

Hint: the locations of the four aces in the deck divide it into the five groups X1, ...,X5.

Answer

53/5

Solution

Define X1,X2…X48, such that Xi = 1 if ith card turns over before 4 aces, 0 otherwise. Thus, total number of cards turned to see first ace = 1 + sum (Xi)

using linearity of expectation, E(X) = 1 + sum ( E(Xi))

Now consider the ith card and the four aces, all the orders are equally likely: X,A,A,A,A Or A,X,A,A,A, or 3 others. They are equally likely when we have no knowledge about position of these Aces with respect of the deck. Hence we have 5 equally likely slots for ith card: 1 A 2 A 3 A 4 A 5. We are interested in 1st slot.

Hence E(Xi) = 1/5 for all i = 1 to 48

Thus E(X) = 1 + 48/5 = 53/5 = 10.6

This can be done by recursive equation f(n) = (4/n)*1 + ((n-4)/n)*(1+f(n-1), where f(n)=expected cards to flip in a deck of n cards, but I definitely can't solve this without a computer.

A shorter explanation is to consider the 52 cards uniformly distributed over (0,1), so on average they're at k/53 for k=1,2,3,…,52. The four aces are on average at 1/5, 2/5, 3/5, 4/5. So 0.2=k/53 implies k=10.6, done!

using linearity of expectation, E(X) = 1 + sum ( E(Xi))

Now consider the ith card and the four aces, all the orders are equally likely: X,A,A,A,A Or A,X,A,A,A, or 3 others. They are equally likely when we have no knowledge about position of these Aces with respect of the deck. Hence we have 5 equally likely slots for ith card: 1 A 2 A 3 A 4 A 5. We are interested in 1st slot.

Hence E(Xi) = 1/5 for all i = 1 to 48

Thus E(X) = 1 + 48/5 = 53/5 = 10.6

This can be done by recursive equation f(n) = (4/n)*1 + ((n-4)/n)*(1+f(n-1), where f(n)=expected cards to flip in a deck of n cards, but I definitely can't solve this without a computer.

A shorter explanation is to consider the 52 cards uniformly distributed over (0,1), so on average they're at k/53 for k=1,2,3,…,52. The four aces are on average at 1/5, 2/5, 3/5, 4/5. So 0.2=k/53 implies k=10.6, done!

Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |