9. Remember that if X is a random variable and E[X] 2 a, then X 2 a with positive probability. This is great, but how can we actually find an instance of X where X 2 a? (a) Suppose X is a random variable taking values in {1, 2,..., k} and that f is some function with Elf(X)] 2 a. One way to find an r with 1 S r S k and /(z) 2 a is to just try all possibilities for a and plug them into f. How many times would you need to evaluate f to use this method? (b) Say X1...., Xn are independent random variables, each taking values (1, 2, ..., k) and now f is some function with Elf(X1,. .., X.)] 2 a. Using the same idea from part (a), how many evaluations of f would you need in order to find 21, .... In with f(F1. .... I.) 2 a? Here's another strategy for finding ($1, .. .. En) with f(31, . . ., x.) 2 a (c) Set gi(z) to be the conditional expectation 91(z) = Elf(X1. ..., Xn) [ X1 = =]. Show that Ex, [gi (X1)] 2 a and determine how many evaluations of g1 you need in order to find z, with g(21) 2 a. (d) Now let ga(z) be the conditional expectation g(z) = Elf(X1,... . X) |X1 = $1, X2 = =], where r, is from part (c). Argue that Elg2(X2)] 2 a and determine how many evaluations of 92 you need to find z, with g(12) 2 0. (e) Repeat the above process n times. On the i-th step, define the conditional expectation gi(1) = EU(X1,-.., X,) |X1=21.....Xi-1 =1,-I,X, = =], where r, is such that g, (z,) 2 a for cach j