ept_Kmn

1552 days ago by geneson

# This worksheet 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 # It contains the code for computing the expected propagation time of # complete bipartite graphs. 
       
#Gives probability of (bm,bn)->(bm+i,bn+j) in a complete bipartite graph with parts of size m and n def MkovKmn(m,n,bm,bn,i,j): mfn = binomial(n-bn,j)*(1-(1-(bn+1.0)/n)^bm)^j*(1-(bn+1)/n)^(bm*(n-bn-j)) nfm = binomial(m-bm,i)*(1-(1-(bm+1.0)/m)^bn)^i*(1-(bm+1)/m)^(bn*(m-bm-i)) return mfn*nfm 
       
#Kmn expected propagation time starting with one vertex colored in the part of size m, e terms computed (using sum approximation of EPT) def KmnEpt(m,n,e): A=zero_matrix(RDF,m*(n+1)) for bm in [1..m]: for bn in [0..n]: for i in range(m-bm+1): for j in range(n-bn+1): A[(bm-1)*(n+1) + bn, ((bm+i)-1)*(n+1) + (bn + j)] = MkovKmn(m,n,bm,bn,i,j) EPT=0 for r in IntegerRange(1,e): #estimate EPT with powers of Markov matrix EPT=EPT+r*((A^r)[0,(m*n+m)-1]-(A^(r-1))[0,m*n+m-1]) return EPT 
       
#generates the data in the appendix table with EPT values for Kmn for n in [1..10]: #range of orders to check for m in [1..n]: print m, '&', n, '&', round(KmnEpt(m,n,200), 5), '&', round(KmnEpt(n,m,200),5) print '' 
        
1 & 1 & 1.0 & 1.0

1 & 2 & 2.0 & 2.0

2 & 2 & 2.33333 & 2.33333

1 & 3 & 2.76316 & 2.625

2 & 3 & 2.78684 & 2.79028

3 & 3 & 3.02251 & 3.02251

1 & 4 & 3.34171 & 3.2

2 & 4 & 3.21498 & 3.199

3 & 4 & 3.29626 & 3.29506

4 & 4 & 3.43624 & 3.43624

1 & 5 & 3.80904 & 3.64678

2 & 5 & 3.53899 & 3.4835

3 & 5 & 3.53847 & 3.51642

4 & 5 & 3.59296 & 3.58345

5 & 5 & 3.6754 & 3.6754

1 & 6 & 4.19683 & 4.0191

2 & 6 & 3.79086 & 3.70709

3 & 6 & 3.73857 & 3.69517

4 & 6 & 3.745 & 3.72317

5 & 6 & 3.78224 & 3.77314

6 & 6 & 3.84289 & 3.84289

1 & 7 & 4.52624 & 4.34043

2 & 7 & 4.00156 & 3.90376

3 & 7 & 3.90751 & 3.84961

4 & 7 & 3.88562 & 3.85339

5 & 7 & 3.89411 & 3.87717

6 & 7 & 3.92618 & 3.9192

7 & 7 & 3.97698 & 3.97698

1 & 8 & 4.81183 & 4.6202

2 & 8 & 4.1854 & 4.08068

3 & 8 & 4.05503 & 3.98838

4 & 8 & 4.01358 & 3.97359

5 & 8 & 4.00381 & 3.98047

6 & 8 & 4.01553 & 4.00292

7 & 8 & 4.04534 & 4.04002

8 & 8 & 4.08905 & 4.08905

1 & 9 & 5.06339 & 4.86653

2 & 9 & 4.34793 & 4.23801

3 & 9 & 4.1862 & 4.11382

4 & 9 & 4.129 & 4.08306

5 & 9 & 4.10694 & 4.07822

6 & 9 & 4.10467 & 4.08725

7 & 9 & 4.11853 & 4.10878

8 & 9 & 4.14588 & 4.14163

9 & 9 & 4.18336 & 4.18336

1 & 10 & 5.28772 & 5.08642

2 & 10 & 4.49207 & 4.37677

3 & 10 & 4.30347 & 4.22654

4 & 10 & 4.23247 & 4.18154

5 & 10 & 4.20132 & 4.16784

6 & 10 & 4.18947 & 4.1677

7 & 10 & 4.19182 & 4.17811

8 & 10 & 4.20632 & 4.19839

9 & 10 & 4.23087 & 4.22732

10 & 10 & 4.26292 & 4.26292
1 & 1 & 1.0 & 1.0

1 & 2 & 2.0 & 2.0

2 & 2 & 2.33333 & 2.33333

1 & 3 & 2.76316 & 2.625

2 & 3 & 2.78684 & 2.79028

3 & 3 & 3.02251 & 3.02251

1 & 4 & 3.34171 & 3.2

2 & 4 & 3.21498 & 3.199

3 & 4 & 3.29626 & 3.29506

4 & 4 & 3.43624 & 3.43624

1 & 5 & 3.80904 & 3.64678

2 & 5 & 3.53899 & 3.4835

3 & 5 & 3.53847 & 3.51642

4 & 5 & 3.59296 & 3.58345

5 & 5 & 3.6754 & 3.6754

1 & 6 & 4.19683 & 4.0191

2 & 6 & 3.79086 & 3.70709

3 & 6 & 3.73857 & 3.69517

4 & 6 & 3.745 & 3.72317

5 & 6 & 3.78224 & 3.77314

6 & 6 & 3.84289 & 3.84289

1 & 7 & 4.52624 & 4.34043

2 & 7 & 4.00156 & 3.90376

3 & 7 & 3.90751 & 3.84961

4 & 7 & 3.88562 & 3.85339

5 & 7 & 3.89411 & 3.87717

6 & 7 & 3.92618 & 3.9192

7 & 7 & 3.97698 & 3.97698

1 & 8 & 4.81183 & 4.6202

2 & 8 & 4.1854 & 4.08068

3 & 8 & 4.05503 & 3.98838

4 & 8 & 4.01358 & 3.97359

5 & 8 & 4.00381 & 3.98047

6 & 8 & 4.01553 & 4.00292

7 & 8 & 4.04534 & 4.04002

8 & 8 & 4.08905 & 4.08905

1 & 9 & 5.06339 & 4.86653

2 & 9 & 4.34793 & 4.23801

3 & 9 & 4.1862 & 4.11382

4 & 9 & 4.129 & 4.08306

5 & 9 & 4.10694 & 4.07822

6 & 9 & 4.10467 & 4.08725

7 & 9 & 4.11853 & 4.10878

8 & 9 & 4.14588 & 4.14163

9 & 9 & 4.18336 & 4.18336

1 & 10 & 5.28772 & 5.08642

2 & 10 & 4.49207 & 4.37677

3 & 10 & 4.30347 & 4.22654

4 & 10 & 4.23247 & 4.18154

5 & 10 & 4.20132 & 4.16784

6 & 10 & 4.18947 & 4.1677

7 & 10 & 4.19182 & 4.17811

8 & 10 & 4.20632 & 4.19839

9 & 10 & 4.23087 & 4.22732

10 & 10 & 4.26292 & 4.26292