A370449 Denominator of probability to directly sort n uniform random values in [0,1] with perfect strategy.

1, 1, 4, 726, 3020778029791104, 1356952251391926002664799322274919178558749179143258568252348272194427343469119954161606283821760

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

P(0) = 1

P(n+1) = Integral_{x=0..1} max_{L=0..n} C_{L,n-L} x^L (1-x)^{n-L} dx

C_{L,R} = (L+R)!/(L!R!) a(L) a(R)

where P(n) = A370448(n)/A370449(n)

and C(L,R) = A370450(L,R)/A370451(L,R)

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:
{P(n)}(2) = Integral_{x=0..1} max(x, 1-x) dx = 3/4 = A370448(2)/A370449(2).
This means that A370449(2) = 4.

Prog

(Python) # uses P_analytic(n) from A370448.
def A370449(n): return P_analytic(n).denominator

Crossrefs

Cf. A370448 (numerators).

Cf. A370450, A370451.

Sequence in context: A307920 A159618 A219012 * A364632 A059754 A134579

Adjacent sequences: A370446 A370447 A370448 * A370450 A370451 A370452

Keyword

frac,nonn

Author

Philip Geißler, Feb 18 2024

Status

approved