Hard | Probability |

An ant is standing on one corner of a cube & can only walk on the edges. The ant is drunk and from any corner, it moves randomly by choosing any edge! What is the expected number of edges the ant travels, to reach the opposite corner?

Hint

Try to find the equivalent vertices with respect to distance yet to travel. This should give 4 equivalent merged vertices, with 1st being start & 4th being destination.

Solution

Let the expected number of step required to go from (0,0,0) to (1,1,1) be E0.Also let expected number of step required to reach (1,1,1) from (0,0,1)(Or from (0,1,0) or from (1,0,0)) be E1. similarly expected number of step required to reach (1,1,1) from (0,1,1) (Or from (1,0,1) or from (1,1,0)) be E2.Then we can write:

E0=1/3(E1+E1+E1)+1

E1= 1/3*E0 + 2/3*E2 + 1

E2 = 2/3*E1 + 1

solving this we find E0 as 10.

E0=1/3(E1+E1+E1)+1

E1= 1/3*E0 + 2/3*E2 + 1

E2 = 2/3*E1 + 1

solving this we find E0 as 10.

Source: Quant Interview

Enable Like and Comment Hard | Probability |

What is the expected distance of any point on Earth and the north pole? Take Earth radius 1.

Clarification: Shortest distance cuts through the sphere, instead of lying on surface.

Further thinking: Is this question same as choosing two random points on unit sphere and asking their expected distance?

Clarification: Shortest distance cuts through the sphere, instead of lying on surface.

Further thinking: Is this question same as choosing two random points on unit sphere and asking their expected distance?

Hint

Imagine a ring of some thickness, whose distance from N is constant from all points on that ring. Get the average of all such rings.

Answer

4/3

Solution

2*sin(x/2)is the distance of north pole from a point on the ring at angle x from the z axis. So, integrate from 0 to pi, (2*pi*sin(x)*2*sin(x/2) dx) and divide by the total area which is 4*pi.

Answer:4/3

Another approach is to imagine a horizontal ring of dy thickness at distance y from N (north pole).

Area of ring = 2*pi*dy

Probability of choosing point on this ring = dy/2

Distance of N & a point on ring = sqrt(2y)

Exp length = integral (y=0 to 2) of sqrt(2y) dy/2 = 4/3

And yes, taking two random points on surface of sphere and asking their expected distance is same as this very question.

Answer:4/3

Another approach is to imagine a horizontal ring of dy thickness at distance y from N (north pole).

Area of ring = 2*pi*dy

Probability of choosing point on this ring = dy/2

Distance of N & a point on ring = sqrt(2y)

Exp length = integral (y=0 to 2) of sqrt(2y) dy/2 = 4/3

And yes, taking two random points on surface of sphere and asking their expected distance is same as this very question.

Source: Quant Interview

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

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

© BRAINSTELLAR |