# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
great blog thanks for helping the community
great blog thanks for helping the community
great blog thanks for helping the community
great blog thanks for helping the community
Great blog thanks for helping the community!
Not able to understand but appreciation for writing ..
This blog gave me PTSD of my stochastic processes class lol. The blog is very informative and thanks also for providing related problems!
I hope it helped you understand probability spaces and stochastic processes more deeply and intuitively though :)
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 ;).
If this is only 101 I am fucked
that's not a website about math olympiads sir
That's why I linked a few codeforces problems too.
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!
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".
The tutorial of 1025G - Company Acquisitions suggests to guess the pattern. Here is a way to get it without wild guesses:
Let $$$a_1, \dots, a_s$$$ be the sizes of the connected components in some moment. As usual, let's claim that the stopping time is $$$\sum f(a_i)$$$ for some $$$f$$$.
In one move, the expected delta of stopping time must be $$$-1$$$. The contribution of $$$a_i$$$ to this delta is $$$\Delta_i = \frac{1}{s}((a_i-1)f(1)-2f(a_i)+f(a_i+1))$$$. Let's claim $$$\Delta_i = -1/s$$$. So, we have $$$n$$$ equations: $$$f(n) = 0$$$, $$$g(i) = (i-1)f(1)-2f(i)+f(i+1) = -1$$$ ($$$1 \leq i \leq n-1$$$).
Now, we want to calculate $$$f(1)$$$. A possible way is writing an expression where the other $$$f(i)$$$ cancel out. For example, let's compute $$$S = \sum_{i=1}^{n-1} g(i) \cdot 2^{-i}$$$ in two ways:
Therefore, we can compute $$$f(1)$$$, then use $$$f(i) = -1+2f(i-1)-(i-2)f(1)$$$.
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 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.
Why did you move it to your blog webpage and now your blog is down? Now I can't read the post.