7. (book # 3.7) A simple model of the stock market suggests that, each day, a stock with price & will increase by a factor > > 1 to er with probability p and will fall to x/r with probability q = 1-p. Assuming we start with a stock with price Xo = 1, find a formula for the expected value E(X,) and the variance Var(X) of the price Xy of the stock after d days. That is, Xy is the stock price after d changes (increase or decrease). Hint: Let Y = number of days when the price increases. Then Y ~ Bin(d, p) and Xd = ry . (1/r)d-Y. To evaluate the expression for E(X), use the binomial theorem (see lecture #3.4). You can state the binomial theorem as I Came = (a + 6)n (why?). 7a. Evaluate your solution for E(X) for d = 60, r = 1.05 and p = 0.6, E(XJ) = 7b. Evaluate your solution for Var(X) for d = 60, r = 1.05 and p = 0.6, Var( Xd) = 8. (book #3.8) Suppose that we have an algorithm that takes as input a string of n bits. We are told that the expected running time is O(n') if the input bits are chosen independently and uniformly at random. That is. letting X, denote the running time with an input of size n, E(X,) 0 and Pr(X, = x,) 2 2-" (2, since more than one sequence might have a given running time I, ). What can Markov's inequality tell us about the worst-case running time a$ of this algorithm on inputs of size n? Nothing to turn in