whether it's going to percolate or not? In this problem and in many similar problems,

there's what's called a phase transition. Which says that, you know, when it's low,

it's not going to percolate. When it's high, it is going to percolate. And

actually, the threshold between when it percolates and when it doesn't percolate

is very sharp. And actually there is a value as N gets large that if you're less

than that value it almost certainly will not percolate, if you're greater it almost

certainly will. The question is what is that value. This is an example of a

mathematical model where the problem is, is very well articulated. What's that

threshold value but, nobody knows the solution to that mathematical problem. The

only solution we have comes from a computational model, where we run

simulations to try and determine the value of that probability. And those simulations

are only enable by fast union find algorithms, that's our motivating example

for why we might need fast union find algorithms, so let's look at that. So what

we're going to run is called a so called Monte Carlo simulation. Where we

initialize the whole grid to be block ed all black and then we randomly fill in

open sites. And we keep going. And every time we add an open site, we check to see

if it makes the system percolate. And we keep going until we get to a point where

the system percolates. And we can show that the vacancy percentage at the time

that it percolates is an estimate of this threshold value. So what we want to do is

run this experiment millions of times, which we can do in a computer, as long as

we can, efficiently do the calculation of does it percolate or not. That's a Monte

Carlo simulation, a computational problem that gives us a solution to this,

scientifc problem where, mathematical problems nobody knows how to solve yet.

So, let's, look in a little bit more detail of how we're going to use our

dynam-, dynamic connectivity model to do this. So, it's clear that, we'll create an

object corresponding to each site. And we'll give'em a name, from zero to N^2-1

as indicated here. And then we'll connect them together. If they're connected by

open sites. So the percolation model on the left corresponds to the, connection

model on the right, according to what we've been doing. Now, you might say,

well, what we want to do is, connect, check whether any site in the bottom row

is connected to any site in the top row, and use union find for that. Problem with

that is, that would be a brute force algorithm. Would be quadratic, right on

the face of it. Because it would have N^2, calls to find, to check whether they're

connected. For each site on the top, I'd check each site on the bottom. Much too

slow. Instead, what we do is create a virtual site on the top and on the bottom.

And then, when we want to know whether this system percolates, we just check

whether the virtual top site is connected to the virtual bottom site. So how do we

model opening a new site? Well to open a site we just connect it to all it's

adjacent open sites. So that's a few calls to Union but that's easy to implement. And

then with that, simple, relationship we can use the exactly the code that we

developed to go ahead and run a simulation for this connectivity problem. And that's

where we get the result that, by running enough simulations for a big-enough n,