Medium | Probability |

A postman brought N letters to a house with two letter-boxes. Since the two boxes were empty, he puts 1 mail in each of the two mail boxes. Then he chooses one of boxes with probability proportional to number of letters present in that box, and puts the 3rd letter in it. He does this for all subsequent letters. What is the expected number of letters in the box with lower letters?

Hint

This can be made equivalent to randomly splitting a deck of n cards into two parts. (n>2)

Solution

Suppose I have a stack of 2 black cards and one red card. Initially I put red between 2 black cards. Now I add black cards randomly between any two cards (so, initially it is either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be: if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Source: P. Winkler

Enable Like and Comment Medium | Probability |

You have an opportunity to make one bid on an object, whose value to its owner is, as far as you know, uniformly random integer between $0 and $100. What you do know is that you are so much better at operating the widget than he is, that its value to you is 80% greater than its value to him. If you offer more than the widget is worth to the owner, he will sell it. But you get only one shot. How much should you bid? For example, if its actual value is $10, you bid & win at $11, and sell it for $18, making profit. But if you bid more than $18, you make lose! But since u don't know how much its actual price is, how do u bid in order to make some profit?

Hint

Consider the case he already won the bid at $x. What happens next?

Solution

CSEBLOG: We should bet only 0! (dont bet!) Suppose I bet $x and get the widget. So, the value of it for the owner would be $y, uniformly distributed between 0 and x. So, its value for me is $1.8y. Expected value for me is 1.8* Expected value of y = 1.8*x/2= 0.9x

So, if I get, expected value of the widget for me is 0.9x$ paying x$.

If x is less, i.e I am not getting it, I did not gain/lose anything.

So, overall I am losing. So, I should not bid.

So, if I get, expected value of the widget for me is 0.9x$ paying x$.

If x is less, i.e I am not getting it, I did not gain/lose anything.

So, overall I am losing. So, I should not bid.

Source: P. Winkler

Enable Like and Comment Medium | Probability |

On a given highway, trucks arrive at the station according to a Poisson process with Lambda = 0.1/minute. This means that after a truck is just passed, the time for the next truck to arrive is an exponential random number with average arrival time of 10 minutes. Your car just broke on this highway, and you are waiting for the next truck for hitchhiking, what is your expected waiting time? On average how many minutes ago the last truck left?

Hint

It's not 5 minutes. Exponential distribution has memoryless property.

Solution

Using memoryless property of exponential distribution, the expected waiting time is 10 minutes. This also holds backwards, hence the expected time last truck passed is also 10 minutes. But this does not violate the total inter-arrival time of 10 minutes, because if your car breaks at a random time, you are more likely to be in long interval than a short one. I don't have time today, remind me to post a more mathematical explanation.

Medium | Probability |

A very sharp, consistently skillful blind archer aimed for the center of a circular board and shot 2 arrows. He is expected to hit the aim, but doesn't hit it for sure. The archer is told that his first shot is better than second. He tried one more shot. What is the probability that this 3rd shot is the best shot among 3?

(ie, Probability that 3rd arrow lands closer to center than his first two shots?)

(ie, Probability that 3rd arrow lands closer to center than his first two shots?)

Hint

Enumeration; Symmetry between random variables.

Answer

1/3

Solution

Suppose x1, x2 and x3 are the distances of the arrows from center. As the archer is consistent, we can use symmetry, i.e., there are six equally likely cases: x1<x2<x3, (or 5 others, which are its permutations). Since archer is told that x1<x2, we are left with following equally likely cases:

x1<x2<x3 , x2<x1<x3 , x1<x3<x2

Among these three, one is favorable. Hence The probability of last shot being best is 1/3.

Notice that if there were (N-1) arrows, with first being better than rest, and then he shoots Nth arrow. The probability that Nth shot is best is 1/N.

x1<x2<x3 , x2<x1<x3 , x1<x3<x2

Among these three, one is favorable. Hence The probability of last shot being best is 1/3.

Notice that if there were (N-1) arrows, with first being better than rest, and then he shoots Nth arrow. The probability that Nth shot is best is 1/N.

Medium | Strategy |

Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?

Hint

the answer is ~1.5n calculations. It uses a trick. When you compare two elements, one comparison is sufficient to find both min & max of those two elements.

Solution

Solution requires approximately 1.5n comparisons instead of 2n comparisons.

Break n numbers into pairs of 2.

So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2.

Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2

So, overall cost 3n/2 comparisons.

Break n numbers into pairs of 2.

So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2.

Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2

So, overall cost 3n/2 comparisons.

Source: H. Cormen

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |