# 1. A card counting problem

Suppose we take a deck of 2n cards, of which n are black and n are red, and shuffle it so that all (2n)! permutations are equally likely. We now play the following game: for each card, before seeing it turned over, you have the option to say *take*; you then get 1 point if the card is black and -1 points if the card is red. If you do not say *take*, the card is turned over anyway, you can observe whether it is red or black, and we move on to the next card.

Suppose you are required to say

*take*exactly once (i.e., once you say*take*the game ends, and if you haven't said*take*before you reach the last card you have to take the last card). What is your expected return if you play the game optimally?Suppose now that you can only say

*take*once, but you are not required to do so. Now what is your expected return with optimal play?

# 2. Waiting times

Suppose we flip a biased coin that comes up heads with probability p until it comes up heads n times. Let X be the total number of times we flip the coin.

- Compute EX.
Show that for any fixed p and fixed δ>0, Pr[X > (1+δ)EX] declines exponentially as a function of n. If it makes your life easier, you may assume that (1+δ)EX is an integer.

# 3. Exposure

Suppose that we generate two strings x and y of length n over an alphabet of size s uniformly at random. A string z of length k is a subsequence of x if there is some sequence of indices f(1)<f(2)<...<f(k) such that z_{j} = x_{f(j)} for j=1..k. A longest common subsequence of x and y is a string z of maximum length that is a subsequence of both x and y. Let X be the length of the longest common subsequence of x and y.

Give the best bound you can on the probability that |X-EX| ≥ α.