Probability 101, the intuition behind martingales and solving problems with them

https://codeforces.com/blog/entry/110801

by mbustamanter • 3 years ago

159 51 3 years ago

Is there a slightly less dense version of this for those of us a bit more removed from uni maths somewhere? Willing to read three times as much text to get the same insight. :)

nerdponx3• 3 years ago

The article posted here is kind of a crash course in mathematical probability, so don't feel bad for being intimidated or overwhelmed.

The Wikipedia page gives a succinct explanation: https://en.m.wikipedia.org/wiki/Martingale_(probability_theo....

... the conditional expected value of the next observation, given all the past observations, is equal to the most recent observation.

The book Introduction to Probability Models by Sheldon Ross is a solid undergraduate-level introduction to this material. Martingales are covered in chapter 10.

It does use plenty of math notation, but none of the abstract stuff here about triples, filtrations, etc. It might be a bit slow at first as you "reactivate" the mathy parts of your brain, but as long as you read with a pencil and notepad handy you should be able to work through it.

There's actually a full upload of the 11th edition (current is the 12th I believe) on some university course webpage: http://mitran-lab.amath.unc.edu/courses/MATH768/biblio/intro...

hansvm• 3 years ago

Martingales are a representation of a class of "do a random thing 'forever'" problems, with a self-similarity constraint and also the restriction that your reward is finite, both of which prevent them from being applied to most problems but make them vastly more computationally tractable. That they're well studied means we know some of those features.

The author then mentions a few of those computational properties (like "Azuma's inequality") and gives a smattering of problems where directly applying them and ignoring most of the rest of the article would help build an intuition.

The rest of the article is useful mostly because it puts all of the above in a more rigorous context and because if you're closer to uni maths it'll help provide some sort of intuition for why the restrictions were necessary and what sort of things might or might not be achievable with them. There's probably a less dense version somewhere, but I'm not quite sure what it would be. Hopefully this short summary helps you know what to look for when you find it.

spapas82• 3 years ago

This gives a mathematical martingale. I only know the betting strategy martingale https://en.m.wikipedia.org/wiki/Martingale_(betting_system)

fnbr• 3 years ago

The betting strategy martingale is an example of a mathematical martingale.

krackers• 3 years ago

At least intuitively, I find it easier to think of martingales as betting strategies, basically a process where given a past sequence of events it spits out some wager on a prediction of the next outcome. Then there's a correspondence between the fairness criterion and betting functions.

https://math.berkeley.edu/~slaman/papers/mlreals.pdf

nerdponx3• 3 years ago

I like to see good math topics, but I really can't stand when the example problems are either totally fanciful or totally abstract. I'm too stupid for that. Give me an example of a practical problem in business, finance, engineering, social science, etc. that I can solve with this tool. Does the "dance party" problem have an analogue in real-world allocation and planning problems? Does a gambler gambling an infinite number of times have practical applications in finance? Etc.

Swizec• 3 years ago

Does a gambler gambling an infinite number of times have practical applications in finance?

If you’re running a sovereign investment fund (or Softbank?), that’s a lot like gambling with an infinite runway. Hopefully you’re using part of that infinite runway to hire people with actual chops in probability and don’t need this article.

cjohnson318• 3 years ago

I agree, I kept looking for an example of solving the problem that the post opened with: "how much longer until XYZ happens". Maybe I missed it?

jrumbut• 3 years ago

I was expecting survival analysis to show up at some point.

Perhaps it did, at some point I started to skim.

scaredginger2• 3 years ago

From a pure mathematics standpoint, why should a mathematical concept need a practical application to justify its existence?

'I have never done anything "useful". No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world.' - G. H. Hardy

It's worth noting however, that much of Hardy's work has been applied since his death, and even before it (to my understanding).

KyeRussell• 3 years ago

Talk about a hammer looking for a nail! Nobody said anything t about justifying a concept’s existence. The comment is quite clear.

dataflow• 3 years ago

The one thing I've never seen any "introduction" to martingale cover is why you should (intuitively) be able to deduce anything useful about them at all, given the expectation is defined not to change (to clarify, I meant expected not to change). Especially when the first example is often the stock market, and everyone knows you can't predict movements of the stock market...

CrazyStat2• 3 years ago

given the expectation is defined not to change.

To be clear, in a martingale the expectation is equal to the current value. It changes as the current value changes (i.e. as time passes).

Especially when the first example is often the stock market, and everyone knows you can't predict movements of the stock market...

Not being able to predict movements is exactly what "the expectation is equal to the current value" looks like. If you had information that changed your expectation to be different from the current value, that would be predicting a movement in one direction or the other.

chinaman425• 3 years ago

Come on, he meant accurately predict it, and you knew that.

JustFinishedBSG• 3 years ago

given the expectation is defined not to change.

Sure the unconditional expectation doesn't change, but that's kinda useless because it's the expectation given that you know nothing. The interesting part is studying what is next given what I know right now i.e conditional expectations. And the martingale assumption i.e. "my best guest for tomorrow is the same as right now" is honestly a pretty sensible assumption for many things.

If I tell you $TSLA is at 200 right now, it's not unreasonable to assume it will be around 200 tomorrow.

If it's raining right now, it doesn't seem too far fetched to guess it will probably be raining in 1 minute.

etc.

And because you can prove so many things on martingales, it is often very very useful and powerful when you have something that isn't quite a martingale to think of a way to make it a martingale, prove whatever and then go back to the original object.

kqr2• 3 years ago

If it's raining right now, it doesn't seem too far fetched to guess it will probably be raining in 1 minute.

That's a bit of an unfair example, though. If the Tesla stock is at 200 right now, the martingale property implies that I should expect it to be at 200 not just next minute or tomorrow, but also next week, two years from now, next decade, and so on. A martingale is not restricted in its time scale.

(This is using clearly expectation in the technical sense. The stock price may well go up, or go down, but we can't tell which or how much, so in the grand scheme of things, we're better off assuming it won't move at all.)

time_to_smile• 3 years ago

everyone knows you can't predict movements of the stock market...

That's why you use a distribution to model the distribution of future possible prices given the information you have today.

The entire point of modeling the market as a martingale: you don't know what the future price is, but you do know a pretty good deal about where the price might go at various point in the future. Perhaps the single most important thing you know is that the future price is expected to be the same as the current price (ignoring the risk-free rate).

The Martingale property is very important to understand about stocks because if you are certain that the expected price of a stock is less than its current value you should sell, if you believe it will be more you should buy. An entire market thinking like this means that the current price should be equal to the expected future price.

Additionally these models don't "predict" future prices, but rather represent what the market believes about future prices given the current price and other information. This is essential to properly modeling risk and pricing assets.

behnamoh• 3 years ago

I wouldn't call this "intuition", more like a detailed and thorough explanation of the topic.

FreeTrade• 3 years ago

The trouble with mathematical approaches to gambling is that while the expected value is taken into account, the emotional value of a bet is rarely considered.

Take a lottery for example - from an expected value point of view it is of course foolish to play most of the time. But the emotional value to the player - he can spend a few dollars and spend the night imagining what he might do with his winnings. That's good value!

With that in mind, I plan to play the martingale next time i go to Las Vegas. I will place a bet of a hundred dollars and rebet until I win a hundred dollars or lose 6300 dollars.

When I win I shall enjoy dinner and drinks courtesy of the casino and feel very good 63 out of 64 nights. Once in a while I'll lose $6300 and feel terrible, but emotional value is summed quite differently to expected value, so it won't out weight the wins.

Keegs• 3 years ago

“The expected value is negative so playing the lottery is silly” also misses that someone looking for a way out of poverty and seeing a lack of alternatives might judge the opportunity cost of his 2 dollars and 5 minutes worth the vanishingly small chance of getting a payout. The choice gets harder to defend the more you play, but I think it’s in bad taste to say lotteries are a tax on people bad at math.

IIAOPSW• 3 years ago

Being in poverty and lacking in numeracy and other educational basics correlate. What you point out is no contradiction.

arcticfox• 3 years ago

Once in a while I'll lose $6300 and feel terrible, but emotional value is summed quite differently to expected value, so it won't out weight the wins.

I'm not sure I'd trade two months of "free" dinners for one day of getting smacked $6300...! To each their own I guess.

throwaway815234• 3 years ago

You want to read about the Kelly criterion for that. Russ O'Connor has a good article explaining why the lottery is a bad deal on that basis: http://r6.ca/blog/20090522T015739Z.html

sn412• 3 years ago

Many have been asking for an intuitive explanation of martingales. The following is the historical context, which helps understand some of the motivation.

suppose you have a fair coin, and you bet 1 dollar that it comes up heads. if it does, then you get 2 dollars, and you gain 1 dollar and exit.

suppose you lose. then put $2 on the next being head. if you win, you get double, for a gain of $4-($2+$1)=$4-$3=$1.

on third toss, put $4. if it comes up heads, you get $8. the gain is $8-$7=$1.

so every time you lose, double the previous bet. you can exit with $1 gain on your first win.

this was the original, flawed, martingale strategy. what's wrong?

then we realize that there is one outcome where you lose all your stake. On that path, your loss is exponential in the number of rounds!

another way to state that is that the expectation of the money after any round is $1, your initial stake. This is where the insight of expected value being preserved comes from.

kqr2• 3 years ago

Confusingly, while this betting strategy is the original "Martingale", it's not really what's meant by the term in probability theory.

An intuitive explanation of martingale in the more technical sense is simply that "your best guess for the future value of a series is its current value". I.e. on average it won't deviate up or down from where it is now, regardless of past values.

But, crucially, that applies at any given time. It means that every time the value moves up and down, you should reset your expectation and believe that whatever value it is now is the new normal.

Some things that are not martingales are

- processes that are biased to move more up than down, or vice versa,

- processes that are mean-reverting, i.e. when they have gone up for a while they are likely to go down again, and

- more generally, processes whose future value can be predicted better by using more information about their recent past.

sn412• 3 years ago

Thank you for these nice intuitions, especially the negative examples. I liked the second point.

MrPatan• 3 years ago

One of my first programs calculated the odds of losing everything with a martingale strategy for a desired outcome and starting capital.

It needed so much capital to get to a safe enough point that it'd be better to just put the money in the bank (but thinking back, this was back before 0 interest rates, so there's another lesson there for you....)

ajkjk3• 3 years ago

it's crazy how unhelpful all the sigma algebra theory is for this. It changes none of the logic or intuition; it just obfuscates the hole theory and makes it inaccessible.

thomasahle• 3 years ago

I agree a "Probability 101" article shouldn't use sigma algebras. It definitely cuts off 99.9% of the people that might benefit from the article.

Not that sigma algebras don't have a place. If you are actually doing advanced things with martingales, sigma algebras are nice clean framework to express what you are doing.

throwaway815234• 3 years ago

It looks like a good article for those who are already studying theoretical probability. For laypeople, not so much.

I haven't yet figured out what the author is doing with the sigma algebra machinery. I had thought that the event set of a probability space was intuitively the power set of the sample set, and that the machinery of sigma algebras was only added to avoid pathologies like non-measurable sets (think Banach-Tarski paradox). Maybe there is more to it?

I would like to understand this better and I do plan to read the article, but I had found the Wikipedia article on martingales to be reasonably understandable a while back. The good thing about this article is it shows applications.

throwaway815234• 3 years ago

I think this article is not "martingales for laypeople". It is "martingales for math nerds" where the application is solving certain types of math problems to mathematical standards of rigor. For that rigor, you do need the sigma algebras. I would say also, the target reader of the article already knows what a sigma algebra is, so the formal definition is given only for review purposes, plus to motivate something the author does about finding a disjoing minimal cover of the sample space. I haven't yet read the article carefully enough to understand why he does that.

ajkjk3• 3 years ago

*whole :(

cevi• 3 years ago

Completely agree, speaking as a mathematician who put in the time to understand the details of sigma-algebras. It's an implementation detail. We don't need to talk about inductors and MOSFETs to describe how bubble-sort works, and we don't need to talk about sigma-algebras to talk about conditional probabilities or expectations.

A wacky alternative implementation of probability theory can be found in Nelson's book "Radically Elementary Probability Theory" - I highly recommend it as a way to see how little the underlying framework matters.

hintymad• 3 years ago

It's pretty amusing that smart people would think that sigma algebra and the concept of space, let alone equivalent space and random variables in the language of sigma algebra, were "intuitive" in a Prob 101 tutorial.

chasebank3• 3 years ago

Let's say I'm applying martingale on an index like SPY or QQQ, which I plan to hold otherwise in a tax free retirement account. If I run out of cash to double down, I'm in the same position as I would be otherwise, except I've averaged down my entry price. When the index eventually comes back up, you profit, and resume martingale. How could this be a losing strategy on an asset you plan to hold otherwise?

pilarphosol• 3 years ago

I’d look into the Kelly criterion to get more color on this.

lordnacho• 3 years ago

Plug the numbers into the Kelly criterion.

The fraction of your wealth you should bet when the coin is fair and you get paid evens is zero.

chasebank3• 3 years ago

Kelly criterion is applicable to betting / trading, where you're winning / losing. If you never 'lose', ie., stay in the market, martingale seems really promising. For instance, SPY will never go to 0. The FED / US govt will never let it. In fact, it can't - it would destroy the US economy. So when you're playing a game where you know the graph will always to up and to the right, eventually, martingale seems appropriate.

FWIW, I trade futures on the side and have always been interested in DCA or martingale long strategies.

throwaway815234• 3 years ago

This has nothing to do with martingales as a term used in gambling. A martingale in probability theory is just a type of stochastic process with certain mathematical characteristics, and this article is about using them on certain types of math problems where their usefulness is not otherwise obvious.

Probability 101, the intuition behind martingales and solving problems with them

Related Stories