All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Back to throne (Posted on 2015-05-21)
Imagine a chess King placed in the central square C(5,5) of a 9x9 “checkerboard”. King’s step consists of his displacement to the neighboring square in one of the 8 directions.

What is the probability that his 4-step random walk terminates at square C?

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration and solution | Comment 2 of 3 |
Probability distributions about the central square after moves 1, 2, 3 and 4:

` 0.125000000 0.125000000 0.125000000 0.125000000 0.000000000 0.125000000 0.125000000 0.125000000 0.125000000`
` 0.015625000 0.031250000 0.046875000 0.031250000 0.015625000 0.031250000 0.031250000 0.062500000 0.031250000 0.031250000 0.046875000 0.062500000 0.125000000 0.062500000 0.046875000 0.031250000 0.031250000 0.062500000 0.031250000 0.031250000 0.015625000 0.031250000 0.046875000 0.031250000 0.015625000`
` 0.001953125 0.005859375 0.011718750 0.013671875 0.011718750 0.005859375 0.001953125 0.005859375 0.011718750 0.023437500 0.023437500 0.023437500 0.011718750 0.005859375 0.011718750 0.023437500 0.052734375 0.052734375 0.052734375 0.023437500 0.011718750 0.013671875 0.023437500 0.052734375 0.046875000 0.052734375 0.023437500 0.013671875 0.011718750 0.023437500 0.052734375 0.052734375 0.052734375 0.023437500 0.011718750 0.005859375 0.011718750 0.023437500 0.023437500 0.023437500 0.011718750 0.005859375 0.001953125 0.005859375 0.011718750 0.013671875 0.011718750 0.005859375 0.001953125`
` 0.000244141 0.000976563 0.002441406 0.003906250 0.004638672 0.003906250 0.002441406 0.000976563 0.000244141 0.000976563 0.002929688 0.006835938 0.009765625 0.011718750 0.009765625 0.006835938 0.002929688 0.000976563 0.002441406 0.006835938 0.017089844 0.024414063 0.030273438 0.024414063 0.017089844 0.006835938 0.002441406 0.003906250 0.009765625 0.024414063 0.032226563 0.041015625 0.032226563 0.024414063 0.009765625 0.003906250 0.004638672 0.011718750 0.030273438 0.041015625 0.052734375 0.041015625 0.030273438 0.011718750 0.004638672 0.003906250 0.009765625 0.024414063 0.032226563 0.041015625 0.032226563 0.024414063 0.009765625 0.003906250 0.002441406 0.006835938 0.017089844 0.024414063 0.030273438 0.024414063 0.017089844 0.006835938 0.002441406 0.000976563 0.002929688 0.006835938 0.009765625 0.011718750 0.009765625 0.006835938 0.002929688 0.000976563 0.000244141 0.000976563 0.002441406 0.003906250 0.004638672 0.003906250 0.002441406 0.000976563 0.000244141`

The 0.052734375 at C after the 4th move, expressed as a common fraction, before reduction to lowest terms, must have a denominator of 8^4 = 32768. Multiplying by this we get 1728 for the numerator so the desired probability is:

0.052734375 = 1728/32768  =  27/512

from:

DefDbl A-Z
Dim crlf\$, grid(9, 9, 4)

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Text1.Text = ""
crlf\$ = Chr(13) + Chr(10)
Form1.Visible = True

grid(5, 5, 0) = 1
For stp = 1 To 4
For row = 1 To 9
For col = 1 To 9
If grid(row, col, stp - 1) > 0 Then
For r = row - 1 To row + 1
For c = col - 1 To col + 1
If r <> row Or c <> col Then
grid(r, c, stp) = grid(r, c, stp) + grid(row, col, stp - 1) / 8
End If
Next
Next
End If
Next
Next
For r = 5 - stp To 5 + stp
For c = 5 - stp To 5 + stp
Text1.Text = Text1.Text & mform(grid(r, c, stp), " 0.000000000")
Next c
Text1.Text = Text1.Text & crlf
Next r
Text1.Text = Text1.Text & crlf
Next stp

g = gcd(Int(grid(5, 5, stp - 1) * 2 ^ 15 + 0.5), Int(2 ^ 15 + 0.5))

Text1.Text = Text1.Text & grid(5, 5, stp - 1) * 2 ^ 15 & "/" & 2 ^ 15 & "  =  "
Text1.Text = Text1.Text & grid(5, 5, stp - 1) * 2 ^ 15 / g & "/" & 2 ^ 15 / g & crlf

Text1.Text = Text1.Text & " done" & crlf

End Sub

Function gcd(a, b)
x = a: y = b
Do
q = Int(x / y)
z = x - q * y
x = y: y = z
Loop Until z = 0
gcd = x
End Function

Edited on May 21, 2015, 10:35 am
 Posted by Charlie on 2015-05-21 10:34:51

 Search: Search body:
Forums (0)