What is the relationship between random walks and destinations?

[member 428835]

Homework Statement

a) Beginning at the origin and taking one unit steps in either the ##x## or ##y## direction at random, what is the expected number of steps until you reach the square boundary with sides length 2?

b) How about until you reach the line ##y=1-x## from the origin?

Relevant Equations

Nothing comes to mind.

a) Let ##N_i## be the expected number of jumps to get to one of the square sides from minimal step number ##i## from the origin (so (1,1) would be ##i=2## since it takes 2 steps minimally to get there). Then we have:
##N_0 = 1+N_1##
##N_1 = 1 + 0.25N_0 + 0.5N_2 + 0.25##
##N_2 = 1 + 0.5N_1 + 0.5##
where ##i## denotes ##i## steps from the origin. This implies ##N_0 = 5.5##.

b) This one seems tougher. However, after I drew a picture, it seems every down or left movement is a step away from the line and every up or right movement is a step toward the line, so kind of 1D? Also, the line ##y=1-x \implies y+x=1##. Thus, if we say ##z=y+x## then we are looking for ##z=1##. So we can think of this problem as a 1D number line, we start at point 0 and randomly walk left or right 1 distance and then repeat. Let ##X## be the number of steps to get from 0 to 1. Then we have ##X = 0.5 + 0.5(1 + 2X) \implies X = X + 1##, which is only true when ##X \to \infty##. Am I missing something here?

 

[PeroK]

Homework Statement:: a) Beginning at the origin and taking one unit steps in either the ##x## or ##y## direction at random, what is the expected number of steps until you reach the square boundary with sides length 2?

b) How about until you reach the line ##y=1-x## from the origin?
Relevant Equations:: Nothing comes to mind.

a) Let ##N_i## be the expected number of jumps to get to one of the square sides from minimal step number ##i## from the origin (so (1,1) would be ##i=2## since it takes 2 steps minimally to get there). Then we have:
##N_0 = 1+N_1##
##N_1 = 1 + 0.25N_0 + 0.5N_2 + 0.25##
##N_2 = 1 + 0.5N_1 + 0.5##
where ##i## denotes ##i## steps from the origin. This implies ##N_0 = 5.5##.

That isn't correct. In the equation ##N_2 = 1 + 0.5N_1 + 0.5##, what deos the ##1## represent?

b) This one seems tougher. However, after I drew a picture, it seems every down or left movement is a step away from the line and every up or right movement is a step toward the line, so kind of 1D? Also, the line ##y=1-x \implies y+x=1##. Thus, if we say ##z=y+x## then we are looking for ##z=1##. So we can think of this problem as a 1D number line, we start at point 0 and randomly walk left or right 1 distance and then repeat. Let ##X## be the number of steps to get from 0 to 1. Then we have ##X = 0.5 + 0.5(1 + 2X) \implies X = X + 1##, which is only true when ##X \to \infty##. Am I missing something here?

You have an infinite sequence of states in this case.

 

[member 428835]

That isn't correct. In the equation ##N_2 = 1 + 0.5N_1 + 0.5##, what deos the ##1## represent?

You have an infinite sequence of states in this case.

Shoot, good call. So the system would actually be:
##N_0 = 1+N_1##
##N_1 =0.25(1+N_0) + 0.5(1+N_2) + 0.25##
##N_2 = 0.5(N_1 +1)+ 0.5##
which implies ##N_0=4.5##.

And so the second one really is infinite?

 

[PeroK]

Shoot, good call. So the system would actually be:
##N_0 = 1+N_1##
##N_1 =0.25(1+N_0) + 0.5(1+N_2) + 0.25##
##N_2 = 0.5(N_1 +1)+ 0.5##
which implies ##N_0=4.5##.

That looks better.

And so the second one really is infinite?

No, it just means you have an infinite recurrence relation to solve!

 

[member 428835]

That looks better.No, it just means you have an infinite recurrence relation to solve!

So what's the answer then? EDIT: not trying to come off cold here, I'm genuinely not sure how to answer this. Feel I've done the correct legwork, but am unsure how to finalize it.

Also, you're a python guy right? How does this script look for estimating the average number of steps to exit the oval ##( (x - 2.5) / 30 )^2 + ( (y - 2.5) / 40 )^2 < 1## taking 10 step intervals (I'm getting 14):

import random

class mathCirc:
    def length(self, n):
        res = 0
        for i in range(n):
            walk = 0
            x = y = 0

            while ( (x - 2.5) / 30 )**2 + ( (y - 2.5) / 40 )**2 < 1:
                P = random.random()
                walk += 1

                # UP
                if P < 0.25:
                    y += 10

                # DOWN
                elif 0.25 < P < 0.5:
                    y -= 10

                # RIGHT
                elif 0.5 < P < 0.75:
                    x += 10

                # LEFT
                elif P > 0.75:
                    x -= 10

            res += walk

        return res/nif __name__ == "__main__":
    n = 100000
    ob1 = mathCirc()
    print(ob1.length(n))

 

[PeroK]

I'm genuinely not sure how to answer this. Feel I've done the correct legwork, but am unsure how to finalize it.

It's the same technique but with an infinite recurrence relation. You need to write down the relationship between ##N_k## and ##N_{k-1}## and ##N_{k+1}##.

 

[member 428835]

It's the same technique but with an infinite recurrence relation. You need to write down the relationship between ##N_k## and ##N_{k-1}## and ##N_{k+1}##.

##N_k = 0.5N_{k-1}+0.5N_{k+1}##, right?

 

[PeroK]

##N_k = 0.5N_{k-1}+0.5N_{k+1}##, right?

Don't forget the ##+1##.

 

[member 428835]

Don't forget the ##+1##.

Shoot, it's late here. I'm making mistakes right and left. So how do we actually voice this to someone? Like, in english if they ask how long we expect it to take to arrive at the point ##z=1##?

 

[PeroK]

Then we have ##X = 0.5 + 0.5(1 + 2X) \implies X = X + 1##, which is only true when ##X \to \infty##. Am I missing something here?

Actually, I've just understood what you did here. That looks like a neat shortcut to show that ##X## cannot be finite.

 

[member 428835]

Actually, I've just understood what you did here. That looks like a neat shortcut to show that ##X## cannot be finite.

Thanks, all the studying lately might finally be paying off. You've been a massive help! But how do we word this? Do we say we expect infinite steps, or simply that no solution exists?

Can you comment on my python script? It looks right to me, but I don't know for sure.

I should clarify this is all self study, so not actually HW.

 

[PeroK]

Thanks, all the studying lately might finally be paying off. You've been a massive help! But how do we word this? Do we say we expect infinite steps, or simply that no solution exists?

You just say that the expected number of steps is infinite. Or, more formally, that the distribution of the number of steps has no mean.

Can you comment on my python script? It looks right to me, but I don't know for sure.

I don't have time at the moment. Sorry.

 

[haruspex]

"square boundary with sides length 2".
I presume you mean side length 4, the square with corners ##(\pm 2, \pm 2)##.

comment on my python script?

Not sure why you are randomising instead of applying the same iterative process you used for the first part. At a rough calculation, there are less than 50 landing points inside the ellipse.

 

[member 428835]

"square boundary with sides length 2".
I presume you mean side length 4, the square with corners ##(\pm 2, \pm 2)##.

Not sure why you are randomising instead of applying the same iterative process you used for the first part. At a rough calculation, there are less than 50 landing points inside the ellipse.

Thanks, I did mean length 4.

I'm randomizing because we can walk up, down, left, or right with equal probability. Notice this technique would work with higher dimensional walks too, like in a sphere, so it's pretty general.

 

[haruspex]

I'm randomizing because we can walk up, down, left, or right with equal probability.

Sure, but you did not involve actual random trials in your solution to part a). You could use the same approach for the ellipse.

 

[member 428835]

Sure, but you did not involve actual random trials in your solution to part a). You could use the same approach for the ellipse.

Okay, yes I see what you mean. Though the ellipse is not centered at the origin, so it would be pretty tedious. Much easier to program the solution, right?

 

[haruspex]

Okay, yes I see what you mean. Though the ellipse is not centered at the origin, so it would be pretty tedious. Much easier to program the solution, right?

Oh, yes, I would still do it in software, just not using randomness.

 

[member 428835]

Oh, yes, I would still do it in software, just not using randomness.

Can you share your code? I feel this monte-carlo approach is just so easy.

 

[haruspex]

Can you share your code? I feel this monte-carlo approach is just so easy.

I have not written it, but it does not seem that hard.
Might try later.

 

[PeroK]

So what's the answer then? EDIT: not trying to come off cold here, I'm genuinely not sure how to answer this. Feel I've done the correct legwork, but am unsure how to finalize it.

Also, you're a python guy right? How does this script look for estimating the average number of steps to exit the oval ##( (x - 2.5) / 30 )^2 + ( (y - 2.5) / 40 )^2 < 1## taking 10 step intervals (I'm getting 14):

import random

class mathCirc:
    def length(self, n):
        res = 0
        for i in range(n):
            walk = 0
            x = y = 0

            while ( (x - 2.5) / 30 )**2 + ( (y - 2.5) / 40 )**2 < 1:
                P = random.random()
                walk += 1

                # UP
                if P < 0.25:
                    y += 10

                # DOWN
                elif 0.25 < P < 0.5:
                    y -= 10

                # RIGHT
                elif 0.5 < P < 0.75:
                    x += 10

                # LEFT
                elif P > 0.75:
                    x -= 10

            res += walk

        return res/nif __name__ == "__main__":
    n = 100000
    ob1 = mathCirc()
    print(ob1.length(n))

You're script looks okay. There's an art to debugging/checking code. In this case, you could print each step, then run it a few times with ##n = 1## to check the walk and the exit criteria are as you expect. Then comment out the unnecessary print commands once you are satisfied.

 

[Prof B]

Homework Statement:: a) Beginning at the origin and taking one unit steps in either the ##x## or ##y## direction at random, what is the expected number of steps until you reach the square boundary with sides length 2?

It always takes exactly 1 step to reach the boundary.

b) How about until you reach the line ##y=1-x## from the origin?

Your reduction to the 1-dimensional case looks correct. Was the 1-dimensional case covered in class?

 

[member 428835]

It always takes exactly 1 step to reach the boundary.

Your reduction to the 1-dimensional case looks correct. Was the 1-dimensional case covered in class?

There is no class. These are random problems I find on the internet. I have an interview book I read from: when I'm stumped, I google, which typically takes me to Stack. Usually beneath solutions are other similar questions. You can see how this adds up, curiously trying every one I read.

 

[haruspex]

It always takes exactly 1 step to reach the boundary.

See post #14.

 

[haruspex]

Can you share your code? I feel this monte-carlo approach is just so easy.

One problem with Monte Carlo is figuring out how accurate your answer is.
The nonrandom way is to write the matrix equation relating the expectations, then either solve it or iterate until it converges.

Iterating in a spreadsheet converged to this
0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 4.04 4.10 0.00 0.00 0.00
0.00 5.20 8.08 8.37 6.40 4.05 0.00
5.91 8.74 10.71 10.90 9.19 5.81 0.00
6.01 9.13 11.12 11.34 9.65 5.99 0.00
0.00 6.65 9.33 9.70 8.10 4.52 0.00
0.00 4.13 5.87 6.02 4.53 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00

 

[Prof B]

There is no class. These are random problems I find on the internet. I have an interview book I read from: when I'm stumped, I google, which typically takes me to Stack. Usually beneath solutions are other similar questions. You can see how this adds up, curiously trying every one I read.

1-dimensional random walks are pretty cool. It's good that you were able to figure out what you needed, but you might want to know more. PDF from MIT discrete math ocw.

 

[haruspex]

Josh wants the expected time to reach a point (x,y) where max(|x|,|y|)=2. It's not 5.5. You calculated the expected time to reach a point such that |x|+|y|=2. Since those points include (1,1), for example, it's not the same thing.

Which post are you referring to and who is "you" here?
In post #3, Josh got the answer 4.5, which looks right to me.

 

[haruspex]

One problem with Monte Carlo is figuring out how accurate your answer is.
The nonrandom way is to write the matrix equation relating the expectations, then either solve it or iterate until it converges.

Iterating in a spreadsheet converged to this
0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 4.04 4.10 0.00 0.00 0.00
0.00 5.20 8.08 8.37 6.40 4.05 0.00
5.91 8.74 10.71 10.90 9.19 5.81 0.00
6.01 9.13 11.12 11.34 9.65 5.99 0.00
0.00 6.65 9.33 9.70 8.10 4.52 0.00
0.00 4.13 5.87 6.02 4.53 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00

Out of interest, I considered the continuous version with a circular boundary and the peak in the middle. This is equivalent to solving a circularly symmetric 2D ##\Delta\phi+c^2=0## with ##\phi=0## at radius R. I got a parabolic dome, and the graph through the centre of the above table indeed looks like a skewed form of that.

 

[Prof B]

Which post are you referring to and who is "you" here?
In post #3, Josh got the answer 4.5, which looks right to me.

OK. I misunderstood.

 

[member 428835]

Out of interest, I considered the continuous version with a circular boundary and the peak in the middle. This is equivalent to solving a circularly symmetric 2D ##\Delta\phi+c^2=0## with ##\phi=0## at radius R. I got a parabolic dome, and the graph through the centre of the above table indeed looks like a skewed form of that.

Can you elaborate on the derivation of ##\Delta\phi+c^2=0##. I'm curious

 

[haruspex]

Can you elaborate on the derivation of ##\Delta\phi+c^2=0##. I'm curious

##\Delta\phi=0## says that at each point the potential is the average of the surrounding points. But in the random walk you have the +1 for the move to reach a neighbouring point, so the 'potential' is some constant more than the local average.