/Solutions

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.

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

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

1. Compute EX.

2. 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| ≥ α.