 ### 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 ?

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 ?

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 ?

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 ?

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)

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).

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.

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.

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 ?

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 ?

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 ?

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).

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)