Percolation Problem


Harshit Maheshwari
Computer Science, IIT-Kanpur

What is this percolation problem ? The most common form of stating percolation problem is:

"Given a 2-dimensional $n \times n$ grid, where each cell can be 'open' or 'closed' with a probability $p$. What is the probability that there exists a path from first row to the last row such that we can move only from one open cell to another with the constraint that the cells be adjoining (diagonal transitions are not allowed) ?"

As of now we don't a mathematical model to solve this question. However, it can be solved using Monte Carlo simulation technique. The result for the 2-dimensional simulation case are very common. We will look further at 3, 4, 5, 6-dimensional cases.
Adjoining Cells: One n-dimensional cell is adjoining to other n-dimensional cell only when one of it's $n$ dimensions, say $i$ differs from the corresponding $i^{th}$ dimension of the other cell by $\pm 1$.
Transition: We can have a transition from one n-dimensional cell to another only when they are adjoining.

Since, the time-complexity of the simulation increase very quickly with increase in dimensionality we had to compromise between the number of iterations, probability gap and the value of $n$. The graphs below show the variance of the probability of reaching the other end of the lattice with respect to the probability of cells being 'open' for the aforementioned dimensions.
I will soon update the results obtained by mathematical formulation for the 2-dimensional case.

Graphs

For 2,3-dimensional lattice: 20($n$), 1000(iterations), 100(probaility gaps)
For 4,5-dimensional lattice: 10($n$), 100(iterations), 100(probaility gaps)

For 6-dimensional lattice: 5($n$), 10(iterations), 10(probaility gaps)





References

A Case Study: Percolation
Chart.js