[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


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 zj = xf(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| ≥ α.

2014-06-17 11:58