Gems from the world of Probability




  1. n persons, all of different heights are standing in a queue facing the window of ticket distributor in a cinema hall. What is the expected number of persons visible to the person at the ticket window if each permutation of n persons is equally likely ?


  2. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out ?


  3. &spades
    There is a bin containing r white balls and b black balls. We repeat the following experiment until there is only one ball left : Take out two balls uniformly at random. If they are of the different colour then throw them away and put a new white ball into the bin. If they are of same colour, then throw them away and put a black ball into the bin. What is the probability that the last ball in the bin is a white ball ?


  4. &spades &spades
    A sick person has a bottle containing pills. There are two types of pills : small pills and large pill. Each large pill is equivalent to two small pills. The sick person has to take one small pill per day. He wakes up daily in morning and takes out one pill at random from the bottle. If it is a small pill, he consumes it and puts the bottle back, otherwise he breaks the large pill into two halves, eat one half and put the other half back into the bottle and this half piece of the large pill would be treated as a small pill henceforth. What is the expected number of small pills left in the bottle when all the large pills have been consumed ?


  5. &spades
    Consider a group consisting of m men, w women, c children, r rabbits.
    Assume that no two individuals have same height. Moreover, each rabbit is shorter in height than each child who in turn is shorter than each women and each woman is shorter in height than each man.

    The game starts with a set of participants arranged in a line from left to right where each permutation is equally likely. There is a prize at the left end of the line. Assume that a participant at place i would see the prize if none of the participants preceding him/her is taller than him/her. A woman can receive the prize only if she can see the prize and there is atleast at-least one of the participants preceding her in the line is a child. What is the expected number of women that would win the prize ?


  6. &spades &spades
    Given a tree on n vertices, and let u and v be any two vertices in the tree. A monkey is performing a random walk starting from vertex u. Give a neat and small proof to show that the expected number of steps required by the monkey to reach vertex v is O(n2). (Do not use connection between electric networks and random walk)


  7. &spades &spades
    Given a connected graph G. Further each node in the graph chooses c nodes uniformly at random and adds edges to these, where c is a large enough constant. Show that this graph has expected diameter O(log n).


  8. &spades
    We are given a random permutation of n real numbers. Consider the following scheme P(k) to estimate the largest of these numbers.
    P(k) : Scan first k numbers in the permutation and select the largest of them. Let it be max(k). Now continue scanning until we find a number larger than max(k). If we find such a number, report that number as the largest of all the numbers. If we do not succeed (and hence end up scanning all the numbers), declare max(k) to be the largest number.
    • What is the probability (in terms of k and n) that using scheme P(k) succeeds in reporting the largest number ?
    • What value of k maximizes the success of our scheme ?



  9. Given a biased coin with unknown bias, how can you use it to simulate a fair coin?


  10. How can you use a fair coin to select a fruit uniformly from three fruits : apple, banana, orange? What is the expected number of tosses required to select one fruit? Your aim should be to use expected constant number of coin tosses to perform a selection.


  11. &spades &spades
    This problem is an extension of the previous one. On a day exactly one of n possible events E1,E2,...,En can occur. Given that event Ei occurs with probability pi , with &Sigma pi = 1. How can you simulate these events using a fair coin ? Note that The expected number of tosses required for predicting an event should be constant.


  12. &spades &spades
    You have a bag that can hold at-most k apples. You enter a store having apples arranged in a row, and your objective is to choose a uniform sample of k apples from the store. However, the store is poorly lit and so you have no idea of the number of apples in the store. Moreover, you are not allowed to move backward. In other words, while moving along the row of apples, you are given only one time access to each apple, and you have to decide in an online manner whether to select the apple or not. How will you ensure that you finally end up having k uniformly picked appled from the store ?


  13. &spades
    From one end of a very very long highway, a stream of n cars leave at intervals of one minute. No overtaking is allowed on this highway. Each car chooses a speed randomly from the coninuous range of 0-100 kmph independent of other cars. It is easy to observe that a car running at lower speed will force its following car to slow down if the latter was moving at a faster speed. You are sitting in the car which started its journey at ith place. What is the expected number of cars you will see in front of your car after reasonably long time ?


  14. Let us select n-1 points independently and uniformly from the segment (0,1). The n-1 points partition the segment into n small segments. What is the probability that there exists a polygon defined by these n segments ?


  15. &spades &spades &spades
    Let us select n points independently and uniformly from the segment (0,1) on a line. The n points partition the segment into n+1 intevals. Show that the expected length of the smallest of these intervals is 1/(n+1)2 ?


  16. &spades &spades &spades &spades
    There is a complete graph on n vertices where weight of each edge is uniformly and independently selected from interval [0,1]. Show that the expected weight of the minimum spanning tree of the graph is bounded by 2 ln 2 &asymp 1.38 . (Note that there is a very short and simple proof based on analysis of Kruskal's algorithm using principle of deferred decision).


  17. &spades
    A line of n airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. The ith passenger in line has a ticket for the seat number i.

    Unfortunately, the first person in line is crazy, and will ignore the seat number on his ticket, picking a random seat to occupy. All the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If their given seat is occupied, they will then find a free seat to sit in, (uniformly) at random. What is the probability that the last (nth) person to board the plane will sit in his/her proper seat (n)? (source : Amitabha bagchi)




  18. &spades
    There is a village consisting of n houses. A smart thief is hiding in some house. Every morning police raids some random house in search of the thief and destroys that house. However, some corrupt policemen inform the thief about it on the evening each day about the house which Police will raid on the next morning. So if Police is going to raid the house in which thief is presently residing, then during the night thief select a random house which has not been destroyed in the past and moves in to that house. The way the Police selects house for raiding is arbitrary and need not follow any probability distribution. Eventually there will be only one house left and so the thief will have to leave the village. What is the expected number of times the thief will change the houses before leaving the village.



  19. &spades &spades &spades
    There is a collection of m sticks arranged along a line from left to right. All of them are red initially. We start from the leftmost stick. Using a fair coin we form two groups of sticks - A and B as follows. For ith stick we toss a coin. If it gives TAILS we put it into B. If it gives HEADS, we add it to A; but if this stick (added to A) was red, then some sticks which follow may turn black. As soon as we have n red sticks in A, we stop. Otherwise, we continute till we have explored all the sticks. Show that the expected number of red sticks in B at the end of the experiment is bounded by 2n. (Note that the problem is complete, and no additional information is needed to solve it).