Making a Board Game using MCMC!

MCMC sounds complicated ... but it's not! Let's see how we can use it to design a board game!
MCMC Principles Video : • Markov Chain Monte Car...
Metropolis-Hastings Video : • Metropolis - Hastings ...
Link to Code : github.com/ritvikmath/RUclips...

[@tianjoshua4079]

This is very instructive. I have a few comments though. In real MCMC applications, we do not know p(x). We know f(x) instead. However, since we only need to calculate p(b)/p(a), it does not matter we use f(b)/f(a) or p(b)/p(a) since p(x) and f(x) only differ by a normalizing constatnt. This game sheds new light on MCMC for me, bringing me to realize that the algorithm design is really clever in acceptance rule so that the transition matrix would make the markov chain state converge to p(x) in the long run.

[@ritvikmath]

Thanks for your analysis!

[@Parknparty]

Nice job! Nice explanation! Nice background! :)

[@ritvikmath]

Thanks! 😃

[@cwumin2105]

Hi rivikmath. Really nice explanation. I still have some doubt regarding MCMC and hope to get some clarifications from your side. Based on this board game, I wonder how it is use in inference mode? We need to run it untill achieve stationary distribution. After that, only we can use for inference? if possible, could you do a video to explain how MCMC use in inference mode? thank you very much

[@user-or7ji5hv8y]

I didn’t realize till now that the pdf used in rejection sampling corresponded to stationary probabilities. I guess that makes sense since they are unconditional probabilities.

[@BruinChang]

Hello, ritvikmath,
In this board game, if the simulation result based on the first trial setting is not { ($10, 0.4), ($15, 0.1), (-$20, 0.2), (-$5, 0.3)}, does this mean I have to change the initial trial of long term probability or state moving probability until the simulation result matches the the long-term probability setting? Thanks.

[@antoniolopardo4259]

Why isn't the diagonal filled with zeros? g never proposes to move to the same state, am I missing something?

[@sahilbatra8435]

I believe Ritvik is taking sum of all rows as 1 and calculating the diagonal values. As Prob of moving from 1 State to any of the other states should sum to 1.

[@fsaldan1]

Only 15 -> 15 is zero because 15 has the lowest probability and all the four probabilities are multiplied by the same number (0.33) before comparing.

[@oscareduardofloreshernande7853]

I have the same question! It's really a nice algorithm, but if I want to find out the transition probabilities such that the diagonal values are 0s, do I need to try different prior probabilities (in this case the 1/3 for each state)?

[@TobiT822]

@@sahilbatra8435 I think the correct way to do this would be to just divide every entry by its row's sum, i.e. norming the entries. Thereby the zeros would be preserved, as they are a designed feature of the board-game.

[@kuan-huawulu1309]

​@@TobiT822 Not sure if I get the idea correct. Ritvik did mentioned in the MCMC introduction video that there is a chance of rejecting the proposal. I think the diagonal values represent the probabilities of rejecting the transition proposal for each given state.

[@user-or7ji5hv8y]

What if we just have data, how can we then find the transition probabilities? Here you started with the long term stationary probabilities as given.

[@long2252]

Can we just generate random numbers from 0 to 1 to determine its state? (0 - 0.4 ; 0.4 - 0.5; 0.5 - 0.7; 0.7 -1 for these states?) Is the result from this simulation different from the MCMC method?

[@mohanreddy9168]

Hi Ritvik, I think it is very close to the concept of Shapley values isn't it?

[@LUTHAYAKUMAR]

Hi... I have used your code as it is using google colab, and it says that in your code you haven't defined the curr_idx, can you please provide me a solution regarding this?

[@kmshraddha5121]

please explain transitional MCMC

[@MrTSkV]

It's interesting that the average earnings per move curve can stay positive (or negative) for quite a while. Is it because the consecutive moves are not independent?

[@ritvikmath]

Yes exactly. If you look at the transition matrix, you see that $10 has a strong chance (>50%) of being positive again in the next move. $15 has a 33% chance of being positive in the next round. You can see similar negative -> negative patterns as well. So, we have constructed a fair board game given a long period of time OR across many independent players but for a specific player especially early in the game, we are likely to see "stickiness" to positive or negative values due to the non-independence of MCMC. Good question!

[@MrTSkV]

@@ritvikmath I just simulated 1 mln of independent fair coin tosses and I can see a somewhat similar pattern (far less conspicuous though). I guess the reason is that consecutive sums are also dependent, since they differ in just one number that is added each time?

[@ritvikmath]

@@MrTSkV Yup, what you simulated is exactly a "random walk". In the long run, we expect the random walk to have an expected value of 0, but in any small interval, because we can only go up or down by 1 (as you mentioned), we are unlikely to see an average value of 0.

[@user-mm4yb8td5r]

Hi Ritvik: The code in .ipynb is not working due to the undefined term: curr_idx from the line: avg_earnings = [payouts[curr_idx]]