[lyncpmou] expected number of barriers passed

let barrier(n,h) be the probability of passing barrier number n, starting from n=1.  h is a parameter that will be used later.

to pass exactly n barriers, one needs to consecutively pass barriers 1 through n, then fail barrier n+1:

exactly(n,h)= prod(i=1,n, barrier(i,h)) * (1-barrier(n+1,h))

(Pari/GP syntax)

the expected number of barriers crossed before the first failure is an infinite sum.  here is the partial sum:

partialexpected(n,h)= sum(i=1,n, i*exactly(i,h))

first, let us investigate the barrier probability being a constant, not dependent on n:

barrier(n,h)= h

the expected number E of barriers crossed for constant barrier probability h:

h=1/6 E=1/5
h=1/5 E=1/4
h=1/4 E=1/3
h=1/3 E=1/2
h=2/5 E=2/3
h=1/2 E=1
h=3/5 E=3/2
h=2/3 E=2
h=3/4 E=3
h=4/5 E=4
h=5/6 E=5

the above exact values are conjectures from the partial sum, e.g.:

partialexpected(999,5.0/6)
4.9999999999999999999999999999999999940
cpu time = 107 ms, real time = 107 ms.

a closed-form formula for a given constant barrier probability is probably not difficult to derive, probably something like geometric series.

if the barrier probability is 1/n, the expected number of barriers crossed is e-1:

barrier(n,h)= 1.0/n
partialexpected(99)
1.7182818284590452353602874713526624977
partialexpected(98)
1.7182818284590452353602874713526624977

the second calculation of only 98 terms verifies convergence of the partial sum.  a barrier probability decreasing as a function of n is nice for making the partial sum converge quickly.

(in Pari/GP, if a function argument is omitted -- in this case h -- it is assigned a default value of 0.)

if the barrier probability is 1/(2*n), equivalently 0.5/n, then the expected value is exp(0.5)-1 (via the RIES Inverse Symbolic Calculator). (the original Inverse Symbolic Calculator has gone offline.)

barrier(n,h)= h/n
partialexpected(99,0.5)
0.64872127070012814684865078781416357161

we conjecture that the expected value for this form of barrier probability is exp(h)-1.  therefore, if h = log(2) ~= 0.693, the expected value is 1 :

partialexpected(99,log(2))
0.99999999999999999999999999999999999996

let the barrier probability decay exponentially:

barrier(n,h)= h^n

if the barrier probability is 1/2^n , then the expected value has the following value, unknown if it has a closed form:

partialexpected(99,0.5)
0.64163256065515386629384277022542943422

if h = 0.7 , the expected value is greater than 1 :

partialexpected(99,0.7)
1.1942513927487148419874371583834978589

we use Pari/GP's nifty solve function to find the value of h such that the expected value is exactly 1 .  does this value of h have a closed form expression?

h = solve(x=0.5,0.7, partialexpected(99,x)-1)
0.64522270323602097913425166394402633225
partialexpected(99,h)
0.99999999999999999999999999999999999996

recall that if the barrier probability is 1/n, the expected value is e-1 :

barrier(n,h)= 1.0/(n+h)
partialexpected(99,0)
1.7182818284590452353602874713526624977

the first barrier is passed with probability 1, not a barrier at all, a free +1 to the expected value.  if we shift all barriers by one, then the expected value is unsurprisingly e-2 :

partialexpected(99,1)
0.71828182845904523536028747135266249771

this is the amount of shift that makes the expected value 1 :

h= solve(x=0,1, partialexpected(99,x)-1)
0.53571808926964201274443895890553620494

let the barrier probability obey a power law.  we shift by 1 to skip the free first barrier:

barrier(n,h)= (n+1.0)^h

when the exponent is -1, the expected value is e-2 as noted before:

partialexpected(99,-1)
0.71828182845904523536028747135266249771

if the probability is 1/sqrt(n+1) , the expected value is greater than 1 :

partialexpected(99,-0.5)
1.4695063145210475624756367446601502576

this exponent makes the expected value 1 :

h= solve(x=-0.5,-1, partialexpected(99,x)-1) -0.73888040289770820386751815624320497895

inspired by modeling family sizes.  have children until you can't, perhaps because of death caused by complications from childbirth.

if sampling a random tree where the number of children of each node has expected value 1, the population stays approximately constant generation to generation (I think).  such a tree models asexual reproduction, or a filtered view of sexual reproduction paying attention to only one gender.