GH18 -- Sage

# This worksheet contains computations of expected propagation time using Markov transition matrices for # Expected propagation time for probabilistic zero forcing # by Jesse Geneson and Leslie Hogben

################################ # Markov method using center with 3 leaves # Four states: 0, 1, 2, 3 leaves blue # With 0 blue Pr[force]= 1/3 # With 1 blue Pr[force]= 2/3 ################################

M=matrix([[(2/3)^3, 3*(2/3)^2*(1/3), 3*(2/3)*(1/3)^2, (1/3)^3],[0, 1/9, 4/9, 4/9],[0, 0, 0, 1],[0, 0, 0, 1]]) show(M)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} \frac{8}{27} & \frac{4}{9} & \frac{2}{9} & \frac{1}{27} \\ 0 & \frac{1}{9} & \frac{4}{9} & \frac{4}{9} \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{array}\right)$

maxt = 100 ept = 0 Mt=n(identity_matrix(4)) for t in [1..maxt]: Mtminus1=Mt Mt = Mt*M ept = t*(Mt[0,3] - Mtminus1[0,3]) + ept #sage numbers matrix entries 0,1,...,n-1 ept

2.76315789473684

2.76315789473684

################################ # Markov method using center with 4 leaves # Five states: 0, 1, 2, 3, 4 leaves blue # With 0 blue Pr[force]= 1/4 # With 1 blue Pr[force]= 1/2 # With 2 blue Pr[force]= 3/4 ################################

M=matrix([[(3/4)^4, 4*(3/4)^3*(1/4), 6*(3/4)^2*(1/4)^2, 4*(3/4)*(1/4)^3, (1/4)^4], [0, (1/2)^3, 3*(1/2)^3, 3*(1/2)^3, (1/2)^3], [0, 0, (1/4)^2, 2*(1/4)*(3/4), (3/4)^2], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1]]) show(M)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} \frac{81}{256} & \frac{27}{64} & \frac{27}{128} & \frac{3}{64} & \frac{1}{256} \\ 0 & \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \\ 0 & 0 & \frac{1}{16} & \frac{3}{8} & \frac{9}{16} \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right)$

maxt = 100 ept = 0 Mt=n(identity_matrix(5)) for t in [1..maxt]: Mtminus1=Mt Mt = Mt*M ept = t*(Mt[0,4] - Mtminus1[0,4]) + ept #sage numbers matrix entries 0,1,...,n-1 ept

3.34171428571428

3.34171428571428

GH18

1961 days ago by hogben