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. Peaks and valleys

Suppose we flip a fair coin n times. For each i, 1≤i≤n, let X_i be the indicator of the event that the i-th coin-flip is heads. For each i, 2≤i≤n-1, let Y_i be the indicator for the event that X_i-1=0, X_i=1, and X_i+1=0; if this even occurs we say that the sequence of coin-flips has a peak at i. Let $S = \sum_{i=2}^{n-1} Y_i$ be the random variable counting the number of peaks in the sequence.

What is E[S]?
What is Var[S]?

2. Stronger than Markov

Let X₁...X_n be the indicator variables for independent coin-flips with bias p; that is, each X_i is 1 with probability p and 0 with probability 1-p. Let $S = \sum_{i=1}^{n} X_i$ .

Compute E[e^S].
Use the expected value above and Markov's inequality to compute an upper bound on Pr[S≥m] = Pr[e^S≥e^m].
Can you find values of p, n, and m, for which this bound is smaller than the bound E[S]/m given by a direct application of Markov's inequality?

3. At the genome factory

A custom gene splicing shop charges $2 to splice a thymine (T) amino acid into a single-strand DNA fragment, and $1 each for adenine (A) and cytosine (C). Guanine (G) is free. So, for example, constructing the sequence GATTACA costs 0+1+2+2+1+1+1=8 dollars.

Write a generating function such that the z^k coefficient gives the number of ways to buy a single amino acid for k dollars.
Write a generating function such that the z^k coefficient gives the number of ways to buy a single DNA strand consisting of n amino acids for k dollars.
Give a simple expression for the number of strands of length n that cost k dollars.