(Applying Markov and Chebyshev) For each of the following random variables, apply Markov's and Chebyshev's inequality to obtain the required bounds. Think, but don't hand in: How do the bounds you obtain compare to actual probabilities?
(a) (Dance) Girls stand in a circle and hold hands. Each of them took off her shoes and neatly put them in front of her. Let n be the number of girls. When the music starts, the girls walk around the circle, while still holding hands. When the music stops, they stop. Assume that each girl stops in front of a uniformly random pair of matching shoes, that is, in one of the n possible positions. (Note that girls positions are strongly correlated, because they hold hands and move around the circle.) Let random variable X be the number of girls that stopped in front of their own pair of shoes.
i. What is the PDF of X?
ii. Apply Markov inequality to find a bound on the probability that X > n.
iii. What is the PDF of X2?
iv. Apply Chebyshev's inequality to find a bound on the probability that X > n.
