Non-Uniform Coupon Collector’s Problem

The Coupon Collector’s Problem is a neat little problem in probability, and I first heard about it recently on the statistics subreddit. You, like me, might be familiar with it if you’ve ever tried to solve the expected number of boxes of cereal to buy to get all the toys. Not that I have that problem right now, but it shows up on probability quizzes and the like.

The problem’s solution hinges on two things. One, there is replacement (sampling from a seemingly infinite population of items that are in some proportion). Two, all items are equally likely. What happens when they aren’t equally likely? We turn back to Absorbing Markov Chains (AMC), because apparently that has to be 50% of what I talk about on here!

Continue reading →

Progressive Betting Strategies Analysis with Markov Chains

If you are a fan of statistics and probability, then you might have a certain affinity for various games of chance. It can be quite fun to, for example, figure out card counting strategies in Blackjack with simulation. It might also be interesting to try to use some machine learning on the basic strategy tables to figure out smaller, easier to learn sub-sets (something that I want to try at some point).

Hopefully you are also aware of the Gambler’s Fallacy. If you have (or think you have) a problem with gambling, don’t be afraid to seek help! Also, never EVER gamble with money that you can’t afford to lose. Always set aside a given amount of money that you are 100% fine with losing all of (because that will happen).

There are excellent sites out there (like Wizard Of Odds) that give excellent information on probabilities and house edges (notice how none are in our favor!). There are also plenty of discussion of strategies (usually about how bad they are). What I was curious about was whether or not some betting strategies were able to increase the probability of making a set profit (and then stopping). Most people don’t go to the casino very often (if at all), so I wanted to find out about short-term behaviors of these strategies, rather than the obvious long-term failure.

Using Markov Chain analysis and Monte Carlo simulation (in the next post), I’m going to examine some betting strategies. The obvious conclusion is “you will still lose everything in the long run”, but there are some interesting twists along the way. I’ve included some code so you can set up your own analyses, too!

Continue reading →

Computational Methods for Games 2: Markov Chains

In many games, tabletop or otherwise, there are a series of positions, board states, or other features that occur in some kind of order. In monopoly, for example, you travel in a circle. Each property is a ‘state’ that your piece (battleship!) can be in. In something like Candyland, Chutes and Ladders, or Mr. Bacon’s Big Adventure, there is a goal state to reach, and you do things (roll die, draw cards, etc.) to try to get there.

What makes these more complicated than say, just figuring the combined probability of rolling a certain sum for many die, is that the game states branch. Branching just means that you can reach more than 1 state after your current one. Markov Chains are a powerful tool for analyzing a game’s progress through it states, and this post will show you an example of that, using the game Betrayal at House on the Hill.

Continue reading →