6.042/18.] Mathematics for Computer Science May10,2005 Srini devadas and Eric Lehman Lecture notes Random walks 1 Random walks a drunkard stumbles out of a bar staggers one step to the right, with a canal lies y steps to his right. Thi I equal p second, he either staggers one step to the left or probability. His home lies r steps to his left, and everal natural questions, including 1. What is the probability that the drunkard arrives safely at home instead of falling into the canal? 2. What is the expected duration of his journey however it ends? The drunkard's meandering path is called a random walk. Random walks are an im- portant subject, because they can model such a wide array of phenomena. For example, in physics, random walks in three-dimensional space are used to model gas diffusion In computer science, the Google search engine uses random walks through the graph of determine the relative importance of websites. In finance theory, random walks can serve as a model for the fluctuation of market prices. And, in this lecture, we'll explore some more palatable applications 2 Pass the Candy Pass the Candy is game involving n students, one professor, and a bowl of candy. The students are numbered 1 to n, and the professor is numbered 0. Everyone stands in a circle as shown below
6.042/18.062J Mathematics for Computer Science May 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Random Walks 1 Random Walks A drunkard stumbles out of a bar. Each second, he either staggers one step to the left or staggers one step to the right, with equal probability. His home lies x steps to his left, and a canal lies y steps to his right. This are several natural questions, including: 1. What is the probability that the drunkard arrives safely at home instead of falling into the canal? 2. What is the expected duration of his journey, however it ends? The drunkard’s meandering path is called a random walk. Random walks are an important subject, because they can model such a wide array of phenomena. For example, in physics, random walks in threedimensional space are used to model gas diffusion. In computer science, the Google search engine uses random walks through the graph of web links to determine the relative importance of websites. In finance theory, random walks can serve as a model for the fluctuation of market prices. And, in this lecture, we’ll explore some more palatable applications. 2 Pass the Candy Pass the Candy is game involving n students, one professor, and a bowl of candy. The students are numbered 1 to n, and the professor is numbered 0. Everyone stands in a circle as shown below. 1 2 3 n/2 n−2 n−1 n 0 (professor)
Random Walks Initially, the professor has the candy bowl. He withdraws a piece of candy and ther asses the bowl either left or right, with equal probability. Each person who receives the bowl thereafter does the same thing: he or she takes a piece of candy from the bowl and then passes it either left or right, with equal probability. In effect, the bowl goes for a random walk around the circle of players. The last person to receive a piece of candy is declared the winner and gets to keep the entire bowl which player is most likely to win? A natural guess is player n/2. She seems most likely to receive the bowl last and thus to win the game, because she is farthest from the professor. On the other hand, players 1 and n seem almost certain to receive the bowl far too early in the process to win the game Let's see if this intuition is right or wrong! 1 A Simpler problem Let's begin by looking at a simpler problem. Suppose that the players are arranged in a line, rather than a circle The players are named A, S1, s2,..., Sk, and B, as shown. Initially, player si has the candy bowl. As before, whenever a player gets the bowl, he or she takes a piece of candy and then passes the bowl either left or right, with equal probability. What is the probability that a gets candy before b? Let Pk be the probability that a gets candy before B. First, suppose that k=1 A S B Here, either A or B gets the bowl on the next step, with equal probability. Thus, Pi=2 e Now suppose that k >1. In the first step, there are two possibilities: the bowl either oves left to player A or moves right to player S2. We can break up the evaluation of Ph into these two cases using the law of total probability: Ph=Pr(first step is left I first step is left) +Pr(first step is righ Pr(a gets candy before B first step is right) Pr(a gets candy before B first
2 Random Walks Initially, the professor has the candy bowl. He withdraws a piece of candy and then passes the bowl either left or right, with equal probability. Each person who receives the bowl thereafter does the same thing: he or she takes a piece of candy from the bowl and then passes it either left or right, with equal probability. In effect, the bowl goes for a random walk around the circle of players. The last person to receive a piece of candy is declared the winner and gets to keep the entire bowl. Which player is most likely to win? A natural guess is player n/2. She seems most likely to receive the bowl last and thus to win the game, because she is farthest from the professor. On the other hand, players 1 and n seem almost certain to receive the bowl far too early in the process to win the game. Let’s see if this intuition is right or wrong! 2.1 A Simpler Problem Let’s begin by looking at a simpler problem. Suppose that the players are arranged in a line, rather than a circle: A S1 S2 . . . Sk B ↑ candy The players are named A, S1, S2, . . ., Sk, and B, as shown. Initially, player S1 has the candy bowl. As before, whenever a player gets the bowl, he or she takes a piece of candy and then passes the bowl either left or right, with equal probability. What is the probability that A gets candy before B? Let Pk be the probability that A gets candy before B. First, suppose that k = 1: A S1 B ↑ candy Here, 1 either A or B gets the bowl on the next step, with equal probability. Thus, P1 = . 2 Now suppose that k > 1. In the first step, there are two possibilities: the bowl either moves left to player A or moves right to player S2. We can break up the evaluation of Pk into these two cases using the law of total probability: Pk = Pr (first step is left) ·Pr (A gets candy before B | first step is left) + Pr (first step is right) ·Pr (A gets candy before B | first step is right) 1 1 = 1 + · Pr (A gets candy before B | first step is right) 2 · 2
Random walks To evaluate the last term, we must find the probability that a gets candy before B starting from this configuration A 1 s S B candy This is a little tricky. From here, the candy must eventually reach either S1 or B. In fact,we know that Si gets the candy before B with probability Pk-1.(In effect, we are considering a smaller version of the problem, in which Si plays the role of A. )If this happe b with we are back in the original configuration and so a goes on to get the candy before b with probability PA. Therefore, starting from the configuration above, a gets the candy before B with probability Pk-1. Pk. Substituting this result into the equation above gives 1 Pk Solving for Pk and adding in the base case gives a complete recurrence Pk Pk (k≥0) 2.2 Solving the Recurrence Equation We now have a recurrence for Pk, the probability that player a gets the candy before player B. A recurrence is good, but an explicit formula for Pk would be better. The simplest technique for obtaining an explicit formula from a recurrence is called guess and verify. The name says it all: we compute a few terms, guess a general pattern, and then verify the result Let's apply the guess-and-verify method to our problem. First, we compute a few terms using the recurrence
Random Walks 3 To evaluate the last term, we must find the probability that A gets candy before B starting from this configuration: A S1 S2 . . . Sk B ↑ candy This is a little tricky. From here, the candy must eventually reach either S1 or B. In fact, we know that S1 gets the candy before B with probability Pk−1. (In effect, we are considering a smaller version of the problem, in which S1 plays the role of A.) If this happens, then we are back in the original configuration, and so A goes on to get the candy before B with probability Pk. Therefore, starting from the configuration above, A gets the candy before B with probability Pk−1 · Pk. Substituting this result into the equation above gives: 1 1 Pk 2 = · 1 + 2 · Pk−1 · Pk Solving for Pk and adding in the base case gives a complete recurrence: P1 Pk 1 1 2 = = 2 − Pk−1 (k ≥ 0) 2.2 Solving the Recurrence Equation We now have a recurrence for Pk, the probability that player A gets the candy before player B. A recurrence is good, but an explicit formula for Pk would be better. The simplest technique for obtaining an explicit formula from a recurrence is called guess and verify. The name says it all: we compute a few terms, guess a general pattern, and then verify the result. Let’s apply the guessandverify method to our problem. First, we compute a few terms using the recurrence:
Random Walks P 1-2_22-3_23-4 The general pattern appears to be PK k+1 All that remains is to verify that our guess is correct. We can use induction on k with the hypothesis that Pk= k/(k+1). This holds for k= l, because Pi=) is the base case of the recurrence. Next, we assume Pk=k/(k+ 1)in order to prove Pk+1=(k+1)/(k+2) We can reason as follows 1 Pk Pk 2 k+1 k+2 The first step uses the recurrence equation, the second uses the induction hypothesis, and the third uses only algebra. Thus, by induction, P*=k/(+1) for all> 1 Therefore, player A receives the candy before player B with probability k/(k+1). We'll se this conclusion repeatedly in the next section 2.3 Analyzing the Game Now let's return to the original problem. There are n players and a professor standing in a circle. If the professor has the candy initially, which player is most likely to get the candy last and thus win the game
4 Random Walks 1 P1 = 2 1 P2 = 2 − P1 2 = 3 1 P3 = 2 − P2 3 = 4 The general pattern appears to be: k Pk = k + 1 All that remains is to verify that our guess is correct. We can use induction on k with 1 the hypothesis that Pk = k/(k + 1). This holds for k = 1, because P1 = is the base case of 2 the recurrence. Next, we assume Pk = k/(k + 1) in order to prove Pk+1 = (k + 1)/(k + 2). We can reason as follows: 1 Pk+1 = 2 − Pk 1 = k 2 − k+1 k + 1 = k + 2 The first step uses the recurrence equation, the second uses the induction hypothesis, and the third uses only algebra. Thus, by induction, Pk = k/(k + 1) for all k ≥ 1. Therefore, player A receives the candy before player B with probability k/(k+1). We’ll use this conclusion repeatedly in the next section. 2.3 Analyzing the Game Now let’s return to the original problem. There are n players and a professor standing in a circle. If the professor has the candy initially, which player is most likely to get the candy last and thus win the game?
Random walks Let's begin by considering player n, who is standing just to the right of the professor The only way that player n can win the game is if the bowl travels clockwise all the way around the circle to player n-l before n ever touches it. How likely is that? Let's get another perspective by"cutting" the circle between players n-l and n and arranging m in a line n012 2n-1 candy We are asking for the probability that n-1 gets candy before n. But this is precisely the problem that we already solved! Here player n takes the role of A, player n-1 takes the role of B, and we have k=n-1 players between them. Therefore, player n gets the candy before player n-1 with probability(n-1)/. In complementary terms, player n-1 gets the candy before player n with probability 1/n. Thus, player n wins the game with probability 1/n This is a startling conclusion! At the beginning of lecture, we guessed that player had little chance of winning the game, because he was standing too close to the professor But weve just shown that player n has a l-in-n chance of winning. Not bad, since there are n players What are the winning chances for the other players? By symmetry, player 1 also wins with probability 1/n. So let's consider the probability that player i wins the game, where 1 <i<n. There are two cases: either player i+ 1 gets the bowl before player i-l or vice rsa. Applying the law of total probabilit ity, we get Pr(i wins)= Pr(i+ l gets candy before i-1) Pr(i wins i+ l gets candy be efore 7 +Pr(i-l gets candy before i+1 Pr(i wins |i-I gets candy before i+1) Let's begin by determining the probability that i wins, given that player+l gets candy before player i-1.(This is the second line in the formula. At the moment that player i+ l first gets candy, this must be the configuration of the game 2t+1 cand. Now player i wins the game only if player i-1 gets the candy before player i. Again, we can invoke our earlier result. Now i takes the role of a, i-1 takes the role of b and chere are k=n-1 players between them. Therefore, player i gets the candy before player
Random Walks 5 Let’s begin by considering player n, who is standing just to the right of the professor. The only way that player n can win the game is if the bowl travels clockwise all the way around the circle to player n − 1 before n ever touches it. How likely is that? Let’s get another perspective by “cutting” the circle between players n − 1 and n and arranging them in a line: n 0 1 2 . . . n − 2 n − 1 ↑ candy We are asking for the probability that n − 1 gets candy before n. But this is precisely the problem that we already solved! Here player n takes the role of A, player n − 1 takes the role of B, and we have k = n − 1 players between them. Therefore, player n gets the candy before player n − 1 with probability (n − 1)/n. In complementary terms, player n − 1 gets the candy before player n with probability 1/n. Thus, player n wins the game with probability 1/n. This is a startling conclusion! At the beginning of lecture, we guessed that player n had little chance of winning the game, because he was standing too close to the professor. But we’ve just shown that player n has a 1inn chance of winning. Not bad, since there are n players! What are the winning chances for the other players? By symmetry, player 1 also wins with probability 1/n. So let’s consider the probability that player i wins the game, where 1 < i < n. There are two cases: either player i + 1 gets the bowl before player i − 1 or vice versa. Applying the law of total probability, we get: Pr (i wins) = Pr (i + 1 gets candy before i − 1) ·Pr (i wins | i + 1 gets candy before i − 1) + Pr (i − 1 gets candy before i + 1) ·Pr (i wins | i − 1 gets candy before i + 1) Let’s begin by determining the probability that i wins, given that player i+1 gets candy before player i − 1. (This is the second line in the formula.) At the moment that player i + 1 first gets candy, this must be the configuration of the game: i i + 1 . . . n 0 1 . . . i − 1 ↑ candy Now player i wins the game only if player i − 1 gets the candy before player i. Again, we can invoke our earlier result. Now i takes the role of A, i − 1 takes the role of B, and there are k = n−1 players between them. Therefore, player i gets the candy before player