No more information is require.

(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 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 1/4 SO S2 1 1/4 2/3 SI $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 ($0,50,$1,53,82) 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 E 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?) (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 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 1/4 SO S2 1 1/4 2/3 SI $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 ($0,50,$1,53,82) 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 E 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?)