There is another stronger condition that is the fundamental of Metropolis-Hastings algorithm called Detailed Balance, which will be my next topic.

All codes are available in
github.com/ridhoma/mont...

This is a very fundamental concept for developing MCMC sampling algorithm. Because we want the sampling process to converge to our target distribution, we must make sure the sampling process;
1. Satisfy Markov property / be a Markov-Chain
2. Irreducible
3. Aperiodic

Moreover, Markov-Chain must be irreducible and aperiodic to guarantee reaching a Stationary Distribution. Irreducible: every state can be reached from any other state. Aperiodic: the chain does not cycle through states in a fixed period.

This interesting properties only applies if the random walk follows a Markov process, that is the probability of transition to the next node/state depends only to the current state. Such graph we may call a Markov-Chain

No matter which node we started at, with long enough simulation time, the distribution of visit frequency will converge to the same values called Stationary Distribution. This also applies with larger graphs.

Moreover, it took only 3 minutes to run this. Soo.. i'm satisfied.

In the scheme of learning MCMC, this exercise is a good familiarization to the concept of rejection sampling, a simple example for Markov-Chain based state proposal, and good introduction to Metropolis-Hasting algorithm

Finally, compare the final solution with greedy algorithm and the result is quite good. It gives 12% shorter distance than greedy. According to ChatGPT, greedy usually gives sub-optimal solution that is 10%-20% global optimum. So our solution might be close 😜

During the first 1000 iterations, Temperature is kept high to maximize the search space. Then it's gradually lowered to start the optimization. Finally temperature is kept low to fine tune the final solution

It took me quite a number of trials to fine-tune the To and the annealing function until I'm satisfied with the outcome. I ended up with this annealing schedule.

This cooling down process is called annealing in material science, hence the algorithm is called Simulated Annealing. The success of finding the optimal solution depend on the initial temperature (To) and the annealing schedulefunction, T(t) = f(To, t)

We repeat the process and after each iteration we will slowly reduce the temperature (slowly cool down the system). Until the temperature reach ~0 we stop the process and whatever the solution we have is our final solution.

We can control how likely we accept the worse solution using temperature parameter T. The higher the temperature, the more likely we accept route even though it is worse than the current route. This encourage exploration of the search space and help escaping local minima

Here "energy" is just a fancy term for "total travel distance" of the TSP route. We will accept the proposal if it gives lower energy than the current solution (distance improves). Otherwise, we may still accept it but with probability exponentially drop as the energy difference increase.

The algorithm basically starts with a random initial state/solution. Then we change the solution with some perturbation function, we call the the proposed next solution. We either accept/reject the proposal depending the energy of the proposed state compared to current state.

Wkwk siap suhu

I'd also like to make my github repo public (with all the codes, visualization, equations, and comments), but probbaly later. Dirapihin dulu, malu kalau berantakan

However, this randomness behavior is not bad at all. Using a technique called Simmulated Annealing, we can take advantage of this behavior and use Monte-Carlo to efficiently solve optimization problem, e.g. Traveling Salesman Problem. Something I will post next time

However, Monte-Carlo is not the best method to estimate pi because it converges very slowly, with rate of 1/√n. Not only that, as more random points are added we might randomly ruin a previously better estimation and end up getting a worse estimation.