A386904 A sequence constructed by greedily sampling the Borel distribution for parameter value 1/2 to minimize discrepancy.
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
Examples
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 |
Links
- Jwalin Bhatt, Table of n, a(n) for n = 1..10000
- Wikipedia, Borel distribution
Programs
-
Mathematica
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]
Comments