DOC PREVIEW
MIT 6 042J - Random Processes

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 19 Random Processes Random Walks are used to model situations in which an object moves in a sequence of steps in randomly chosen directions. For example in Physics, three-dimensional random walks are used to model Brownian motion and gas diffusion. In this chap-ter we’ll examine two examples of random walks. First, we’ll model gambling as a simple 1-dimensional random walk —a walk along a straight line. Then we’ll explain how the Google search engine used random walks through the graph of world-wide web links to determine the relative importance of websites. 19.1 Gamblers’ Ruin a Suppose a gambler starts with an initial stake of n dollars and makes a sequence of $1 bets. If he wins an individual bet, he gets his money back plus another $1. If he loses, he loses the $1. We can model this scenario as a random walk between integer points on the reall line. The position on the line at any time corresponds to the gambler’s cash-on-hand or capital. Walking one step to the right (left) corresponds to winning (losing) a $1 bet and thereby increasing (decreasing) his capital by $1. The gambler plays until either he is bankrupt or increases his capital to a target amount of T dollars. If he reaches his target, then he is called an overall winner, and his profit, m, will be T − n dollars. If his capital reaches zero dollars before reaching his target, then we say that he is “ruined” or goes broke. We’ll assume that the gambler has the same probability, p, of winning each individual $1 bet and that the bets are mutually independent. We’d like to find the probability that the gambler wins. The gambler’s situation as he proceeds with his $1 bets is illustrated in Fig-ure 19.1. The random walk has boundaries at 0 and T . If the random walk ever reaches either of these boundary values, then it terminates. In a fair game, the gambler is equally likely to win or lose each bet, that is p = 1/2. The corresponding random walk is called unbiased. The gambler is more likely to win if p > 1/2 and less likely to win if p < 1/2; these random walks are called 445446 CHAPTER 19. RANDOM PROCESSES capitalgambler’snT = n + mtimebet outcomes:WLLWLWWLLLFigure 19.1: This is a graph of the gambler’s capital versus time for one possible sequence of bet outcomes. At each time step, the graph goes up with probability p and down with probability 1 − p. The gambler continues betting until the graph reaches either 0 or T . biased. We want to determine the probability that the walk terminates at boundary T , namely, the probability that the gambler is a winner. We’ll do this by showing that the probability satisfies a simple linear recurrence and solving the recurrence, but before we derive the probability, let’s just look at what it turns out to be. Let’s begin by supposing the coin is fair, the gambler starts with 100 dollars, and he wants to double his money. That is, he plays until he goes broke or reaches a target of 200 dollars. Since he starts equidistant from his target and bankruptcy, it’s clear by symmetry that his probability of winning in this case is 1/2. We’ll show below that starting with n dollars and aiming for a target of T ≥ n dollars, the probability the gambler reaches his target before going broke is n/T . For example, suppose he want to win the same $100, but instead starts out with $500. Now his chances are pretty good: the probability of his making the 100 dollars is 5/6. And if he started with one million dollars still aiming to win $100 dollars he almost certain to win: the probability is 1M/(1M + 100) > .9999. So in the fair game, the larger the initial stake relative to the target, the higher the probability the gambler will win, which makes some intuitive sense. But note that although the gambler now wins nearly all the time, the game is still fair. When he wins, he only wins $100; when he loses, he loses big: $1M. So the gambler’s average win is actually zero dollars. Now suppose instead that the gambler chooses to play roulette in an American casino, always betting $1 on red. A roulette wheel has 18 black numbers, 18 red numbers, and 2 green numbers, designed so that each number is equally likely to appear. So this game is slightly biased against the gambler: the probability of winning a single bet is p = 18/38 ≈ 0.47. It’s the two green numbers that447 19.1. GAMBLERS’ RUIN slightly bias the bets and give the casino an edge. Still, the bets are almost fair, and you might expect that starting with $500, the gambler has a reasonable chance of winning $100 —the 5/6 probability of winning in the unbiased game surely gets reduced, but perhaps not too drastically. Not so! The gambler’s odds of winning $100 making one dollar bets against the “slightly” unfair roulette wheel are less than 1 in 37,000. If that seems surprising, listen to this: no matter how much money the gambler has to start —$5000, $50,000, $5 1012 —his odds are still less than 1 in 37,000 of winning a mere 100 dollars! · Moral: Don’t play! The theory of random walks is filled with such fascinating and counter-intuitive conclusions. 19.1.1 A Recurrence for the Probability of Winning The probability the gambler wins is a function of his initial capital, n, his target, T ≥ n, and the probability, p, that he wins an individual one dollar bet. Let’s let p and T be fixed, and let wn be the gambler’s probabiliity of winning when his initial capital is n dollars. For example, w0 is the probability that the gambler will win given that he starts off broke and wT is the probability he will win if he starts off with his target amount, so clearly w0 = 0, (19.1) wT = 1. (19.2) Otherwise, the gambler starts with n dollars, where 0 < n < T . Consider the outcome of his first bet. The gambler wins the first bet with probability p. In this case, he is left with n + 1 dollars and becomes a winner with probability wn+1. On the other hand, he loses the first bet with probability q ::= 1 − p. Now he is left with n−1 dollars and becomes a winner with probability wn−1. By the Total Probability Rule, he wins with probability wn = pwn+1 + qwn−1. Solving for wn+1 we have wn+1 = wn − rwn−1 (19.3) p where q r ::= . p This recurrence holds only for n + 1 ≤ T , but there’s no harm in using (19.3) to define wn+1 for all n + 1 > 1. Now, letting W (x) ::= w0 + w1x +


View Full Document

MIT 6 042J - Random Processes

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Random Processes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Random Processes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Random Processes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?