Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2017-02-16 01:31:42

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Knight's Random Walk

A knight on an unbounded chess board picks one of the possible 8 moves uniformly at random. What is the expected time after which the knight comes back to where it started?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#2 2017-02-16 01:57:14

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2017-02-16 02:57:49

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

I can find this value for a finite n. But I do not think taking limit on n makes sense.

What is the mean time of return to the origin when you do a random walk on the integers?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#4 2017-02-16 07:50:12

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

Hi;

I do not understand the question. The answers given above are over the integers.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2017-02-16 15:20:23

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

I meant, what is the expected time after which you return to the origin in the following random walk?

Start at 0. When in i, with probability 0.5, go to i+1, and with probability 0.5 go to i-1


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#6 2017-02-16 15:54:04

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

Just a 1 dimensional walk like a straight line?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2017-02-16 16:22:36

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

Yes, let's solve a simpler problem first


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#8 2017-02-16 16:50:47

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

I am working on it but as I am also breaking in a brand new machine it will take longer than usual.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2017-02-16 17:07:20

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

Oh, I hope that is fun!


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#10 2017-02-16 17:25:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

It is not, I had to defeat much protection by Micro$oft just to get Manjaro installed. It is still not done yet and I am testing now.

What does your simulation say about this problem?

Everyone time I compute it I am getting infinity. The walk will always return to 0 but the expected number of moves so far is infinity.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2017-02-16 18:55:10

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

I do not know how one does infinite similations.

In that case, I think the knight case is similar..


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#12 2017-02-16 20:07:20

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

I do not know for sure, I now the knight has answers on an 8 x 8 board. Unbounded, is another matter.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2017-02-19 21:32:53

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Knight's Random Walk

I know how to solve it for an 8 by 8 board.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#14 2017-02-20 02:35:49

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Knight's Random Walk

Do you agree with the answers I gave in post #2?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB