Problem

1. Given a stream of n numbers, show how to select one uniformly at random using only constant storage. What if you don't know n in advance?

2. A k-streak starts at toss i in a sequence of n coin flips when the outcome of the ith flip and the next k - 1 flips are identical. For example, sequence HTTTHH contains 2-streaks starting at the second, third, and fifth tosses. What are the expected number of k-streaks that you will see in n tosses of a fair coin?