
Percolation Simulation

This is a simulation of aspects of mathematical percolation theory.

For other percolation simulations, see Category:Percolation Simulations, or:
1D finite grid simulation
Mean run density 
2D finite grid simulations
Site percolation | Bond percolation | Mean cluster density

Let 



c


{\displaystyle c}

 be a 2D boolean square matrix of 



n
×
n


{\displaystyle n\times n}

 values of either 1 or 0 where the
probability of any value being 1 is 



p


{\displaystyle p}

, (and of 0 is therefore 



1
−
p


{\displaystyle 1-p}

).
We define a cluster of 1's as being a group of 1's connected vertically or
horizontally (i.e., using the Von Neumann neighborhood rule) and bounded by either 



0


{\displaystyle 0}

 or by the limits of the matrix.
Let the number of such clusters in such a randomly constructed matrix be 




C

n




{\displaystyle C_{n}}

.

Percolation theory states that 



K
(
p
)


{\displaystyle K(p)}

 (the mean cluster density) will satisfy 



K
(
p
)
=

C

n



/


n

2




{\displaystyle K(p)=C_{n}/n^{2}}

 as 



n


{\displaystyle n}

 tends to infinity. For 



p
=
0.5


{\displaystyle p=0.5}

, 



K
(
p
)


{\displaystyle K(p)}

 is found numerically to approximate 



0.065770


{\displaystyle 0.065770}

...

Task
Show the effect of varying 



n


{\displaystyle n}

 on the accuracy of simulated 



K
(
p
)


{\displaystyle K(p)}

 for 



p
=
0.5


{\displaystyle p=0.5}

 and
for values of 



n


{\displaystyle n}

 up to at least 



1000


{\displaystyle 1000}

.
Any calculation of 




C

n




{\displaystyle C_{n}}

 for finite 



n


{\displaystyle n}

 is subject to randomness, so an approximation should be
computed as the average of 



t


{\displaystyle t}

 runs, where 



t


{\displaystyle t}

 ≥ 



5


{\displaystyle 5}

.

For extra credit, graphically show clusters in a 



15
×
15


{\displaystyle 15\times 15}

, 



p
=
0.5


{\displaystyle p=0.5}

 grid.

Show your output here.

See also
 s-Cluster on Wolfram mathworld.
package require Tcl 8.6
 
proc determineClusters {w h p} {
    # Construct the grid
    set grid [lrepeat $h [lrepeat $w 0]]
    for {set i 0} {$i < $h} {incr i} {
	for {set j 0} {$j < $w} {incr j} {
	    lset grid $i $j [expr {rand() < $p ? -1 : 0}]
	}
    }
    # Find (and count) the clusters
    set cl 0
    for {set i 0} {$i < $h} {incr i} {
	for {set j 0} {$j < $w} {incr j} {
	    if {[lindex $grid $i $j] == -1} {
		incr cl
		for {set q [list $i $j];set k 0} {$k<[llength $q]} {incr k} {
		    set y [lindex $q $k]
		    set x [lindex $q [incr k]]
		    if {[lindex $grid $y $x] != -1} continue
		    lset grid $y $x $cl
		    foreach dx {1 0 -1 0} dy {0 1 0 -1} {
			set nx [expr {$x+$dx}]
			set ny [expr {$y+$dy}]
			if {
			    $nx >= 0 && $ny >= 0 && $nx < $w && $ny < $h &&
			    [lindex $grid $ny $nx] == -1
			} then {
			    lappend q $ny $nx
			}
		    }
		}
	    }
	}
    }
    return [list $cl $grid]
}
 
# Print a sample 15x15 grid
lassign [determineClusters 15 15 0.5] n g
puts "15x15 grid, p=0.5, with $n clusters"
puts "+[string repeat - 15]+"
foreach r $g {puts |[join [lmap x $r {format %c [expr {$x==0?32:64+$x}]}] ""]|}
puts "+[string repeat - 15]+"
 
# Determine the densities as the grid size increases
puts "p=0.5, iter=5"
foreach n {5 30 180 1080 6480} {
    set tot 0
    for {set i 0} {$i < 5} {incr i} {
	lassign [determineClusters $n $n 0.5] nC
	incr tot $nC
    }
    puts "n=$n, K(p)=[expr {$tot/5.0/$n**2}]"
}