Yes I know this might seem irrelevant for a Codeforces Blog but recently I came across something really interesting. A mathematical strategy that will always ensure a win in a gambling game! (Spoiler: Obviously there is a catch). What makes it relevant to post here is the perfect mathematics that goes behind it. Lets take a look at the maths behind a strategy that always guarantees a win.

The Martingale Strategy ensure a win in any game with close to 50 percent winning odds. Leaving out the part that it is a gambling strategy let us look at a scenario:

How it goes:

• A bet of 1$ is made with 50 percent winning chances. If you win, you get 2$ but if you lose, you lose it all. If an infinite number of bets are made here, we will be in a situation of no profit and no loss.
• A bet of 1$ is made with 49.5 percent winning chances. If you win, you get 2$ but if you lose, you lose it all. If a large number of bets are made here, we will be in a situation of a minor net loss. The tiny 0.5 percent is how any casino or gaming website ensures their profit.
• Now the first case will never exist in the real world but the second might. This is where the martingale strategy comes into picture.

A noob's strategy:

• If you win, increase the bet (because obviously he is lucky today)
• If you lose, get scared and reset the bet

The Martingale Strategy:

• It is the reverse of the strategy above
• If you win, reset the bet
• If you lose, double the bet

The Maths:

• Lets say we start from 1$ and lose 5 bets in a row and win the 6th
• Bet amounts are as follows : 1, 2, 4, 8, 16, 32 (The 6th bet's amount)
• Total loss=1+2+4+8+16=31$, Total win=32$, Net profit= 32-31= 1$
• You can try converting all the numbers to their binary equivalent. 31 is 11111 and 32 is 100000. What is interesting is that no matter where you start the bet from, after a complete losing streak, you regain the initial bet in profit.

How it ensures a win:

• How convenient is it though? The probability of losing 5 matches in a row is 0.5^5 = 3.125 %. Now if you increase this to a 10 loss streak, a mere 0.09765 %. Now this is still more than my probability of becoming an expert on codeforces but I am certain none of you are as unlucky here.
• You can almost be certain that a win is very close.
• A person playing the martingale strategy gets happy after seeing losses.

Why it fails:

• Now it all seemed too good right, and I am certain some of you would be ready to make their huge financial investments into gambling.
• Hold your horses because to ensure a win always, you better have a billion dollars in the bank. Just like unbounded binary search, the bet space increases pretty fast here getting multiplied by powers of 2.
• Lets say you are a billionaire. Do you still win? The clear answer is NO! Every casino or betting website has a minimum starting bet and a maximum bet. Once you put a cap on these two factors, you are screwed. Now you cannot increase your bet unboundedly which pretty much takes away the possibility of regaining all what has been lost.

While it is fun to try it out once, it becomes evident very soon that you can lose all your money in log(n) time complexity. The simple answer is "The House Always Wins". My suggestion is to never try it. No matter how rich you are, you can come to the road real quick with this optimized get ripped quick algorithm.