OFFSET
0,3
COMMENTS
Given n random numbers distributed uniformly in [0,1], and a list of n places to put them, P(n) = A370448(n)/A370449(n) describes the probability that one is able to sort them directly in order with the following procedure:
Take the first number. Without knowledge about the following numbers, place the number in the list such that the list is ordered (without moving any other number). Repeat until this is not possible anymore (i.e. because the new number would need to be inserted between two previously placed numbers directly next to each other on the list). If there are multiple valid spaces for placing the number in the list, the space is chosen that maximizes the total success probability. These probabilities are rational.
LINKS
Philip Geißler, Table of n, a(n) for n = 0..6
Reddit, User: Sarah_Carrygun, Original derivation of the success probability with perfect strategy.
FORMULA
EXAMPLE
For n=2, one has two options to place the first number in the list of 2 spaces.
If the first random number r_1 is >0.5, one should place it on the right space (assuming an ascending list) because it maximizes the probability that the next number r_2 can still be placed in the list.
Without knowledge of r_2: P(r_2 can be placed after r_1 is placed on the right space) = P(r_2<r_1) = r_1.
Equivalently, if r_1 is <0.5, one should place it on the left space.
Without knowledge of r_2: P(r_2 can be placed after r_1 is placed on the left space) = P(r_2>r_1) = 1-r_1.
Thus, P(r_2 can be placed after r_1 is placed optimally) = max(r_1, 1-r_1).
For the total probability {P(n)}(2) that both numbers can be placed such that they are ordered, the above expression needs to be integrated over r_1:
This means that A370448(2) = 3.
PROG
(Python)
import sympy, functools
from numpy.lib.stride_tricks import sliding_window_view as rolling
binomial_sym_sympy = lambda L, R : sympy.functions.combinatorial.factorials.binomial(L+R, L)
@functools.cache
def C_analytic(L, R):
return binomial_sym_sympy(L, R) * P_analytic(L) * P_analytic(R)
@functools.cache
def P_analytic(n):
_zero, _one, _x = sympy.core.numbers.Zero(), sympy.core.numbers.One(), sympy.symbols("x")
if n == 0: return _one
# provide analytic expressions for the functions to integrate and the bounds of them
int_bounds = [_zero, *[1/(1 + C_analytic(L+1, n-L-2)/C_analytic(L, n-L-1)) for L in range(n-1)], _one]
int_polys = [sympy.poly(C_analytic(L, n-1-L) * _x**L * (1-_x)**(n-1-L), _x, domain="Q").integrate() for L in range(n)]
int_summands = [int_poly(R_bound)-int_poly(L_bound) for int_poly, (L_bound, R_bound) in zip(int_polys, rolling(int_bounds, 2))]
return sum(int_summands)
def A370448(n): return P_analytic(n).numerator
CROSSREFS
KEYWORD
frac,nonn
AUTHOR
Philip Geißler, Feb 18 2024
STATUS
approved