Stopping Time

Stopping Time Records

We define the `k^(th)` Stopping Time Class `G_k` as the set of integers whose Stopping Time is `k`:
`G_k={n in NN, sigma(n)=k}`

We note `g_k`the number of elements of `G_k`

As `sigma(n)=k`, we have:
`{(AA i lt k; F^((i))(n) gt n),(F^((k))(n) le n):}`
or:
`{(AA i lt k; u_i gt u_0),(u_k le u_0):}`

And if `o_k` is the number of odd steps during the `k` first steps:
`u_k~~u_0+o_k*ln(3)-k*ln(2)`
`o_k=ceil((k*ln(2))/ln(3))`
`AA i lt k; o_i gt i*ln(2)/ln(3)`

As each step can be either odd or even, there are `2^k` trajectories of `k` steps.

We can count the number `h_(k,o)` of admissible trajectories of `k` steps with `o` odd steps by:
`{(o ge k*ln(2)/ln(3) rArr h_(k,o)=0),(o lt k*ln(2)/ln(3) rArr h_(k,o)=h_(k-1,o)+h_(k-1,o-1)):}`

`G_k` contains elements which follow an admissible trajectory of `k` steps including `o_k` odd steps.
Such trajectories have a probability of `h_(k,o)/(2^k)`

The smallest element of `G_k` is an integer whose height can be estimated by:
`\stackrel{~}{u}_k=k*ln(2)-ln(h_(k,o))`
The Figure bellow represents this model and real Stopping Time Records.

Stopping Time Mean

For each class modulo `2^n`, the `n` first steps are completely defined, so we can count:
`g_(n,k)` the number of classes modulo `2^n` with a stopping time of `k`,
`g_(n,+)` the number of classes modulo `2^n` with a stopping time greater than `n`.

A first lower estimation for the mean of stopping time can be:
`bar sigma_n=(sum_k=0^n (k*g_(n,k)))/2^k`
but this estimation converges too slowly.

A number with a height of `u` and such that the stopping time is `k`, reaches the height `u-delta` just below `u`, after the `k` first steps, with:
`delta=k*ln(2)-floor((k*ln(2))/ln(3))*ln(3)`
A number with a height of `u` and such as the stopping time is unknown, reaches an height `u-delta` just below `u`, with:
`delta in [0, ln(2)[`

At the level `n`, the average value of `delta` is bounded by:
`bar delta(n) in [bar delta_min(n), bar delta_max(n)[`
`bar delta_min(n)=(sum_(k=0)^n(g_(n,k)*(k*ln(2)-floor((k*ln(2))/ln(3))*ln(3))))/2^n`
`bar delta_max(n)=(sum_(k=0)^n(g_(n,k)*(k*ln(2)-floor((k*ln(2))/ln(3))*ln(3)))+g_(n,+)*ln(2))/2^n`

`bar sigma` being the mean of stopping time and `bar delta` the average value of `delta` means that, after `bar sigma` steps the height is reduced by `bar delta`.

The mean of the total stopping time is the number of steps to reduce the height to `0`.
`bar (sigma_oo) = (bar sigma)/(bar delta)`

So we have the stopping time mean by:
`bar sigma=bar delta * bar (sigma_oo)`

We can compute a estimation as accurate as we want of the mean of the stopping time, counting `g_(n,k)` and `g_(n,+)` for increasing values of `n`. This is showed in Figure bellow.

For example, with n = 50, we have:
`3,486 le bar sigma le 3,502 `
and pursuing up to `n = 120`, we have:
`3,49244 le bar sigma le 3,49292 `