A stable denominator week
source link: https://codeforces.com/blog/entry/125330
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
|
11 hours ago, # |
As I see, you went for the diagonals (probably because the probabilities on the same diagonal are the same), but it was much easier to go for rows (or columns), because the sum of 1/i(i+1)=1/i−1/(i+1)1/i(i+1)=1/i−1/(i+1) on a subsegment is very nice. |
-
Very nice!
Do you know if this has a combinatorial meaning? Maybe we can arrive at 1/i directly from some linearity of expectation argument?
-
Okay, so imagine that we have a chip at (n,m)(n,m), and every second we randomly move it left or down, decreasing some coordinate somehow to stay positive (this is essentially what happens in the problem). If a<na<n and b<mb<m are two positive integers, and we look at the coordinates (x,y)(x,y) of the chip during the operations, then eventually one of the following happens: x≤ax≤a or y≤by≤b. In other words, we arrive at one of the rectangles AA and BB on the figure below.
-------+ <-o | | A | v | | -------+ +-------- | | B | | +--------Now, while this didn't happen, on each operation, if ss is the number of possible jumps, the probability to jump to AA right now is a/sa/s, to jump to BB is b/sb/s, and to stay outside them is some other number. In any case, these two probabilities are always in a:ba:b proportion, therefore the probability that we arrive at AA before BB is a/(a+b)a/(a+b) (exercise for the reader, but should be intuitively obvious).
Then, provided that we ended up in AA, the probability that we are at its right border is the probability that the last jump was at this exact point chosen from aa possible points given from the premise, which is 1/a1/a. Thus, the probability that we ever were on the right border of AA is clearly the probability that the first point from A∪BA∪B that we entered was on the right border of AA, which is (the probability that we entered AA and not BB) times (the probability that on the last jump we picked this point among a−1a−1 others) =a/(a+b)⋅1/a=1/(a+b)=a/(a+b)⋅1/a=1/(a+b).
Is this what you are asking?
-
Actually, you could even say that while the chip still can reach the required border, there are three options:
to reach it with probability 1/s1/s,
to go somewhere where we can no longer win from, with probability (a+b−1)/s(a+b−1)/s,
to continue from some other place.
Again, since the first two options are the only ones that stop the process, and since their probabilities ratio is 1:(a+b−1)1:(a+b−1), then the answer is 1/(a+b)1/(a+b).
-
This argument makes sense, but it seems to be computing something different from what we need to compute?
In your top-level comment you suggest to take my solution that computes the probability that we pass through position (x, y), then sum up those probabilities by row. So we effectively compute "the expected number of times we visit the cells (x, y) for any y between y_0 and m", where y_0=ceil(k/x), and this expected number turns out to have a nice formula, something like 2/(x+y0-1)-2/(x+m). My question was whether we can arrive at this formula directly without computing the per-cell probability.
In your latest comment, you seem to be computing something slightly different: instead of expected number of visits on the boundary you compute the probability that we ever visit the boundary. It is similar, but does not have 2 in the numerator, and also does not have the "-2/(x+m)" term, so I'm not sure it is helpful in solving the original problem?
-
-
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK