A386009 -id:A386009 - cp's OEIS frontend

A386016 A sequence constructed by greedily sampling the Borel distribution for parameter value 1/2 to minimize ratio discrepancy.

1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 1, 2, 4, 1, 3, 1, 1, 2, 1, 1, 1, 2, 1, 1, 3, 1, 5, 1, 2, 1, 1, 1, 2, 4, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 6, 3, 2, 1, 1, 1, 2, 1, 4, 1, 1, 2, 1, 3, 1, 1, 5, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 4, 1, 1, 7

Offset: 1

Jwalin Bhatt, Jul 14 2025

The geometric mean approaches A386009 in the limit.

The Borel distribution has PDF p(i) = (i/2)^(i-1) / (exp(i/2)*i!).

			Let p(k) denote the probability of k and c(k) denote the count of occurrences of k so far.
We take the ratio of the actual occurrences c(k)+1 to the probability and pick the one with the lowest value.
Since p(k) is monotonic decreasing, we only need to compute c(k) once we see c(k-1).
| n | (c(1)+1)/p(1) | (c(2)+1)/p(2) | (c(3)+1)/p(3) | choice |
|---|---------------|---------------|---------------|--------|
| 1 |     1.648     |       -       |       -       |   1    |
| 2 |     3.297     |     5.436     |       -       |   1    |
| 3 |     4.946     |     5.436     |       -       |   1    |
| 4 |     6.594     |     5.436     |       -       |   2    |
| 5 |     6.594     |    10.873     |    11.951     |   1    |

Jwalin Bhatt, Table of n, a(n) for n = 1..10000
Wikipedia, Borel distribution

Cf. A386009, A386904.

pdf[i_] := ((i/2)^(i - 1))/((E^(i/2)) * Factorial[i])
samplePDF[numCoeffs_] := Module[
  {coeffs = {}, counts = {0}, minTime, minIndex, time},
Do[
    minTime = Infinity;
    Do[
      time = (counts[[i]] + 1)/pdf[i];
      If[time < minTime, minIndex = i; minTime = time],
      {i, 1, Length[counts]}
    ];
    If[minIndex == Length[counts], AppendTo[counts, 0]];
    counts[[minIndex]] += 1;
    AppendTo[coeffs, minIndex],
    {numCoeffs}
  ];
  coeffs
]
A386016 = samplePDF[120]

A386904 A sequence constructed by greedily sampling the Borel distribution for parameter value 1/2 to minimize discrepancy.

Original entry on oeis.org

1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 1, 5, 1, 2, 1, 1, 3, 1, 1, 2, 1, 6, 1, 1, 2, 1, 1, 3, 1, 2, 1, 4, 1, 1, 2, 1, 1, 7, 1, 2, 1, 3, 1, 1, 8, 1, 2, 1, 1, 5, 1, 2, 1, 1, 3, 1, 1, 2, 1, 4, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 9, 1, 2, 1, 1, 4, 1, 3, 1, 2, 1, 1, 6, 1, 2, 1, 1, 1, 3, 1, 2, 1, 5, 1, 1, 2, 1, 1, 4, 1, 2, 1, 3, 1, 1, 2, 1, 1, 10

Offset: 1

Jwalin Bhatt, Aug 07 2025

The geometric mean approaches A386009 in the limit.

The Borel distribution with parameter value 1/2 has PDF p(i) = (i/2)^(i-1) / (exp(i/2)*i!).

			Let p(k) denote the probability of k and c(k) denote the count of occurrences of k so far, then the expected occurrences of k at n-th step are given by n*p(k).
We subtract the actual occurrences c(k) from the expected occurrences and pick the one with the highest value.
| n | n*p(1) - c(1) | n*p(2) - c(2) | n*p(3) - c(3) | choice |
|---|---------------|---------------|---------------|--------|
| 1 |     0.606     |       -       |       -       |   1    |
| 2 |     0.213     |     0.367     |       -       |   2    |
| 3 |     0.819     |    -0.448     |     0.251     |   1    |
| 4 |     0.426     |    -0.264     |     0.334     |   1    |
| 5 |     0.032     |    -0.080     |     0.418     |   3    |

Jwalin Bhatt, Table of n, a(n) for n = 1..10000
Wikipedia, Borel distribution

Cf. A386009, A386016.

samplePDF[n_]:=Module[{coeffs, unreachedVal, counts, k, probCountDiffs, mostProbable},
  coeffs=ConstantArray[0, n]; unreachedVal=1; counts=<||>;
  Do[probCountDiffs=Table[probCountDiff[i, k, counts], {i, 1, unreachedVal}];
    mostProbable=First@FirstPosition[probCountDiffs, Max[probCountDiffs]];
    If[mostProbable==unreachedVal, unreachedVal++]; coeffs[[k]]=mostProbable;
    counts[mostProbable]=Lookup[counts, mostProbable, 0]+1; , {k, 1, n}]; coeffs]
A386904=samplePDF[120]

cp's OEIS Frontend

A386016 A sequence constructed by greedily sampling the Borel distribution for parameter value 1/2 to minimize ratio discrepancy.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica