How Monte Carlo could Decentralize the Internet
Article also available on Mirror
It’s just past midnight, and the table is full. You sit on the end, your trusty friend at your side. And at the other end: your arch nemesis. He screwed you over big last time you played Black Jack. But tonight will be different. You’re onto him now, and there will be no more tricks… except for the one you’re holding literally up your sleeve. But the House has taken notice. Too much notice, for your taste, and that’s when you realize… this isn’t the Monte Carlo we’re talking about.
We better start from the beginning. You know what blockchains are, right? Good, then you’ll know they are a distributed public ledger, with no central point of control. And with that, no central point of failure. Zero trust, decentralized, all that good stuff. If you don’t know how they work, here’s an article about implementing one in python.
Now that you know what a blockchain is, you’ll know it’s absolutely essential for creating a decentralized, zero-trust network. Except… it might not be.
It turns out you may not need a blockchain to accomplish those things at all. Or blocks. Or miners. What iOTA, and others have accomplished is a decentralized, zero-trust network, with no transaction fees or gas cost. All accomplished without a blockchain, using only acyclic (non-cyclical) graphs, Markov chains, and Monte Carlo.
Bayesed & Confused
I know, I know. You want to hear about Monte Carlo. But before you can play at the Table in Monte Carlo, you first have to learn the rules of the game. Let’s start with a close friend and alley of Bayes, called Prior. Priors consist of all information we previous had on a given analysis, adjusting our weights accordingly. What are weights? Well, let’s give an example.
You’ve read many carefully conducted studies on fresh water dolphins. They all say that they can’t survive in salt water. But you also have a friend who claims he knows the distinctions of fresh water dolphins very well, and claims he’s seen them swimming off the coast in seawater. How do you take his information into account? Will you view your friend’s testimony to be as as significant as the studies you read? Will you disregard all previous information you had on dolphins? Chances are, you will assign your friend’s information at a lower level than the rigorous studies you’ve read. That is to say, his account is assigned a lesser weight than the studies you’ve read. The research you’ve read is assigned a greater weight. The studies you read before talking with your friend are your priors and your friend’s testimony is called the likelihood. Instead of writing over your priors with the new information from your friend, you will merely update your priors based on this new information. Assuming your friend isn’t a marine biologist, you will probably assign his account a relatively low weight. And as result, you will give this new evidence a low likelihood of credibility. The posterior is the combination of the probabilities of your prior and likelihood, taking weights into account.
But what if a new study comes out saying fresh water dolphins have been found to survive in controlled conditions in saltwater? If the study was conducted well, you will probably assign this a greater weight than your friend. But do you just disregard all previous studies you’ve read, demonstrating they can’t survive in saltwater? The the Bayesian approach would be to take the likelihood of this study being correct, like we did before, and create a new posterior based on that and your prior. But in this case, the weight will be much greater. Perhaps it’s around 80%. So how do you factor-in new this information? If your prior says there’s an 75% chance that dolphins can’t survive saltwater, you won’t want to simply throw that out the window (or cast it into the sea). Remember that posterior from before? This is where that gets very important. As stated, it combines your priors (times their weights) and the likelihood of the new study being true (which we said was 80%). Since the new information contradicts the older information, this means that the posterior will be greater than your prior, but lower than your likelihood for the current information.
It still gives dolphins a likelihood of being unable to survive saltwater, but that confidence is lower than it was before. This posterior becomes your new prior. The key to this is that with a Bayesian net, you are constantly creating posteriors based on new likelihoods and prior information, adjusting them based on the weight of that information, and making that your new prior.
Are you still with me? You can read more about it here, if you’re still Baysed and Confused (as many usually are at first, but it becomes more intuitive the more you use it). But you might also be wondering, what does this have to do with Monte Carlo? Let’s get into that. Well, so far we’ve been dealing with very clean priors. What if your prior consists of a bunch of scattered forms of information, each with differing weights? How, when new information comes along, can you calculate the posterior?
Welcome to Monte Carlo
This isn’t the first time Monte Carlo was a big deal. Remember when that computer beat that non-computer at Go? That implemented a Monte Carlo Tree Search. Want to figure out how millions of self-driving cars can interact? Monte Carlo. Well, first we need to talk about the problem. We would love there to be certainly. And if we can’t have that, we would love to be able to calculate how certain we are. But, sometimes, that becomes too messy and computationally expensive. Monte Carlo gives us a way to get an approximation of certainty. Monte Carlo is a simulation.
Imagine you had a pet dragon (bare with me, here). And you wanted to build a house for it to live in, to shelter it from the rain. You don’t have any measuring equipment big enough for a dragon, and you don’t know its size. There’s also another small issue. It’s invisible. How could you figure out it’s approximate size? Well, remember the rain I mentioned? That could actually prove useful. As the dragon sleeps one night, there’s a slight drizzle. Not much water, but enough for there to be a scattering of raindrops over the dragon and the surrounding dirt. The next morning, as the dragon takes off, you see a slight “dragon shape” where the raindrops didn’t hit the soil. It might look something like this.
From this, you can tell the average of where the raindrops hit the dragon (where there is dry soil), and from that, you can get an approximation of how big your dragon is. It’s not perfect, but it’s close-enough.
This is essentially how a Monte Carlo Simulation works. The raindrops are random points that ‘fall’ on a given area. And without calculating the entire area, we can get an approximation of a shape’s measurement, based on which points fall inside that shape.
Markov Unchained
Now, we’re going to chain these bad boys to a Markov… chain. If you don’t know what Markov Chains are, you can read about them here. They’re everywhere. But here’s how they work with Monte Carlo.
We’re used to causal connections. The chicken eats the worm. The tourist eats the chicken. And the panda eats the tourist. But sometimes figuring out these connections is impossible given a finite amount of time and computational space. Imagine trying to calculate every event that leads to your existence, starting from birth? Or from conception(gross)? Or your parents meeting? Or their parents meeting? Or the evolution of humanity? The creation of life? The formation of the Earth? How about the big bang? Does that sound impossible? That’s because it is. The calculating capacity needed for that would quickly become larger than the size of the known Universe. An alternative to causal connections is to figure out probabilistic connections between two events.
Now, that looks like a job for Markov chains. They already connect things based on their probabilistic relationship. But how does Monte Carlo fit in?
With Monte Carlo, we get samples of posterior distribution (tying in with Bayes). To make sense of this, note that the height of the distribution is its likelihood of occurring. By running a Markov Chain multiple times, we get an approximation of likelihoods, and we can turn these into points. We can then take these points and turn them into a graph. They will likely fall on a Posterior distribution in much greater numbers where the Posterior is highest. Let’s make a Histogram from that.
Don’t Tangle with Monte Carlo
So now we get to the real deal. You’ve met Bayes. You’ve learned about Monte Carlo. You connected it to Markov Chains. Now what does all of this have to do with decentralized networks? It involves adding yet another thing Monte Carlo can do, which are called Random Walks. You can think of these as the result, if you mapped all the random movements of a mouse in a maze. When it gets interesting, is when they are weighted, which we’ll use with Markov Chains, basing the ‘movement’ of the mouse off the weights. Here’s a version in Python by Stuart Jamieson, used to calculate stock prices.
This code will return a thousand different price simulations.
IOTA uses what is called a Tangle. This Tangle is a graph implementing a Random Walk, with probabilistic weights determined by a Markov Chain, traversing through a graph. By doing this, they can actually validate not just one, but many transactions at the same time. Making it fast, cheap, and secure. It’s obviously a bit more complicated than that, and you can read the full details here. But, in ten years time, this could be all you hear about, and what truly transforms the internet, iOT, and our lives in ways we can’t even imagine yet.
So, Monte Carlo started out being this obscure math experimentation, working a pencil-pushing job, wondering what its purpose was, to being a Bayesian Master, bending distributions with its mind, validating protocols, beating Go agents, and just might be the One prophesied to free us all from a centralized internet.
And that wraps this up! Will this be the end of Blockchains? Can graph technology decentralize us all? Tune in next decade! Same block time, same block channel.
So, now if you hear someone talking about how Monte Carlo could help us decentralize the internet, you know they aren’t talking about gambling. Unless, of course, if they are.
Many thanks to these guys for making this so understandable:
https://www.geophysik.uni-muenchen.de/~igel/downloads/inviimontecarlo.pdf
