Lesson 2

Advanced Problems.

1. (20 points) A king puts \(15\) white and \(15\) black balls into two boxes. The prisoner may distribute the balls arbitrarily as long as no box is empty. The king picks a box uniformly at random, then a ball uniformly from that box; if it is white, the prisoner is freed. How should the balls be distributed to maximize the chance?
2. (20 points) Consider the following shuffle algorithm on \([n]\). For each \(i \in [n]\), choose \(j_{i}\) uniformly from \([n]\) and swap the elements currently in positions \(i\) and \(j_{i}\).
   • (10 points) Show that for \(n=3\) the output distribution on \(S_{3}\) cannot be uniform, without computing any exact probabilities.
   
   
   • (10 points) Give a condition on \(n\) that implies the distribution cannot be uniform.
   
   

3. (20 points) Consider the cycle graph on \(8\) vertices labeled \(0,1,…,7\) \(\pmod 8\). Start at vertex \(0\). At each step, move to one of the two neighbors uniformly. Compute \[\Pr[\text{vertex \(4\) is never visited in the first \(n\) steps}].\]
4. (20 points) Two integers are selected independently and uniformly at random from \([n]\), and the larger of the two is returned. Find an asymptotic formula for the expected value of the returned number as \(n \to \infty\).
5. (20 points) Suppose that \(n\) is even. Describe a procedure that generates a random regular graph on \(n\) vertices with degree \(d\) (self loops are not allowed, multiple edges are allowed). The procedure must be constructive and efficient (also its running time should be bounded), avoiding the naive approach of generating a random graph and checking for regularity.
6. (25 points) Let \(\pi\) be uniform on \(S_{n}\). What is the probability that \(\pi\) has neither fixed points nor \(2\)‑cycles as \(n \to \infty\)?
   Hint:

   Inclusion–exclusion over \(2\)‑cycles. Choose \(j\) disjoint unordered pairs to be \(2\)‑cycles, count them, and on the remaining \(n-2j\) elements count derangements.