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

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

# 2. Stronger than Markov

Let X_{1}...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 .

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.