Hard | Probability |

There are 26 black(B) and 26 red(R) cards in a standard deck. A run is number of blocks of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has 6 runs; namely, RRRR, BBB, R, B, R, B. Find the expected number of runs in a shuffled deck of cards.

Hint

Linearity of expectation

Answer

27

Solution

We form the answer for general deck of 2n cards, with n red cards and n black cards. Consider any sequence X1,X2..X2n (of R & B). Now define Y1 = 1;

Yi = 1 if Xi and X(i-1) are of different colors

Yi = 0 otherwise.

We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)

Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)

Ans = 1+(2n-1)*E[Y_i] = n+1

This is 27 for deck of 52 cards.

Yi = 1 if Xi and X(i-1) are of different colors

Yi = 0 otherwise.

We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)

Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)

Ans = 1+(2n-1)*E[Y_i] = n+1

This is 27 for deck of 52 cards.

Source: Quantnet

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

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

© BRAINSTELLAR |