2
$\begingroup$

Suppose that user receives reputation only by upvotes and downvotes of her/his question and that for every upvote she/he can have either $0$ or $1$ or $2$ downvotes, with equal probability, equal to $\dfrac {1}{3}$. Also, suppose that downvotes can only be received after an upovote had been received, so that reputation is strictly increasing by $5$, $3$ or $1$ points at every step.

How many prime numbers (as the score of the reputation) are expected (on average) until the reputation is $\geq 100 000$?

$\endgroup$
18
  • 3
    $\begingroup$ Seems like a simulation problem. $\endgroup$
    – lulu
    Dec 15, 2017 at 14:39
  • $\begingroup$ Are you considering "steps" (beginning at $1$?) that result from the net addition and subtraction of an upvote and corresponding downvotes (per your probabilistic model), or should intermediate values of reputation between upvotes and downvotes be considered? $\endgroup$
    – hardmath
    Dec 15, 2017 at 14:42
  • 1
    $\begingroup$ I made an edit to be more clear and precise. $\endgroup$
    – user480281
    Dec 15, 2017 at 14:46
  • 1
    $\begingroup$ @lulu: Yes, it should converge to 1/3. Intuitively this is because for each number we hit we have just skipped either 0, 2, or 4 numbers with equal probability, averaging 2 skipped numbers for each hit number. $\endgroup$ Dec 15, 2017 at 14:59
  • 1
    $\begingroup$ @lulu: The roots of $x^5-\frac13x^4-\frac13x^2-\frac13$ other than $1$ have magnitudes $0.74$ and $0.78$ which tells us how quickly the transient ought to fall off. $\log_{10}(0.78)$ is about $-0.1$, so I would expect $P(10k)$ to approach $0.333\ldots$ to about $k$ significant digits (or better). Does that match your results? $\endgroup$ Dec 15, 2017 at 15:18

1 Answer 1

2
$\begingroup$

As clarified the reputation advances with each upvoted question by $1,3,$ or $5$ with equal chances.

An exact computation is possible using the linearity of expectation.

That is, the expected number of primes below (say) $100,000$ that will be "hit" by a reputation "trajectory" is simply the sum of probabilities of hitting for each such prime.

As Comments by Henning Makholm and lulu explain, the probability of any particular number being hit approaches one-third fairly quickly. So a decent approximation to the expected number of primes occurring in the reputation history is one-third of these primes, e.g. roughly $\pi(10^5)/3 = 9592/3$ before reputation passes $100,000$.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy