{"id":783,"date":"2016-07-16T13:22:32","date_gmt":"2016-07-16T18:22:32","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=783"},"modified":"2016-07-18T03:43:13","modified_gmt":"2016-07-18T08:43:13","slug":"random-walk-with-endpoints","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/random-walk-with-endpoints\/","title":{"rendered":"Random walk with endpoints"},"content":{"rendered":"

<\/p>The Riddler post<\/a> for today is about a bar game where you flip a coin and move forward or backward depending on the result. Here is the problem:\n

\nConsider a hot new bar game. It\u2019s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. (It\u2019s a very, very long bar.) You are assigned a winning number, the negative integer -X, and your friend is assigned his own winning number, a positive integer, +Y. A marker is placed at zero on the number line. Then the coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)<\/p>\n
How long can you expect to sit, flipping a coin, at the bar? Put another way, what is the expected number of coin flips in a complete game?\n<\/p><\/blockquote>\n
Here is my solution:
\n [Show Solution]<\/a><\/p>\n
\n
This problem is famously known as Gambler\u2019s ruin<\/a> and it\u2019s an example of a one-dimensional random walk<\/a>. In the typical Gambler\u2019s ruin setup, you flip a coin repeatedly and either gain \\$1 or lose \\$1 depending on the outcome. You have a fixed starting budget and a desired goal amount. You keep playing until either you have reached your goal amount, or you run out of money. The bar game we\u2019re looking at here is precisely Gambler\u2019s ruin, but shifted so that you start with \\$0 and end when you\u2019re either up \\$Y or you\u2019re \\$X in debt.<\/p>\n
Here is one possible solution. Let\u2019s define $E_n$ to be the expected number of coin flips in a complete game assuming the marker starts at location $n$ on the number line. We would like to find $E_0$. Suppose that at each flip, we move forward with probability $p$ and backward with probability $q$ (where $p+q=1$). If we are currently at $n$, then with probability $p$, we came from $n-1$ and with probability $q$ we came from $n+1$. Either way, we incurred one additional flip. We can therefore write the following recurrence relations for the expected number of coin flips:<\/p>\n
\\begin{align}
\nE_{-X} &= 0 \\\\
\nE_n &= p E_{n-1} + q E_{n+1} + 1 \\qquad\\text{for }-X < n < Y\\\\
\nE_Y &= 0
\n\\end{align}<\/p>\n
In matrix form, these equations look like:<\/p>\n
\\[
\n\\begin{bmatrix}
\n1 & -q & 0 & \\dots & 0 \\\\
\n-p & 1 & -q & \\ddots & \\vdots \\\\
\n0 & -p & 1 & \\ddots & 0 \\\\
\n\\vdots & \\ddots & \\ddots & \\ddots & -q \\\\
\n0 & \\dots & 0 & -p & 1
\n\\end{bmatrix}
\n\\begin{bmatrix}
\nE_{-X+1} \\\\ E_{-X+2} \\\\ \\vdots \\\\ E_{Y-2} \\\\ E_{Y-1}
\n\\end{bmatrix}
\n=
\n\\begin{bmatrix}
\n1 \\\\ 1 \\\\ \\vdots \\\\ 1 \\\\ 1
\n\\end{bmatrix}
\n\\]<\/p>\n
This system of equations has a nice structure; the matrix on the left is both tridiagonal<\/a> and Toeplitz<\/a>. One can solve this system of equations using a specialized form of Gaussian elimination<\/a>, for example.<\/p>\n
Although the equations have a closed-form solution, it is pretty messy. Instead, I\u2019ll show how you can derive the answer by hand in the case $p=q=\\tfrac{1}{2}$. The last equation can be solved for $E_{Y-1}$ in terms of $E_{Y-2}$:<\/p>\n
\\[
\nE_{Y-1} = \\tfrac{1}{2} E_{Y-2} + 1
\n\\]<\/p>\n
We can then substitute this into the second equation and solve for $E_{Y-2}$ in terms of $E_{Y-3}$:<\/p>\n
\\[
\nE_{Y-2} = \\tfrac{2}{3} E_{Y-3} + 2
\n\\]<\/p>\n
Substitute into the third equation and solve for $E_{Y-3}$ in terms of $E_{Y-4}$:<\/p>\n
\\[
\nE_{Y-3} = \\tfrac{3}{4} E_{Y-4} + 3
\n\\]<\/p>\n
The pattern is now clear (you can prove it using induction if you like). Continuing in this fashion until we get to the starting point,<\/p>\n
\\[
\nE_{1} = (1- \\tfrac{1}{Y}) E_{0} + Y \u2013 1
\n\\]<\/p>\n
We can do something similar but starting from the other end. e.g. solving for $E_{-X+1}$ in terms of $E_{-X+2}$, and then $E_{-X+2}$ in terms of $E_{-X+3}$, and so on. This time, we obtain the result:<\/p>\n
\\[
\nE_{-1} = (1- \\tfrac{1}{X}) E_0 + X \u2013 1
\n\\]<\/p>\n
We can now combine the fruits of our labor with the only equation we haven\u2019t used yet, which relates $E_0$, $E_1$, and $E_{-1}$. The result is that:<\/p>\n
\\begin{align}
\nE_0 &= \\tfrac{1}{2} E_{-1} + \\tfrac{1}{2} E_1 + 1 \\\\
\n&= \\tfrac{1}{2}\\left( (1- \\tfrac{1}{X}) E_0 + X \u2013 1 \\right) + \\tfrac{1}{2} \\left( (1 \u2013 \\tfrac{1}{Y}) E_0 + Y \u2013 1 \\right) + 1\\\\
\n&= \\tfrac{1}{2}\\left( 2- \\tfrac{1}{X} \u2013 \\tfrac{1}{Y} \\right) E_0 + \\tfrac{1}{2}(Y + X)
\n\\end{align}<\/p>\n
Rearranging and solving for $E_0$, we obtain:<\/p>\n
$\\displaystyle
\nE_0 = \\frac{ Y + X }{ \\tfrac{1}{X} + \\tfrac{1}{Y} } = XY
\n$<\/span><\/p>\n
A similar approach can be used to compute the probability that each player will win. To do this, let $P^Y_n$ be the probability that we\u2019ll reach $Y$ first given that we are currently at $n$, and similarly define $P^X_n$. Then the recursions look like:<\/p>\n
\\begin{align}
\nP^Y_{-X} &= 0 \\\\
\nP^Y_n &= p P^Y_{n-1} + q P^Y_{n+1} \\qquad\\text{for }-X < n < Y\\\\
\nP^Y_Y &= 1
\n\\end{align}<\/p>\n
Written as matrices, the only difference between this problem and that of finding expectation is the right-hand side of the equation! Using a similar recursive approach, we can solve the equations and we obtain:<\/p>\n
$\\displaystyle
\nP_0^X = \\frac{Y}{X+Y} \\qquad\\text{and}\\qquad P_0^Y = \\frac{X}{X+Y}
\n$<\/span><\/p>\n
So, practically speaking, if we must travel twice as far on the number line as our opponent, we are half as likely to win the game. Just for fun, I made some plots that show how the expected value and the probability of winning change if you\u2019re not using a fair coin. The plots show the case where $X+Y = 50$. For example, the 40% curve means that the coin flips in your favor 40% of the time.<\/p>\n
$\"bargame_E\"$ <\/a><\/p>\n
$\"bargame_P\"$ <\/a><\/p>\n
If you\u2019re interested in a derivation of the solution for the case $p\\ne \\tfrac{1}{2}$, there is a well-written set of notes here<\/a>.<\/p>\n<\/div>\n
and here is a much slicker solution, courtesy of Daniel Ross<\/a>:
\n [Show Solution]<\/a><\/p>\n
\n
Define the random variables $\\{Z_i\\}$ and $S_k$ as:<\/p>\n
\\[
\nZ_i = \\begin{cases} 1 & \\text{the }i^\\text{th}\\text{ flip is }H \\\\
\n-1 & \\text{the }i^\\text{th}\\text{ flip is }T
\n\\end{cases}
\n\\qquad\\text{and}\\qquad S_k = \\sum_{i = 1}^k Z_i
\n\\]<\/p>\n
Also, let $T$ be the random variable corresponding to the duration of the game. Therefore, $S_T$ is a random variable whose only possible values are $-X$ with probability $r$, or $Y$ with probability $(1-r)$. <\/p>\n
Wald\u2019s equation<\/a> and Wald\u2019s second equation<\/a> (sometimes also called the Blackwell-Girshick equation) give expressions for the mean and variance of random-length sums of identically distributed random variables:<\/p>\n
\\begin{align}
\n\\mathbb{E}(T) \\mathbb{E}(Z_1) &= \\mathbb{E}(S_T)\\\\
\n\\mathbb{E}(T) \\mathrm{Var}(Z_1) &= \\mathbb{E}\\left( (S_T\u2212 \\mathbb{E}(Z_1) T )^2 \\right)
\n\\end{align}<\/p>\n
Since $\\mathbb{E}(Z_1) = 0$, the first equation simplifies to $0 = -rX + (1-r)Y$. Solving for $r$, we obtain<\/p>\n
\\[
\nr = \\mathbb{P}(\\text{game ends at } \u2013 X) = \\frac{Y}{X+Y}
\n\\]<\/p>\n
Since $\\mathrm{Var}(Z_1) = 1$, the second equation is $\\mathbb{E}(T) = rX^2 + (1-r)Y^2$. Substituting the value we found for $r$, we obtain<\/p>\n
\\[
\n\\mathbb{E}(T) = \\frac{Y}{X+Y} X^2 + \\frac{X}{X+Y} Y^2 = XY
\n\\]<\/p>\n
and that\u2019s it!<\/p>\n<\/div>\n
<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"
The Riddler post for today is about a bar game where you flip a coin and move forward or backward depending on the result. Here is the problem: Consider a hot new bar game. It\u2019s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. … Continue reading “Random walk with endpoints”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[16,8,21,15,2],"class_list":["post-783","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-dynamic-programming","tag-probability","tag-random-walk","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/783","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=783"}],"version-history":[{"count":36,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/783\/revisions"}],"predecessor-version":[{"id":823,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/783\/revisions\/823"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}