A366451 The sum s > n which has the greatest probability of occurring when summing rolls of an n-sided die.

4, 6, 8, 9, 11, 13, 15, 16, 18, 20, 21, 23, 25, 27, 28, 30, 32, 34, 35, 37, 39, 40, 42, 44, 46, 47, 49, 51, 52, 54, 56, 58, 59, 61, 63, 64, 66, 68, 70, 71, 73, 75, 76, 78, 80, 82, 83, 85, 87, 88, 90, 92, 94, 95, 97, 99, 101, 102, 104, 106, 107, 109, 111, 113

Offset: 2

Author

Nicholas Stefan Georgescu, Oct 10 2023

Keywords

• nonn

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).

Examples

			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...
		

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)

Crossrefs

Cf. A060644, A365443.

Programs

Mathematica

A366451[n_] := Floor[(n+1)^(n+1)/n^n] - n; Array[A366451, 100, 2] (* Paolo Xausa, Oct 12 2024 *)

Python

from fractions import Fraction
a = lambda n: int(Fraction((n+1)*(n+1)**n-n**(n+1),n**n))

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).

From Javier Múgica, May 01 2025: (Start)

Taylor expansion of the maximum of p(s) gives a(n) ~ (e-1)*(n+1/2) - (e-2)/(24n).

The maximum for s > 2n is attained at s ~ (e-sqrt(-e^2+2e+2))*n, approx. 2.5*n. In general, the position of the maximum for s > kn is given by an algebraic equation in s and e of degree k in each of them. (End)