Hard | Probability |

A stick is broken into 3 pieces, by randomly choosing two points along its unit length, and cutting it. What is the expected length of the middle part?

Hint

Selecting the random point from a small 'dt' length element is dt , as length of stick=1. Now use the definition of Expectation.

Answer

1/3

Solution

Double integral of |x-y|dxdy gives 1/3 as answer. This is same as one would expect from a broken pencil.

Palak's Solution:

Integrate from 0 to 1, x*x/2 + (1-x)*(1-x)/2 = 1/3

logic: if one cut is at distance x from left, with probability x, the second cut comes before it, and expected length of middle piece is x/2.. Similarly with prob (1-x) it, middle piece is expected to have length (1-x)/2. Thus adding and integrating from 0 to 1.

Palak's Solution:

Integrate from 0 to 1, x*x/2 + (1-x)*(1-x)/2 = 1/3

logic: if one cut is at distance x from left, with probability x, the second cut comes before it, and expected length of middle piece is x/2.. Similarly with prob (1-x) it, middle piece is expected to have length (1-x)/2. Thus adding and integrating from 0 to 1.

Source: Quant Interview

Enable Like and Comment 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 Latest solved Puzzles

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

© BRAINSTELLAR |