OFFSET
2,1
COMMENTS
A player chooses a target t > n and rolls a fair n-sided die repeatedly, keeping a running total of the numbers rolled. The player wins if t occurs in the sequence of running totals. a(n) is the choice of t that maximizes the probability of winning
A fair die with sides numbered 1 through n is assumed.
For given n, sum s occurs by adding one die role to a sum s-n .. s-1; so the probability p(s) of s occurring is p(s) = Sum_{i=1..n} p(s-i)*(1/n), i.e., the mean of the preceding n probabilities, and starting from p(0) = 1 for s=0 always occurring and p(s) = 0 for s < 0 never occurring.
It is immediately apparent upon plotting the probabilities from sum s = n+1 onwards that the highest probability is achieved at s = a(n).
It can be shown that, given the equation of n < s <= 2n, the maximum near a(n) is the only zero of the first derivative, and the second derivative is always negative, therefore any following probability must necessarily be less the maximum of the previous n probabilities, and therefore less than p(a(n)). Therefore any subsequent terms must then be less than p(a(n)). Because this is appending a rolling average of the previous n terms the probabilities dampen in their oscillations about a value of 2/(n+1).
LINKS
Paolo Xausa, Table of n, a(n) for n = 2..10000
James Monroe, Pi is Evil, Numberphile youtube video. Note the errata by the authors in the comments: a(20) is actually 35. In addition, the more accurate approximation of (e-1)(n+1/2)
FORMULA
For n < s < 2n, the probability of sum s occurring is p(s) = ((n+1)^(s-1) - s*n^n*(n+1)^(s-n-2))/n^s, which means that, from the difference between s and s-1, the sequence value is given by:
a(n) = floor(((n+1)*(n+1)^n - n^(n+1))/n^n).
a(n) = A060644(n) - n.
An empirical observation is that a(n) is well approximated by (e-1)*(n+1/2).
EXAMPLE
For n=20, the probability of occurrence p(s) of sum s > n begins at p(21) = 0.08266... and rises to p(35) = 0.09767... before decreasing to p(36) = 0.09760... and never reaches p(35) again, so a(20) = 35 is the sum s with greatest probability of occurrence.
s p(s)
-- ----------
21 0.08266...
...
34 0.09751...
a(20) = 35 0.09767... <--- maximum probability
36 0.09760...
...
42 0.09350...
MATHEMATICA
PROG
(Python)
from fractions import Fraction
a = lambda n: int(Fraction((n+1)*(n+1)**n-n**(n+1), n**n))
CROSSREFS
KEYWORD
nonn
AUTHOR
Nicholas Stefan Georgescu, Oct 10 2023
STATUS
approved