Mixing
Random walk probability
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I encounter a problem:Consider a two dimensional map, with an x-axis (horizontal direction) and a y-axis (vertical direction). Coordinates on the map can therefore be represented as a two-dimensional vector (x, y).
A tourist is standing at coordinates (0, 0), and is looking for the the tourist information centre, located at coordinates (−10, 30). However, the tourist is completely lost and instead of asking for directions, begins a random walk to search for the tourist information centre.
The tourist moves one step at a time, either horizonally or vertically (but can not move diagonally). Steps can also be forwards (in a positive direction) or backwards (in a negative direction). Therefore, at every point, there are 4 possible moves the tourist can make. For instance, when standing at the origin (0,0), the tourist can move either to (0, 1), (0, −1), (1, 0) or (−1, 0), and has an equal probability of moving in each direction, thus a probability of 0.25 for each option. What is the probability that this tourist locates the tourist office in 1000 steps
or less?
Aaron Montgomery gave the hint that the simulation is a good way to estimate the probability. Could any expert give a full code, like the C++ or R code, to help us better understand this kind of question? Thanks in advance.
probability random-walk
asked Aug 2 at 17:59
Amy_777
204
add a comment |Â
up vote
3
down vote
favorite
I encounter a problem:Consider a two dimensional map, with an x-axis (horizontal direction) and a y-axis (vertical direction). Coordinates on the map can therefore be represented as a two-dimensional vector (x, y).
A tourist is standing at coordinates (0, 0), and is looking for the the tourist information centre, located at coordinates (−10, 30). However, the tourist is completely lost and instead of asking for directions, begins a random walk to search for the tourist information centre.
The tourist moves one step at a time, either horizonally or vertically (but can not move diagonally). Steps can also be forwards (in a positive direction) or backwards (in a negative direction). Therefore, at every point, there are 4 possible moves the tourist can make. For instance, when standing at the origin (0,0), the tourist can move either to (0, 1), (0, −1), (1, 0) or (−1, 0), and has an equal probability of moving in each direction, thus a probability of 0.25 for each option. What is the probability that this tourist locates the tourist office in 1000 steps
or less?
Aaron Montgomery gave the hint that the simulation is a good way to estimate the probability. Could any expert give a full code, like the C++ or R code, to help us better understand this kind of question? Thanks in advance.
probability random-walk
asked Aug 2 at 17:59
Amy_777
204
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I encounter a problem:Consider a two dimensional map, with an x-axis (horizontal direction) and a y-axis (vertical direction). Coordinates on the map can therefore be represented as a two-dimensional vector (x, y).
A tourist is standing at coordinates (0, 0), and is looking for the the tourist information centre, located at coordinates (−10, 30). However, the tourist is completely lost and instead of asking for directions, begins a random walk to search for the tourist information centre.
The tourist moves one step at a time, either horizonally or vertically (but can not move diagonally). Steps can also be forwards (in a positive direction) or backwards (in a negative direction). Therefore, at every point, there are 4 possible moves the tourist can make. For instance, when standing at the origin (0,0), the tourist can move either to (0, 1), (0, −1), (1, 0) or (−1, 0), and has an equal probability of moving in each direction, thus a probability of 0.25 for each option. What is the probability that this tourist locates the tourist office in 1000 steps
or less?
Aaron Montgomery gave the hint that the simulation is a good way to estimate the probability. Could any expert give a full code, like the C++ or R code, to help us better understand this kind of question? Thanks in advance.
probability random-walk
asked Aug 2 at 17:59
Amy_777
204
I encounter a problem:Consider a two dimensional map, with an x-axis (horizontal direction) and a y-axis (vertical direction). Coordinates on the map can therefore be represented as a two-dimensional vector (x, y).
A tourist is standing at coordinates (0, 0), and is looking for the the tourist information centre, located at coordinates (−10, 30). However, the tourist is completely lost and instead of asking for directions, begins a random walk to search for the tourist information centre.
The tourist moves one step at a time, either horizonally or vertically (but can not move diagonally). Steps can also be forwards (in a positive direction) or backwards (in a negative direction). Therefore, at every point, there are 4 possible moves the tourist can make. For instance, when standing at the origin (0,0), the tourist can move either to (0, 1), (0, −1), (1, 0) or (−1, 0), and has an equal probability of moving in each direction, thus a probability of 0.25 for each option. What is the probability that this tourist locates the tourist office in 1000 steps
or less?
Aaron Montgomery gave the hint that the simulation is a good way to estimate the probability. Could any expert give a full code, like the C++ or R code, to help us better understand this kind of question? Thanks in advance.
probability random-walk
asked Aug 2 at 17:59
Amy_777
204
edited Aug 2 at 21:29
asked Aug 2 at 17:59
Amy_777
204
asked Aug 2 at 17:59
Amy_777
204
asked Aug 2 at 17:59
Amy_777
204
204
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $vecD=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $vecr_1, cdots, vecr_n$ with each $vecr=xe_1+ye_2$ being such that either $x=pm 1$ and $y=0$ or $x=0$ and $y=pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $vecD$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_pm$ be the number of horizontal steps in $pm$ directionrespectively. Similarly define $N_pm^y$. Clearly,
$$
N_+^x-N_-^x=X, qquad N_+^y-N_-^y=Y, qquad N_+^x+N_-^x+N_+^y+N_-^y=n
$$
We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations
$$
beginpmatrix
N_+^x\
N_-^x\
N_+^y\
N_-^y
endpmatrix=frac12beginpmatrix
m+X\
m-X\
n-m+Y\
n-m-Y
endpmatrix
$$
Which obiously requires $mgeq |X|$, $n-mgeq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $vecD$ are
$$
nu_m=binomnmbinommN_+^xbinomn-mN_+^y=
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
and the total number of $n$-paths ending at $vecD$ are
$$
boxed
N_n(X,Y)=sum_mtext is (n,X,Y)text-admissible
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $mgeq 10$ and $1000-mgeq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10leq mleq 970$.
answered Aug 2 at 19:16
Hamed
4,333421
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
 |Â
show 3 more comments
up vote
1
down vote
I'm not sure how you're getting the claim that $P((a + c) leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.
My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:
Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] times [-1000, 1000]$ (so, $approx 4 cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.
And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.
EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:
set totalvisits = 0
set trials = 10000 % may be useful to experiment with a bigger number
for i = 1 to trials
set x = 0, y = 0, visit = 0
for n = 1 to 1000
generate random integer z in 1, 2, 3, 4
if z = 1, add 1 to x
if z = 2, subtract 1 from x
if z = 3, add 1 to y
if z = 4, subtract 1 from y
if x = -10 and y = 30, set visit = 1
totalvisits = totalvisits + visit
% The probability of visiting the info center is totalvisits / trials
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
add a comment |Â
up vote
1
down vote
In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,dots,1000$.
To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let
$$
b_n = text# ways to walk from (0,0) to $v$ in $n$ stepsquad;\
c_n = text# ways to walk from (0,0) to (0,0) in $n$ steps
$$
You can show that
$$
b_n = sum_k=0^n a_k c_n-k,
$$
because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0le kle n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$:
$$
a_n = b_n - sum_k=0^n-1a_kc_n-k tag1
$$
This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_n$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.
Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well:
$$
b_n = begincasesbinomn(n+(-10)+30)/2binomn(n+(-10)-30)/2 & ntext is even\0 & textotherwiseendcasestag2
$$
$$
c_n = begincasesbinomnn/2^2 & ntext is even\0 & textotherwiseendcaseshspace4cmtag3
$$
In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=sum_n=40^1000 a_ncdot (1/4)^n$. You should now have enough information to write a program to compute $P$.
answered yesterday
Mike Earnest
14.7k11644
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $vecD=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $vecr_1, cdots, vecr_n$ with each $vecr=xe_1+ye_2$ being such that either $x=pm 1$ and $y=0$ or $x=0$ and $y=pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $vecD$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_pm$ be the number of horizontal steps in $pm$ directionrespectively. Similarly define $N_pm^y$. Clearly,
$$
N_+^x-N_-^x=X, qquad N_+^y-N_-^y=Y, qquad N_+^x+N_-^x+N_+^y+N_-^y=n
$$
We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations
$$
beginpmatrix
N_+^x\
N_-^x\
N_+^y\
N_-^y
endpmatrix=frac12beginpmatrix
m+X\
m-X\
n-m+Y\
n-m-Y
endpmatrix
$$
Which obiously requires $mgeq |X|$, $n-mgeq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $vecD$ are
$$
nu_m=binomnmbinommN_+^xbinomn-mN_+^y=
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
and the total number of $n$-paths ending at $vecD$ are
$$
boxed
N_n(X,Y)=sum_mtext is (n,X,Y)text-admissible
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $mgeq 10$ and $1000-mgeq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10leq mleq 970$.
answered Aug 2 at 19:16
Hamed
4,333421
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
 |Â
show 3 more comments
up vote
2
down vote
accepted
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $vecD=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $vecr_1, cdots, vecr_n$ with each $vecr=xe_1+ye_2$ being such that either $x=pm 1$ and $y=0$ or $x=0$ and $y=pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $vecD$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_pm$ be the number of horizontal steps in $pm$ directionrespectively. Similarly define $N_pm^y$. Clearly,
$$
N_+^x-N_-^x=X, qquad N_+^y-N_-^y=Y, qquad N_+^x+N_-^x+N_+^y+N_-^y=n
$$
We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations
$$
beginpmatrix
N_+^x\
N_-^x\
N_+^y\
N_-^y
endpmatrix=frac12beginpmatrix
m+X\
m-X\
n-m+Y\
n-m-Y
endpmatrix
$$
Which obiously requires $mgeq |X|$, $n-mgeq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $vecD$ are
$$
nu_m=binomnmbinommN_+^xbinomn-mN_+^y=
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
and the total number of $n$-paths ending at $vecD$ are
$$
boxed
N_n(X,Y)=sum_mtext is (n,X,Y)text-admissible
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $mgeq 10$ and $1000-mgeq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10leq mleq 970$.
answered Aug 2 at 19:16
Hamed
4,333421
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
 |Â
show 3 more comments
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $vecD=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $vecr_1, cdots, vecr_n$ with each $vecr=xe_1+ye_2$ being such that either $x=pm 1$ and $y=0$ or $x=0$ and $y=pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $vecD$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_pm$ be the number of horizontal steps in $pm$ directionrespectively. Similarly define $N_pm^y$. Clearly,
$$
N_+^x-N_-^x=X, qquad N_+^y-N_-^y=Y, qquad N_+^x+N_-^x+N_+^y+N_-^y=n
$$
We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations
$$
beginpmatrix
N_+^x\
N_-^x\
N_+^y\
N_-^y
endpmatrix=frac12beginpmatrix
m+X\
m-X\
n-m+Y\
n-m-Y
endpmatrix
$$
Which obiously requires $mgeq |X|$, $n-mgeq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $vecD$ are
$$
nu_m=binomnmbinommN_+^xbinomn-mN_+^y=
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
and the total number of $n$-paths ending at $vecD$ are
$$
boxed
N_n(X,Y)=sum_mtext is (n,X,Y)text-admissible
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $mgeq 10$ and $1000-mgeq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10leq mleq 970$.
answered Aug 2 at 19:16
Hamed
4,333421
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $vecD=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $vecr_1, cdots, vecr_n$ with each $vecr=xe_1+ye_2$ being such that either $x=pm 1$ and $y=0$ or $x=0$ and $y=pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $vecD$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_pm$ be the number of horizontal steps in $pm$ directionrespectively. Similarly define $N_pm^y$. Clearly,
$$
N_+^x-N_-^x=X, qquad N_+^y-N_-^y=Y, qquad N_+^x+N_-^x+N_+^y+N_-^y=n
$$
We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations
$$
beginpmatrix
N_+^x\
N_-^x\
N_+^y\
N_-^y
endpmatrix=frac12beginpmatrix
m+X\
m-X\
n-m+Y\
n-m-Y
endpmatrix
$$
Which obiously requires $mgeq |X|$, $n-mgeq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $vecD$ are
$$
nu_m=binomnmbinommN_+^xbinomn-mN_+^y=
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
and the total number of $n$-paths ending at $vecD$ are
$$
boxed
N_n(X,Y)=sum_mtext is (n,X,Y)text-admissible
binomnmbinommfracm+X2binomn-mfracn-m+Y2
$$
Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $mgeq 10$ and $1000-mgeq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10leq mleq 970$.
answered Aug 2 at 19:16
Hamed
4,333421
edited Aug 2 at 19:29
answered Aug 2 at 19:16
Hamed
4,333421
answered Aug 2 at 19:16
Hamed
4,333421
answered Aug 2 at 19:16
Hamed
4,333421
4,333421
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
 |Â
show 3 more comments
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Fun fact: $N_n(X,Y)$ can be written without a summation as $binomnfracn+X+Y2binomnfracn+X-Y2$.
– Mike Earnest
Aug 2 at 19:23
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Oh really?! Is it easy to see?
– Hamed
Aug 2 at 19:30
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Sort of! Use the change of coordinates $s = x+y$ and $t=x-y$. In this new coordinate system, the values of $s$ and $t$ are independent random walks.
– Mike Earnest
Aug 2 at 19:37
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
Of course they are! OK, now I feel dumb... :)
– Hamed
Aug 2 at 19:38
1
1
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
You shouldn't feel dumb! I only learned about that trick because I saw it in this paper: arxiv.org/pdf/math/9712215.pdf. It is a quite clever trick
– Mike Earnest
Aug 2 at 19:40
 |Â
show 3 more comments
up vote
1
down vote
I'm not sure how you're getting the claim that $P((a + c) leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.
My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:
Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] times [-1000, 1000]$ (so, $approx 4 cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.
And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.
EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:
set totalvisits = 0
set trials = 10000 % may be useful to experiment with a bigger number
for i = 1 to trials
set x = 0, y = 0, visit = 0
for n = 1 to 1000
generate random integer z in 1, 2, 3, 4
if z = 1, add 1 to x
if z = 2, subtract 1 from x
if z = 3, add 1 to y
if z = 4, subtract 1 from y
if x = -10 and y = 30, set visit = 1
totalvisits = totalvisits + visit
% The probability of visiting the info center is totalvisits / trials
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
add a comment |Â
up vote
1
down vote
I'm not sure how you're getting the claim that $P((a + c) leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.
My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:
Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] times [-1000, 1000]$ (so, $approx 4 cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.
And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.
EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:
set totalvisits = 0
set trials = 10000 % may be useful to experiment with a bigger number
for i = 1 to trials
set x = 0, y = 0, visit = 0
for n = 1 to 1000
generate random integer z in 1, 2, 3, 4
if z = 1, add 1 to x
if z = 2, subtract 1 from x
if z = 3, add 1 to y
if z = 4, subtract 1 from y
if x = -10 and y = 30, set visit = 1
totalvisits = totalvisits + visit
% The probability of visiting the info center is totalvisits / trials
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I'm not sure how you're getting the claim that $P((a + c) leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.
My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:
Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] times [-1000, 1000]$ (so, $approx 4 cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.
And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.
EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:
set totalvisits = 0
set trials = 10000 % may be useful to experiment with a bigger number
for i = 1 to trials
set x = 0, y = 0, visit = 0
for n = 1 to 1000
generate random integer z in 1, 2, 3, 4
if z = 1, add 1 to x
if z = 2, subtract 1 from x
if z = 3, add 1 to y
if z = 4, subtract 1 from y
if x = -10 and y = 30, set visit = 1
totalvisits = totalvisits + visit
% The probability of visiting the info center is totalvisits / trials
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
I'm not sure how you're getting the claim that $P((a + c) leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.
My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:
Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] times [-1000, 1000]$ (so, $approx 4 cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.
And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.
EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:
set totalvisits = 0
set trials = 10000 % may be useful to experiment with a bigger number
for i = 1 to trials
set x = 0, y = 0, visit = 0
for n = 1 to 1000
generate random integer z in 1, 2, 3, 4
if z = 1, add 1 to x
if z = 2, subtract 1 from x
if z = 3, add 1 to y
if z = 4, subtract 1 from y
if x = -10 and y = 30, set visit = 1
totalvisits = totalvisits + visit
% The probability of visiting the info center is totalvisits / trials
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
edited Aug 4 at 1:56
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
answered Aug 2 at 18:44
Aaron Montgomery
4,217423
4,217423
add a comment |Â
add a comment |Â
up vote
1
down vote
In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,dots,1000$.
To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let
$$
b_n = text# ways to walk from (0,0) to $v$ in $n$ stepsquad;\
c_n = text# ways to walk from (0,0) to (0,0) in $n$ steps
$$
You can show that
$$
b_n = sum_k=0^n a_k c_n-k,
$$
because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0le kle n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$:
$$
a_n = b_n - sum_k=0^n-1a_kc_n-k tag1
$$
This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_n$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.
Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well:
$$
b_n = begincasesbinomn(n+(-10)+30)/2binomn(n+(-10)-30)/2 & ntext is even\0 & textotherwiseendcasestag2
$$
$$
c_n = begincasesbinomnn/2^2 & ntext is even\0 & textotherwiseendcaseshspace4cmtag3
$$
In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=sum_n=40^1000 a_ncdot (1/4)^n$. You should now have enough information to write a program to compute $P$.
answered yesterday
Mike Earnest
14.7k11644
add a comment |Â
up vote
1
down vote
In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,dots,1000$.
To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let
$$
b_n = text# ways to walk from (0,0) to $v$ in $n$ stepsquad;\
c_n = text# ways to walk from (0,0) to (0,0) in $n$ steps
$$
You can show that
$$
b_n = sum_k=0^n a_k c_n-k,
$$
because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0le kle n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$:
$$
a_n = b_n - sum_k=0^n-1a_kc_n-k tag1
$$
This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_n$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.
Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well:
$$
b_n = begincasesbinomn(n+(-10)+30)/2binomn(n+(-10)-30)/2 & ntext is even\0 & textotherwiseendcasestag2
$$
$$
c_n = begincasesbinomnn/2^2 & ntext is even\0 & textotherwiseendcaseshspace4cmtag3
$$
In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=sum_n=40^1000 a_ncdot (1/4)^n$. You should now have enough information to write a program to compute $P$.
answered yesterday
Mike Earnest
14.7k11644
add a comment |Â
up vote
1
down vote
up vote
1
down vote
In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,dots,1000$.
To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let
$$
b_n = text# ways to walk from (0,0) to $v$ in $n$ stepsquad;\
c_n = text# ways to walk from (0,0) to (0,0) in $n$ steps
$$
You can show that
$$
b_n = sum_k=0^n a_k c_n-k,
$$
because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0le kle n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$:
$$
a_n = b_n - sum_k=0^n-1a_kc_n-k tag1
$$
This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_n$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.
Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well:
$$
b_n = begincasesbinomn(n+(-10)+30)/2binomn(n+(-10)-30)/2 & ntext is even\0 & textotherwiseendcasestag2
$$
$$
c_n = begincasesbinomnn/2^2 & ntext is even\0 & textotherwiseendcaseshspace4cmtag3
$$
In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=sum_n=40^1000 a_ncdot (1/4)^n$. You should now have enough information to write a program to compute $P$.
answered yesterday
Mike Earnest
14.7k11644
In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,dots,1000$.
To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let
$$
b_n = text# ways to walk from (0,0) to $v$ in $n$ stepsquad;\
c_n = text# ways to walk from (0,0) to (0,0) in $n$ steps
$$
You can show that
$$
b_n = sum_k=0^n a_k c_n-k,
$$
because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0le kle n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$:
$$
a_n = b_n - sum_k=0^n-1a_kc_n-k tag1
$$
This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_n$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.
Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well:
$$
b_n = begincasesbinomn(n+(-10)+30)/2binomn(n+(-10)-30)/2 & ntext is even\0 & textotherwiseendcasestag2
$$
$$
c_n = begincasesbinomnn/2^2 & ntext is even\0 & textotherwiseendcaseshspace4cmtag3
$$
In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=sum_n=40^1000 a_ncdot (1/4)^n$. You should now have enough information to write a program to compute $P$.
answered yesterday
Mike Earnest
14.7k11644
edited 6 hours ago
answered yesterday
Mike Earnest
14.7k11644
answered yesterday
Mike Earnest
14.7k11644
answered yesterday
Mike Earnest
14.7k11644
14.7k11644
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870330%2frandom-walk-probability%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password