Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

nor's blog

Probability 101, the intuition behind martingales and solving problems with them
By nor, 16 months ago, In English

https://nor-blog.codeberg.page/posts/2022-12-31-probability-and-martingales/

  • Vote: I like it
  • +468
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
16 months ago, # |
  Vote: I like it +48 Vote: I do not like it

great blog thanks for helping the community

→ Reply
»
16 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Not able to understand but appreciation for writing ..

→ Reply
»
16 months ago, # |
  Vote: I like it +15 Vote: I do not like it

This blog gave me PTSD of my stochastic processes class lol. The blog is very informative and thanks also for providing related problems!

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I hope it helped you understand probability spaces and stochastic processes more deeply and intuitively though :)

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Fortunately I already passed that class and I have an understanding of these concepts (I've never heard of the Azuma's inequality before though), but I remember struggling a lot (to say the least) since I lacked a proper measure theory background at the time ;).

      → Reply
»
16 months ago, # |
  Vote: I like it +116 Vote: I do not like it

If this is only 101 I am fucked

→ Reply
»
16 months ago, # |
  Vote: I like it -25 Vote: I do not like it

that's not a website about math olympiads sir

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    That's why I linked a few codeforces problems too.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so, so much for this blog. Two days ago, after the good bye problem E, I wanted so badly to actually and finally learn expected value. Your blog will be read over and over again by me until I learn the maximum I possibly can from it!

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I'm glad you found it useful. This blog mostly concerns itself with building an intuitive foundation for probability, and for practicing expected value specifically, I would recommend trying out other problems (since this blog only has problems on martingales).

    A good idea could be to read the first three sections of this blog (before martingales), and go through the problems mentioned in the blogs in the Catalog under the heading "Probability Theory".

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The tutorial of 1025G - Company Acquisitions suggests to guess the pattern. Here is a way to get it without wild guesses:

Spoiler
→ Reply
»
15 months ago, # |
← Rev. 4   Vote: I like it +52 Vote: I do not like it

Since this blog seems to be getting some traction on other websites (for instance, here) that don't necessarily deal with competitive programming, I felt like I should clarify a few points:

  • The reason why I called it probability 101 was to indicate that this is a foundational blog in some sense. The content might be dense, but it tries to tie together concepts that are treated in a much more rigorous sense elsewhere, and it is easy to get lost in the content. Understanding the connections tends to be more important than the contents themselves for complex topics (this is also part of the reason why "meta" things like category theory exist in the first place).
  • The blog doesn't just talk about martingales, it treats it as a nice topic in probability theory that deserves some attention for itself. The main motivation behind writing the blog was to inform people of a mathematically "correct" way of thinking about probability and random processes that you can build some intuition around. Looking at the concepts structurally is how the blog goes around explaining probability, and though not all of the ideas developed will be useful for martingales directly, all of them are important in developing the relevant understanding of probability in general from a bottom-up perspective.

  • The problem solving mentioned in the topic deals with math Olympiad and competitive programming problems -- it won't be necessarily applicable in real life situations in the form it is explained. Real life applications usually involve stochastic calculus where these concepts need some more rigour to be made precise, and they fit very neatly into that theory. However, the point of my blog was to show applications in more discrete settings. In fact, the blog was written with the idea that this theory wasn't developed just for formalizing probability — rather, it is a clear way of thinking that makes you understand probability from another perspective, and naturally leads to things like random processes.

  • Sigma algebras naturally arise from the definition of probability. They're just a triple of two related sets and a function, so if you follow along the blog with some attention and pen and paper (yes, I'm aware that the blog is dense in quite some parts), it shouldn't be hard to grasp the main ideas. Having some working knowledge of set operations is pretty much the only prerequisite. The point is, don't be afraid of mathematical objects. Work out some examples and get a feel of the operations and structures involved.

  • Again, sigma algebras arise naturally as a representation of all possible information you have about a set. In the context of processes, more refined sigma algebras correspond to having more progress in the process (because you can roughly reason about more possibilities). I don't know of a more intuitive (and correct) way of reasoning about processes generally. Reading the section on martingales will help understand why the sigma algebra formalism is so important.

The bottom line is that it might take a couple of readings to completely understand the presentation of topics, and the reason why they were presented in the order they were. Perhaps looking at the problems and explanations of the significance theorems might help in understanding the underlying ideas more concretely. Also, the context in which you might know martingales may be very different from what the blog covers. The ideas remain the same in both cases — that abstraction is why math is so important nowadays.

→ Reply