Lesson 1

Basic Problems.

1. (5 points) A coin is flipped \(n\) times. What is the probability that all the heads appear at the end of the sequence?
   Hint:

   Favorable sequences have the form \(T^{k}H^{n-k}\).
2. (5 points) An urn contains \(b\) black and \(w\) white balls. Two balls are drawn simultaneously. Find the probability that the colors are the same.
   Hint:

   Use combinations for “two black” or “two white”.
3. (5 points) Ten students take an exam with ten questions. Each student, in turn, draws a random question from the remaining ones. Alice knows exactly one question. When should she enter: first, last, or does it not matter?
4. (10 points) Select a number \(x\) from \([n]\), then select a number \(y\) out of the \(n-1\) remaining numbers. For \(m<n\), compute \(\Pr[x-y \ge m]\).
   Hint:

   Count ordered pairs \((x,y) \in [n]^{2}\) with \(x-y\ge m\).
5. (10 points) A student knows \(50\) out of \(75\) exam questions. What is the probability that the student knows at least two questions from an exam ticket containing three different random questions.
6. (10 points) Two marksmen use a revolver with a \(6\)-chamber cylinder and one bullet. They alternate shots until the bullet fires. Who has a higher chance to hit first? How does the answer change if the cylinder is re-spun before every shot?
   Hint:

   No re-spin: the bullet's initial position is uniform over the 6 chambers. With re-spins: write down a formula for the probability.
7. (10 points) Teams \(A\) and \(B\) play a best-of-three series. Team \(A\) wins any given game with probability \(\frac{3}{5}\). How likely is it that three games are played? How likely is it that the series winner loses the first game?
   Hint:

   Draw the process tree.
8. (10 points) Roll seven dice. What is the probability that the seven resulting integers contain all of \([6]\)?
   Hint:

   Exactly one face repeats. Choose the repeated face, its two positions, then permute the other five.
9. (10 points) A drawer contains red and black socks. When two socks are drawn uniformly at random, the probability both are red is \(1/2\). How small can the total number of socks be?
10. (10 points) In a randomized algorithm with one-sided error, a single run outputs a correct result with probability \(p\). I.e. if algorithm outputs “true” the answer is “true”, but if it outputs “false”, then the answer is “false” with probability at least \(p\). Show that after \(\lceil 100/p\rceil\) independent runs, the probability that none is correct is at most \(2^{-100}\).
    Hint:

    Use \(1+x\le e^{x}\) for any \(x\).
11. (10 points) One offers you a game with three dice: \[A=[2,6,7,2,6,7],\quad B=[1,5,9,1,5,9],\quad C=[3,4,8,3,4,8].\] You choose a die first, then I choose one of the two remaining, and we roll once. Whoever rolls the larger number wins. Which die would you choose?
    Hint:

    Compute \(\Pr[A>B]\), \(\Pr[B>C]\), and \(\Pr[C>A]\) by listing pairs.
12. (15 points) Consider a random walk on a hexagon with vertices labeled \(1,\dotsc,6\). Start at vertex \(1\). At each step move to one of the two neighbors uniformly. Compute the probability that vertex \(4\) is never visited in \(n\) steps.
    Hint:

    Group states by distance to \(4\) and write a short recurrence.