patternMinor
How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?
Viewed 0 times
thesimulateknightmovewouldpercolationthresholdconnectedhowexplore
Problem
"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation threshold of this graph?"
Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $$ or $$ for the eight cases.
In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.
Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $$ or $$ for the eight cases.
In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.
Solution
First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what event signifies that percolation happens. One common option is that the top of the board is connected to the bottom of the board. For each probability $p$, you estimate the probability that this happens by doing many samplings. You then use binary search to estimate the probability $p_c$.
Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.
Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.
Context
StackExchange Computer Science Q#47992, answer score: 4
Revisions (0)
No revisions yet.