1. Peaks and valleys
Suppose we flip a fair coin n times. For each i, 1≤i≤n, let Xi be the indicator of the event that the i-th coin-flip is heads. For each i, 2≤i≤n-1, let Yi be the indicator for the event that Xi-1=0, Xi=1, and Xi+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 X1...Xn be the indicator variables for independent coin-flips with bias p; that is, each Xi is 1 with probability p and 0 with probability 1-p. Let .
Use the expected value above and Markov's inequality to compute an upper bound on Pr[S≥m] = Pr[eS≥em].
- 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 zk coefficient gives the number of ways to buy a single amino acid for k dollars.
Write a generating function such that the zk 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.