(50 pts.) Markov Chains Markov chains are a mathematical model of stochastic processes where random decisions are made at suc- cessive time steps, each depending only on the current state of the system and not its past history. They are used in a huge variety of applications, both in computer science (natural language processing, compression, queueing theory) and other fields including physics, biology, economics, chemistry, you name it (they are the basis of so-called Markov chain Monte Carlo algorithms universally used in the sciences to estimate the best model parameters matching observed data). Formally, a Markov chain is a directed graph M whose vertices are the set S of possible states (with a des- ignated start state so), and whose edges indicate the possible random choices: for each state s, the outgoing edges have weights which sum to 1 (self-loops being allowed), and the probability of following a particular edge is its weight. For example: 1/2 SO 1/4 $1 1/4 1 $2 2/3 $3 1/3 1 If we take a random walk in a Markov chain for k steps starting from so, then every possible path has a probability given by multiplying all of the weights of the edges along the path: for instance, in our example above, the path (so, S0, S1,S3,S2) has probability (1/2). (1/4). (1)-(2/3)=1/12. One basic question about Markov chains is the following: given a Markov chain M, a start state so S, and an ending state g = S, what is the most likely path to take from so to g? Describe an efficient algorithm to solve this problem. (Hint: If the probability of a path were the sum of the weights instead of the product, this would look like a problem you've seen before. Can you transform the weights so that maximizing their sum is equivalent to maximizing the product of the original weights?) The time it takes an individual popcorn kernel to pop conforms to a normal distribution very closely. Assume that the mean time to popping is 165.0 seconds with a standard deviation of 92.1 seconds. What is the probability that a kernel of popcorn would take longer than 200 seconds to pop? Give your answer to five decimal places. Use Statistical Table B. probability: What is the probability that a kernel of popcorn would pop in less than 120 seconds? Give your answer to five decimal places. Use Statistical Table B. probability: