/Solutions

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 be the random variable counting the number of peaks in the sequence.

1. What is E[S]?
2. 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 .

1. Compute E[e^S].

2. Use the expected value above and Markov's inequality to compute an upper bound on Pr[S≥m] = Pr[e^S≥e^m].

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

1. Write a generating function such that the z^k coefficient gives the number of ways to buy a single amino acid for k dollars.

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

3. Give a simple expression for the number of strands of length n that cost k dollars.