Suppose that a sequence of items passes by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen so far. Moreover we do not know the total number of items in advance and we cannot store more than one item at any time. (a) Consider the following algorithm. When the first item appears, we store it. When the k-th item appears, we replace the stored item with probability 1/k. Show that this algorithm solves the problem. (b) Now suppose that when the k-th item appears, we replace the stored item with probability 1/2. What is the distribution of the stored item in this case?