Просто кусочек переписки из рабочего чата Одноклассников. ----...

Just a piece of correspondence from the work chat Odnoklassniki.
----
[10/07/15 12:28:04 AM Mikhail Bezoyan: are there any gurus of theorver among us? there is a question

[10/07/15, 12:29:59] Leonid Talalaev: I think every second here considers himself a guru until you ask a question :)

[10/07/15 12:37:04] Mikhail Bezoyan: stupid question: I want to put an object in the cache only for N error, but I don't want to store the number of errors We need such a probability distribution function of the probability of adding an object to the cache so that the expected number of a slip to which the object enters the cache is approximately equal to N. Time has gone)

[07.10.15, 12:38:31] Dmitriy Y. Bugaichenko: Uniform distribution [0,1] + limit <1 / N

[10/07/15 12:39:28] Mikhail Bezoyan: what is the limit?

[07.10.15, 12:39:31] Dmitriy Y. Bugaichenko: But you can smoke a little https://ru.wikipedia.org/wiki/ Distribution_Bernulli

[07.10.15, 12:40:01] Dmitriy Y. Bugaichenko: Do ​​not float the brain and do rnd.nextDouble () <1.0 / n

[07.10.15, 12:40:24] Mikhail Bezoyan: if I zayuzayu uniform for N = 2 then the probability that the papade in the cache with 2 attempts will be 1/2 + 1/4 not? Maybe that's right, of course.

[10/07/15 12:41:12 AM] Dmitriy Y. Bugaichenko: You also need to wait for the number of attempts after which you need to. In fact, it is both empirical for you to choose N. Ie. just need some kind of regulator. And the main thing is not to complicate

[07.10.15, 12:43:01] Mikhail Bezoyan: is there evidence that the expectation will be N?

[10/07/15, 12:43:04 PM] Leonid Talalaev: without a random house, you can start a global counter of misses and put it only when it is a multiple of N

[10/07/15 12:43:07 PM] Mikhail Bezoyan :)

[10/07/15 12:43:11 AM] Vyacheslav Baranov: there is another option of counting bloom filter. It will be more accurate

[10/07/15, 12:44:21] Dmitriy Y. Bugaichenko: If you want evidence, smoke the Bernoulli distribution. But here KISS is much more important.

[10/07/15, 12:46:16 PM] Shevchuk Aleksey: Misha, but weakly make a variant with counters + the proposed probabilistic variants and check what approach will work more precisely on the experiment?)

[10/07/15 12:47:35 AM] Dmitriy Y. Bugaichenko: You can make a unit testik simple and emulate

[07.10.15, 12:48:11] Mikhail Bezoyan: still suggest making a report on this topic)

[07.10.15, 12:49:03] Dezhin Ilya: write an article :)

[07.10.15, 12:49:03] Vyacheslav Baranov: On 07/10/15, at 12:46, Aleksey Shevchuk wrote:
> Misha, and weakly make a variant with counters + proposed probabilistic options and experiment to check which approach will work more precisely?)

Here, even the choice of f-tion accuracy can cause a week of flooding.

[10/07/15, 12:50:26 PM] Oleg Larionov: well, in fact, it turns out that if you choose for each het, put or not put, and put with probability p, then the expectation is p * sum_k = 0 ^ \ inf ((k + 1) * (1-p) ^ k)

[10/07/15, 12:51:47 PM] Oleg Larionov: and here you can play around with the p parameter and get the right expectation of how often the value gets into the cache. even the sum of the series is = 1 / p ^ 2

[07.10.15, 12:58:15] Oleg Larionov: the result is N = 1 / p, where N is the expectation. And it turns out the same thing that Dima told you

[07.10.15, 13:00:11] Mikhail Bezoyan: well, that's probably the proof)

[10/07/15, 1:02:52 PM] Dmitriy Y. Bugaichenko: Oleg Larionov is recognized as the main gur of theorist