Let n be a large power of two (thus, log n is an integer). Consider a binary string s = s_1 s_2...s_n, whore each bit s_i is 0 with probability 1/2, and 1 with probability 1/2, independently of the other bits. A run of length k is a substring of length k, all of whose bits are equal. In class, we have seen that it is very likely that the bit string s contains a run of length at least log n-2 log log n. In this exercise, you will prove that it is very unlikely that s contains a run of length more than 2 log n. Let k be an integer with 1 lessthanorequalto k lessthanorequalto n. Define the event A = "the bit string s contains a run of length at least k". For each t with 1 lessthanorequalto i lessthanorequalto n - k + 1, define the event A_i = "the substring s_i s_i + 1...s_i+k-1 is a run". Use the Union Bound (Lemma 5.3.5 on page 135 of the textbook) to prove that Pr(A) lessthanorequalto n - k + 1/2^k - 1 Let k = 2 log n. Prove that Pr(A) lessthanorequalto 2