Problems involving linearity of expectation and careful choice of random variables



    1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.



    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. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls



    4. Given a graphs G=(V,E) on n vertices and m edges. Show that there is a bipartite sub-graph of the graph G with atleast m/2 edges.



    5. Show that the expected number of comparisons made during randomized quick sort on an input of size n is O(nlog n) .



    6. Mulmuley Games (A slightly different formulation)
        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.
        There are five types of games. Each 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.
      1. Game A : all rabbits and women are the participant. What would be the expected number of women that would see the prize?

      2. Game B : all rabbits, women and children participate in the game. What would be the expected number of children who can see the prize.

      3. Game C : all rabbits, women and children participate in the game. 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.

      4. Game D : all rabbits, women, children and men are the participants. 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.

      5. Game E : all rabbits, women, children and men are the participants. A woman can receive the prize only if she can see the prize and all children appear before her. What is the expected number of women that would win the prize?




    7. A randomized binary search tree on n keys is formed as follows. Initially the tree is empty. We keep a pool of all the key that have to be inserted in to the tree. At each step, we take out a key from the pool uniformly randomly and insert it into the binary search tree. We continue until the pool becomes empty, and we get a binary search tree. Use Mulmuley's game A to show that the expected depth of ith largest key in a random binary search tree is log i + log n-i.



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

    More Ball-Bin Problems and Traversal Problems



    1. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?



    2. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.



    3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?



    4. There are two bins A and B, each containing one ball initially. We have n balls with us that we shall put one by one into these bins randomly in n steps as explained below. Let A(t) and B(t) denote the number of balls in bin A and B respectively after t steps. During (t+1) step, we take out a ball from the box and put it into bin A with probability A(t)/(A(t)+B(t)), and into bin B with probability A(t)/(A(t)+B(t)). What can you say about the distribution of the random variable A(t). In other words, what is the probability that bin A has t balls (for a given t less than or equal to n).



    5. Consider the following description of 1-dimensional random walk : A particle is at the origin (mid-point) of interval [-n,n] initially. In each minute, the particle moves one unit to left or one unit to the right with equal probability. What is the expected number of minutes until the particle hits one of the boundaries of interval [-n,n]? What can you say about the expected distance of the particle from the origin?



    6. *** 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. Use arguments analogous to the previous problem to show that the expected number of steps required by the monkey to reach vertex v is O(n^2).



    Problems on variance and application of Chernoff's bound.



    1. There are m balls and n bins. For each ball we select a bin uniformly at random, and place it inside the bin. Show that if m>=n\log n, the fullest bin will have O(m/n) balls.



    2. On Random Graphs

      Definition : Let G(n,p) be the random graph on n vertices which is obtained by independently adding an edge between every pair of vertices with probability p.



      1. A triangle in G(n,p) is defined as a set of three nodes such that every pair of these nodes is joined by an edge. Let X be the random variable which denotes the number of distinct triangles in G(n,p). What is the expectation of X? What is the variance of X?



      2. Consider G(n,p) for p=1/2. Show that the expected diameter is at most a constant.



      3. Consider G(n,p) for p=(c log n)/n , where c is a large enough constant. Show that the expected diameter of this graph is O(log n).



      4. 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).
        Remark : Compare the two problems given above and note the following observation : Unlike a random graph, if the initial graph is connected, it requires only a constant number of random edges per vertex to reduce the graph diameter to O(log n).



    3. On spreading of rumor





      1. Consider a group of n persons. Initially one person has some information. This information is spread in rounds as follows. In a round, each person who has the information calls some person uniformly at random from the group and communicates the information to him. Show that the expected number of rounds before everyone knows the information is O(log n) with very high probability (i.e., with probability at least 1-1/O(n))



      2. The previous algorithm for spreading rumor is called 'push-algorithm'. Now consider the 'pull-algorithm' for rumor spreading. In this algorithm, we begin with one node having the information. In each round, every node calls a node at random. If x calls a node y and y has the information, then x also gets the information. Show that the expected number of rounds before everyone knows the information is O(log n) with very high probability.



      3. *** Show that the a combination of 'push-algorithm' and 'pull-algorithm' would reduce the expected number of rounds to O(loglog n).


    Problems based on application of conditional probability



    1. n persons, all of different heights are standing in a queue facing the window of ticket collector 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. 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 ?




    3. Given an undirected weighted graph G(V,E) on n vertices and m edges. For a subset S of edges, Let T(V,S) be the minimum spanning tree for the subgraph G(V,S) . An edge e of set E-S is said to be light with respect to S if its addition can improve the mst. Show that if set S is formed by picking each edge independently with probability p , then expected number of light edges from the set E-S is n/p .



    4. There is a family with two children. Assume that each child is equally likely to be a girl or a boy independent of the other child. Given the additional information that there is at-least one boy in the family, what is the probability that the other child is also a boy.




    How to sample with a coin ?



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



    2. You have to permute n items uniformly. You have only a fair coin at your disposal. Give two algorithms that output a uniformly picked permutation of the items. (Hint : One algorithm will be based on the idea of quick sort while the other algorithm will be based on throwing n balls into 2n bins with repating a throw in case of collosion). What is the expected number of coin tosses required in each case.



    3. We want n random variables, each of them should take a value uniformly in the range 1 to n . Furthermore we want that they should be pairwise independent. How can you generate a sample of these n numbers with only O(log n) random bits?



    4. 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?



    5. On a day (exactly) one of n possible events E1,E2,...,En can occur. Given that event Ei occurs with probability pi , with \sum_{i\le n} pi = 1. How can you simulate these events using a fair coin ? What is the expected number of tosses required for predicting an event ?



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