# 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?

## 1.1. Solution

In each case, we can set up a recurrence. Let T_{i}(k,m) be the expected return for the i-th game starting from a state with k black cards and m cards total. The expected value of the next card is k/m - (m-k)/m = 2k/m - 1.

For the first two games, we can take this expected return, or we can flip the card and take whichever of T_{i}(k-1,m-1) or T_{i}(k,m-1) we get. The recurrence is thus T_{i}(k,m) = max(2k/m - 1, (k/m)T_{i}(k-1,m-1) + (1-k/m)T_{i}(k,m-1)), with a boundary condition of T_{1}(k,1) = 2k-1 for the first game and T_{2}(k,1) = k for the second.

To solve the recurrence for T_{1}, we look at some small cases:

k |
m |
T |

0 |
1 |
-1 |

1 |
1 |
1 |

0 |
2 |
-1 |

1 |
2 |
max(0, (1/2)(1+-1)) = 0 |

2 |
2 |
max(1, 1) = 1 |

0 |
3 |
-1 |

1 |
3 |
max(-1/3, (1/3)(-1)+(2/3)(0)) = -1/3 |

2 |
3 |
max(1/3, (2/3)(0)+(1/3)(1)) = 1/3 |

3 |
3 |
1 |

At this point we guess that the max is always a no-op and that T_{1}(k,m) = 2k/m - 1 for all k and m. We can verify this by checking the boundary condition:

and the recurrence, for m>1:

For T_{2}, again compute small cases:

k |
m |
T |

0 |
1 |
0 |

1 |
1 |
1 |

0 |
2 |
0 |

1 |
2 |
max(0, (1/2)(1+0)) = 1/2 |

2 |
2 |
1 |

0 |
3 |
0 |

1 |
3 |
max(-1/3, (1/3)(0)+(2/3)(1/2)) = 1/3 |

2 |
3 |
max(1/3, (2/3)(1/2)+(1/3)(1)) = 2/3 |

3 |
3 |
1 |

Now the obvious guess is T_{2}(k,m) = k/m. Again we verify:

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

## 2.1. Solution

Express X = ∑ X

_{i}where X_{i}, i=1..n, is the number of coin-flips in the interval following the (i-1)-th head and ending with the i-th head. Then the X_{i}are all identically distributed, and for each we have EX_{i}= 1 + (1-p)EX_{i}giving EX_{i}= 1/p and EX = n/p.This is tricky. The easiest way to get the bound is to observe that the event [X > (1+δ)n/p] occurs precisely when, among the first (1+δ)n/p coin-flips, there are fewer than n heads. The expected number of heads is μ = p((1+δ)n/p) = (1+δ)n, so we are asking if there are fewer than (1/(1+δ))μ = (1-δ/(1+δ))μ heads. Applying the Chernoff lower bound exp(-μδ

^{2}/2) with δ ← δ/(1+δ) gives a bound on this probability of exp(-μδ^{2}/2(1+δ)^{2}) = exp(-nδ^{2}/2(1+δ)p).

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

## 3.1. Solution

Use the method of bounded differences, applied to the function f(x_{1}...x_{n},y_{1}...y_{n}) that computes the length of any longest common subsequence of x and y. It is easy to see that this function is Lipschitz. If we change exactly one y_{i}, for example, then we can reduce the length of the LCS by at most one (since given any LCS that includes y_{i}, we can get a shorter common subsequence by deleting it). But this also means that we can only increase the length of the LCS by at most one as well, since if we could change y_{i} to y'_{i} and increase the LCS by more than one, then changing y'_{i} to y_{i} would decrease the LCS by more than one, contradicting our previous observation.

The Azuma-Hoeffding inequality now gives Pr[|X-EX| ≥ λ√(2n)] ≤ 2 exp(-λ^{2}/2) or Pr[|X-EX| ≥ α] ≤ 2 exp(-α^{2}/4n).