[VA] SRC #012a - Then and Now: Probability

[Albert Chan]

Here, we do P(R, S=R-1) by hand, to discover its patterns.
Even rows are previous row probabilities, scaling to 1 way, edge /4, inside /6.

1/2     1/2 --> P(2,1) = 1
1/8     1/8
1/8     1/4     1/8 --> P(3,2) = 1/2
1/32    1/24    1/32
1/32    7/96    7/96    1/32 --> P(4,3) = 5/24
1/128   7/576   7/576   1/128
1/128   23/1152 7/288   23/1152   1/128 --> P(5,4) = 23/288

We can also get P(5,4), directly from scaled P(4,3):

P(5,4) = 2*(1/128 + 7/576 + 7/576 + 1/128) = 4*(1/128 + 7/576) = 23/288

(10-21-2022 04:10 PM)Albert Chan Wrote:  P(R, S=R-1) = 3^(3-R) - 2^(5-2*R)

We are now ready to proof above, by induction
Assume formula is correct, we split it to two types, to get P(R+1, S=R):

P(R, S=R-1)              =   P(edges)      +              P(inside)

3^(3-R) - 2^(5-2*R) = 2^(4-2*R)     + (3^(-R+3) - 3*2^(4-2*R))

P(R+1, S=R)
= 2 * sum(scaled to 1 way of P(R, S=R-1)
= 2 * (2^(4-2*R)/4 + (3^(-R+3) - 3*2^(4-2*R))/6)
= 9*3^(-R) - 8*2^(-2*R)
= 3^(3-(R+1)) - 2^(5-2*(R+1))                  QED