Solve the following problems using linearity of expectation. Clearly explain the steps. (For each problem you will want to think about what the appropriate random variables should be and define them explicitly.)

(a) A coin with probability p of coming up heads is tossed independently n times. What is the expected number of occurrences of the string HH? For example, in HHHTHHT, it occurs 3 times, once starting at position 1, once starting at position 2 and once starting at position 5.

(b) A random string of 100,000 characters is written down, where each character is independently, equally likely to be any of the upper-case letters A through Z in English. What is the total expected number of occurrences of the sequences "FOOFOO" and "OOFOOF"? For example, in the sequence ABOFOOFOOFOO, the sequence FOOFOO occurs twice (once starting at the 4th character, and once starting at the 7th character), and OOFOOF occurs once (starting at the 5th character).