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?
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
Private Sub Form_Load()
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 |
computer exploration and solution
