A place to share my thoughts and ideas with the world.
A Neat Random Walk Problem
Get link
Facebook
X
Pinterest
Email
Other Apps
-
As many of the people that read this blog probably know, I enjoy inventing math problems, especially problems that are probabilistic in nature, and then working out the math to solve that problem. In this blog post, I will introduce one problem that I solved that I think is particularly elegant:
You are randomly walking along the x-axis starting at \( x=0 \). When you are at \( x = n \), you move to \( x = n-1 \) with probability \( p = \frac{n}{n+1} \) and to \( x = n+1 \) with probability \( p = \frac{1}{n+1} \). What is the expected number of steps until you return to \( x = 0 \) for the first time?
This problem differs from standard random walk problems because the probability of moving left and right along the x-axis depends on your current location. In this problem, there is a force that is pulling you towards \( x = 0 \), and the further away you get, the more of an effect this force has on you.
So how do we go about solving this problem? When I first attempted the problem I attempted to setup an equation that described the situation. In particular, I defined a function \( f(n) \) to be the expected number of steps to reach \( x = 0 \) from \( x = n \). This was ultimately a dead end, but my key insight was fairly similar.
Let's define a function \( f(n) \) to be the expected number of steps to reach \( x = n-1 \) from \( x = n \). Then the answer to the original problem is simply \( 1 + f(1) \). To get some intuition about what this function needs to look like, we need to think about what can happen when you are at \( x = n \). No matter what you have to take 1 step. With probability \( p = \frac{n}{n+1} \) that is the only step you need to take, because that is the probability of moving to \( x = n-1 \) immediately. However, with probability \( p = \frac{1}{n+1} \) you need to take more steps. In this case, you end up at \( x = n+1 \) but you ultimately want to get back to \( x = n-1 \). To do that, we must first get back to \( x = n \) then we have to get to \( x = n-1 \). By definition of \(f\), the expected number of steps needed to complete this sequence of events is exactly \( f(n+1) + f(n) \). This gives rise to the following equation:
$$ f(n) = 1 + \frac{1}{n+1} [ f(n+1) + f(n) ] $$
Solving this equation for \( f(n) \) yields;
$$ f(n) = \frac{n + 1}{n} + \frac{f(n+1)}{n} $$
We've got an interesting situation here where we have a recurrence relation but no base case. Theoretically, if we knew \( f(n) \) for any \( n \geq 1 \), then we would know the value of \( f(n) \) for all \( n \) by repeatedly applying the formula. After carefully thinking about the problem, you will probability realize that as we get further away from \( x = 0 \), the expected number of steps to move one unit to the left will approach \( 1 \). Formally we have \( \lim_{n \rightarrow \infty} f(n) = 1 \). Let's take a deeper look at \( f(1) \) for a moment, which is ultimately what we are interested in finding:
\begin{align*}
f(1) &= \frac{2}{1} + \frac{f(2)}{1} \\
&= \frac{2}{1} + \frac{3}{2 \cdot 1} + \frac{f(3)}{2 \cdot 1} \\
&= \frac{2}{1} + \frac{3}{2 \cdot 1} + \frac{4}{3 \cdot 2 \cdot 1} + \frac{f(4)}{3 \cdot 2 \cdot 1} \\
&= \frac{2}{1!} + \frac{3}{2!} + \frac{4}{3!} + \frac{5}{4!} + \frac{f(5)}{5!} \\
&= \frac{2}{1!} + \frac{3}{2!} + \frac{4}{3!} + \dots + \frac{n+1}{n!} + \dots
\end{align*}
since \( \lim_{n \rightarrow \infty} \frac{f(n)}{n!} = 0 \), we have:
$$ f(1) = \sum_{n=1}^\infty \frac{n+1}{n!} $$
$$ 1 + f(1) = \sum_{n=0}^\infty \frac{n+1}{n!} $$
Now you might recognize this infinite series already but don't worry if you don't. The sum evaluates to exactly $ 2 e \approx 5.437 $. Here's why: let's define \( g(x) = e^x = \sum_{k=0}^\infty \frac{x^k}{k!} \) Then consider \( x g'(x) = x e^x = \sum_{k=1}^\infty \frac{k x^k}{k!} \). Now define \( h(x) = g(x) + x g'(x) = 1 + \sum_{k=1}^\infty \frac{(k+1) x^k}{k!} \). This looks familiar! In fact, \( 1 + f(1) = h(1) = e^1 + 1 e^1 = 2 e \). There you have it! The expected number of steps to return to the origin is \( 2 e \).
This was a beautiful problem, and it has one of the most elegant solutions I have ever come up with. When I initially thought of the problem, I had no idea \( e \) was going to pop up in the answer so that was somewhat of a surprise. If you liked this problem, consider a new but very similar problem where the force is reversed:
You are randomly walking along the x-axis, starting at \( x = 1 \). When you are at \( x = n \), you move to \( x = n-1 \) with probability \( p = \frac{1}{n+1} \) and you move to \( x = n+1 \) with probability \( p = \frac{n}{n+1} \). What is the probability that you eventually reach \( x = 0 \).
In this post, I will discuss my findings in terms of an optimal strategy for Farkle , which is a dice game of chance. If you are unfamiliar with the game, I encourage you to skim the linked article so that you can better understand this blog post. All of my findings are based on sound mathematical methods and a computer program was used to determine the optimal strategy. Before I begin, let me first state the value of different dice rolls I assumed while developing the strategy. Each 1: 100 points Each 5: 50 points 3 1's: 1000 points 3 2's: 200 points ... 3 6's: 600 points 4 1's: 2000 points ... 4 6's 1200 points 5 1's 3000 points ... 5 6's 1800 points Straight 1-6 1500 points 3 Pairs (e.g., 22 33 44): 750 points Everything else is considered to be a Farkle (0 points). There are many variants to Farkle, but I like to play by this set of rules. The "game state" of Farkle roll can roughly be characterized by 2 values: the curre...
A few weeks ago, I was using a Markov Chain as a model for a Project Euler problem, and I learned about how to use the transition matrix to find the expected number of steps to reach a certain state. In this post, I will derive the linear system that will help answer that question, and will work out specific an example using a 1-dimensional random walk as the model. Terminology Before I begin the derivation, let me define some terms. The transition matrix is an \( n \) by \( n \) matrix that describes how you can move from one state to the next. The rows of the transition matrix must always sum to 1. States can either be transient or absorbing . An absorbing state is one that cannot be left once reached (it transitions to itself with probability 1). A transient state is a state that is not an absorbing state. In many problems, it is of general interest to compute the expected number of steps to reach an absorbing state (from some start state). Derivation Let \...
In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di...
Comments
Post a Comment