ept_Tn_star

1490 days ago by hogben

# This worksheet is generates data for # "Using Markov chains to determine expected propagation time for probabilistic zero forcing" # by Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, and Michael Ross # This worksheet is written by Leslie Hogben # It contains the code for computing the expected propagation time of # triangular books, stars, and any graph if given its Markov matrix (using Theorem 2.2). 
       
### The function ept computes expected propagation time given a Markov matrix M by applying Theorem 2.2 ### 
       
def ept(M): nstates=M.dimensions()[0] # matrix dimension jay=ones_matrix(nstates) eye=identity_matrix(nstates) Mi=(M-jay[0].outer_product(eye[nstates-1])-eye).inverse() # x.outer_product(y) does x*y^t for column vertos x,y ept=Mi[0,nstates-1]+1 return ept 
       
### The next two cells define Markov matrices of T_n, the triangular book on n vertices ### # MT starts with a high degree vertex # MT2 starts with a degre 2 vertex 
       
def MT(nn): t=nn-2 # number degree 2 vertices # states are (1,k) amd (2,k) where 1 means v white and 2 means v blue and k = 0,...,t is the # of blue degree 2 vertices m=zero_matrix(RR,2*t+2) # m is the matrix; use QQ for exact, RR for decimal d=nn-1 # degree of u and v # starting with u blue v white, state (1,k) is matrix index k, k=0,...,t # k=0 pfu=1/d # probability of u forcing any one specific vertex pnfu=1-pfu # probability of u not forcing any one specific verte for r in [0..t]: # r is the number of new blue degree 2 vertices m[0,r]=binomial(t,r)*pfu^r*pnfu^(t-r+1) # r degree 2 vertices forced and v not forced m[0,t+1+r]=binomial(t,r)*pfu^(r+1)*pnfu^(t-r) # r degree 2 vertices forced and v forced # 1 <= k <= n-3 implies v will become blue by being forced by a degree 2 vertex for k in [1..t-1]: pfu=(k+1)/d # probability of u forcing any one specific vertex pnfu=1-pfu # probability of u not forcing any one specific verte for r in [0..t-k]: # r is the number of new blue degree 2 vertices m[k,t+1+k+r]=binomial(t-k,r)*pfu^r*pnfu^(t-k-r) # r degree 2 vertices forced m[t,t+1+t]=1 # starting with u and v both blue, state (2,k) is matrix index t+1+k, k=0,...,t # 0 <= k <= n-3 for k in [0..t-2]: pfuv=(k+2)/d # probability of u forcing any one specific degree 2 vertex (same for v) pnfuv=1-pfuv # probability of u not forcing any one specific degree 2 vertex (same for v) pnf = (1-pfuv)^2 # probability of neither u nor v forcing any one specific degree 2 vertex pf = 1-(1-pfuv)^2 # probability any one specific degree 2 vertex being forced for r in [0..t-k]: # r is the number of new blue degree 2 vertices m[t+1+k,t+1+k+r]=binomial(t-k,r)*pf^r*pnf^(t-k-r) # r degree 2 vertices forced m[t+t,t+1+t]=1 m[t+1+t,t+1+t]=1 return m 
       
def MT2(nn): t=nn-2 # number degree 2 vertices # states are (0,1), (1,k) and (2,k) where first coordinate i means i of u and v are blue and k = 1,...,t is the # of blue degree 2 vertices m=zero_matrix(RR,2*t+1) # m is the matrix; use QQ for exact, RR for decimal d=nn-1 # degree of u and v # row zero is state (0,1), i.e., neither of u or v blue # all other states are same. # the degree 2 blue vertex can force 0, 1, or 2 of u and v m[0,0]=1/4 m[0,1]=1/2 m[0,t+1]=1/4 # forcing with u blue and v white # starting with u blue v white, state (1,k) is matrix index k, k=1,...,t # v will become blue by being forced by a degree 2 vertex for k in [1..t-1]: pfu=(k+1)/d # probability of u forcing any one specific vertex pnfu=1-pfu # probability of u not forcing any one specific verte for r in [0..t-k]: # r is the number of new blue degree 2 vertices m[k,t+k+r]=binomial(t-k,r)*pfu^r*pnfu^(t-k-r) # r degree 2 vertices forced m[t,t+t]=1 # starting with u and v both blue, state (2,k) is matrix index t+1+k, k=0,...,t for k in [0..t-2]: pfuv=(k+2)/d # probability of u forcing any one specific degree 2 vertex (same for v) pnfuv=1-pfuv # probability of u not forcing any one specific degree 2 vertex (same for v) pnf = (1-pfuv)^2 # probability of neither u nor v forcing any one specific degree 2 vertex pf = 1-(1-pfuv)^2 # probability any one specific degree 2 vertex being forced for r in [0..t-k]: # r is the number of new blue degree 2 vertices m[t+k,t+k+r]=binomial(t-k,r)*pf^r*pnf^(t-k-r) # r degree 2 vertices forced m[t+t-1,t+t]=1 m[t+t,t+t]=1 return m 
       
def Mstar(nn): m=zero_matrix(RR,nn) # m is the Markov matrix; use QQ for exact, RR for decimal d=nn-1 # degree of center c # starting with c blue, states are k=0,...,d # k is number of blue leaves and also the matrix index for k in [0..d-2]: pfu=(k+1)/d # probability of forcing any one specific vertex pnfu=1-pfu # probability of not forcing any one specific vertex for r in [0..d-k]: # r is the number of new blue leaves m[k,k+r]=binomial(d-k,r)*pfu^r*pnfu^(d-k-r) # r leaves forced m[d-1,d]=1 m[d,d]=1 return m 
       
def Mstar1(nn): m=zero_matrix(RR,nn) # m is the Markov matrix; use QQ for exact, RR for decimal d=nn-1 # degree of center c # starting with one leaf blue (state 0 is center white, rest are same as for starting with c) m[0,1]=1 # center now blue, k is number of blue leaves and also the matrix index for k in [1..d-2]: pfu=(k+1)/d # probability of forcing any one specific vertex pnfu=1-pfu # probability of not forcing any one specific vertex for r in [0..d-k]: # r is the number of new blue leaves m[k,k+r]=binomial(d-k,r)*pfu^r*pnfu^(d-k-r) # r leaves forced m[d-1,d]=1 m[d,d]=1 return m 
       
for nn in [4..20]: print nn, ept(MT(nn)), ept(MT2(nn)), ept(Mstar(nn-1)), ept(Mstar1(nn-1)) 
       
4 2.55350877192982 2.55555555555556 2.00000000000000 2.00000000000000
5 2.96897238895558 2.89411764705882 2.76315789473684 2.62500000000000
6 3.29499515315658 3.17759232070973 3.34171428571429 3.20000000000000
7 3.55010426798164 3.41267456633158 3.80903752169536 3.64677601809955
8 3.76223850802392 3.61509281458301 4.19683433843315 4.01909622762703
9 3.94819802383873 3.79059745710033 4.52623618618081 4.34043391856039
10 4.11434555997378 3.94421643077043 4.81182629358542 4.62020114502392
11 4.26279122277983 4.08062333531279 5.06338597376695 4.86652578120848
12 4.39509353715367 4.20337556719461 5.28772358826496 5.08641782866500
13 4.51332317228946 4.31507533641494 5.48983535974149 5.28501969773178
14 4.61989515247563 4.41765698090453 5.67351688482488 5.46593867143068
15 4.71714192191280 4.51255040334603 5.84170537957696 5.63183960548844
16 4.80701612222771 4.60080212079016 5.99670414649956 5.78483916682593
17 4.89098497587851 4.68319391097589 6.14034480064268 5.92668831249691
18 4.97006063090373 4.76034366749407 6.27410634106946 6.05884649042214
19 5.04489612809663 4.83277326528680 6.39920118362093 6.18252283366976
20 5.11589619826270 4.90094494031662 6.51663656925485 6.29871441207102
4 2.55350877192982 2.55555555555556 2.00000000000000 2.00000000000000
5 2.96897238895558 2.89411764705882 2.76315789473684 2.62500000000000
6 3.29499515315658 3.17759232070973 3.34171428571429 3.20000000000000
7 3.55010426798164 3.41267456633158 3.80903752169536 3.64677601809955
8 3.76223850802392 3.61509281458301 4.19683433843315 4.01909622762703
9 3.94819802383873 3.79059745710033 4.52623618618081 4.34043391856039
10 4.11434555997378 3.94421643077043 4.81182629358542 4.62020114502392
11 4.26279122277983 4.08062333531279 5.06338597376695 4.86652578120848
12 4.39509353715367 4.20337556719461 5.28772358826496 5.08641782866500
13 4.51332317228946 4.31507533641494 5.48983535974149 5.28501969773178
14 4.61989515247563 4.41765698090453 5.67351688482488 5.46593867143068
15 4.71714192191280 4.51255040334603 5.84170537957696 5.63183960548844
16 4.80701612222771 4.60080212079016 5.99670414649956 5.78483916682593
17 4.89098497587851 4.68319391097589 6.14034480064268 5.92668831249691
18 4.97006063090373 4.76034366749407 6.27410634106946 6.05884649042214
19 5.04489612809663 4.83277326528680 6.39920118362093 6.18252283366976
20 5.11589619826270 4.90094494031662 6.51663656925485 6.29871441207102