wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> 2nd order random walks
        
(Message started by: JocK on Jul 9th, 2005, 3:39am)
Title: 2nd order random walks
Post by JocK on Jul 9th, 2005, 3:39am
A standard (1st order) random walk is characterised by random positional changes:

xn+1 = xn +- 1

with both signs occurring randomly with equal probability.

Starting with x0 = 0, the asymptotic behaviour of such a 1st order random walk is characterised  by the fact that, averaged over many random walks, the squares of the displacements  (xn)2  grow proportional to n, the number of steps.


Here we consider 2nd order random walks for which the velocities (rather than the positions)undergo random changes:

xn+1 - xn = xn - xn-1 +- 1

Can you characterise the asymptotic behaviour of the squares of the displacements for this 2nd order random walk?
(You may assume as starting condition the random walker to be at rest at the origin: x-1 = x0 = 0.)




-- Bonus questions --

What if you make the size of the random velocity changes dependent on the position? For instance:

xn+1 - xn = xn - xn-1 +- xn

or even:

xn+1 - xn = xn - xn-1 +- (xn)2


Furthermore, we have restricted ourselves to 1D random walks. Extending the 1st order random walk to higher dimensions, leaves the proportionality of the squares of the displacements with the number of steps unchanged. But what about the various 2nd order random walks listed above? Is the asymptotic behaviour different in different dimensions?
Title: Re: 2nd order random walks
Post by THUDandBLUNDER on Jul 9th, 2005, 4:56pm

Quote:
Can you characterise the asymptotic behaviour of the squares of the displacements for this 2nd order random walk?  
(You may assume as starting condition the random walker to be at rest at the origin: x-1 = x0 = 0.)

:[hide]How about 4n3/9[/hide]?
Title: Re: 2nd order random walks
Post by Barukh on Jul 9th, 2005, 11:12pm

on 07/09/05 at 16:56:35, THUDandBLUNDER wrote:
:[hide]How about 4n3/9[/hide]?

I get almost the same: [hide]n3/3[/hide].
Title: Re: 2nd order random walks
Post by Barukh on Jul 12th, 2005, 6:22am
So, two close answers were given. What will the judges say?  ;)
Title: Re: 2nd order random walks
Post by THUDandBLUNDER on Jul 12th, 2005, 7:21am
For vn - vn-1 = +/- xn I think that E(|xn|) => oo as n => oo
Title: Re: 2nd order random walks
Post by Barukh on Jul 12th, 2005, 9:04am

on 07/12/05 at 07:21:18, THUDandBLUNDER wrote:
For vn - vn-1 = +/- xn I think that E(|xn|) => oo as n => oo

Given the starting conditions in the original problem, I think E(xn2) = 0 for every n.  ;D


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board