key: cord-0597786-286xdc7y
authors: Finch, Steven
title: Variance of Longest Run Duration in a Random Bitstring
date: 2020-05-25
journal: nan
DOI: nan
sha: 98d5b01cfcb1214d2fea75cab7796ea168a92d69
doc_id: 597786
cord_uid: 286xdc7y

We continue an earlier study, starting with unconstrained $n$-bitstrings, focusing now less on average behavior and more on uncertainty. The interplay between $bullet$ longest runs of 0s and of 1s, when bitstrings are multus $bullet$ longest runs of 0s and bitsums (# of 1s), when bitstrings are solus is examined. While negative correlations approach zero as $n rightarrow infty$ in the former (for clumped 1s), the limit is evidently nonzero in the latter (for separated 1s). Similar analysis is possible when both 0s and 1s are clumped (bimultus), and when 0s are clumped but 1s are separated (persolus). Our methods are experimentally-based.

What can be said about the statistics of the duration R n,1 of the longest run of 1s in a random bitstring of length n? Each of the 2 n possible bitstrings are assumed to be equally likely; we call this the unconstrained case for reasons that will become clear later. The two summation identities

give rise to generating functions for the mean and mean square:

The expression for E(R n,1 ) appears in [1] ; although a reference for E(R 2 n,1 ) is not known, our expression surely is not new. The Taylor expansion of the numerator series for E(R n,1 ) is [2] z + 4z 2 + 11z 3 + 27z 4 + 62z 5 + 138z 6 + 300z 7 + 643z 8 + 1363z 9 + 2866z 10 + · · · and, up to small periodic fluctuations [3, 4, 5] , (2) as n → ∞. The Taylor expansion of the numerator series for E(R 2 n,1 ) is z + 6z 2 + 21z 3 + 61z 4 + 158z 5 + 386z 6 + 902z 7 + 2051z 8 + 4565z 9 + 10006z 10 + and the variance satisfies V(R n,1 ) ∼ 1 12 + π 2 6 ln(2) 2 = 3.5070480758... again up to small periodic fluctuations. This constant is fairly ubiquitous, cf. [6, 7] . Of course, identical results hold for R n,0 , the duration of the longest run of 0s in a bitstring.

We examine four constrained cases in this paper. Let Ω be a set of finite bitstrings. Rather than exhibit complicated series

for each choice of Ω, we instead simply provide the denominator d n = the count of all ω ∈ Ω of length n as well as the generating function H k (z) for the count of all ω ∈ Ω with no runs of k 1s (or k 0s, depending on the scenario). A nonzero correction term G(z) is often required too. For the preceding, clearly d n = 2 n , G(z) = 0 and

For E(R 3 n,1 ) and E(R 4 n,1 ), the factor 2k − 1 in the E(R 2 n,1 ) formula would be replaced by 3k 2 − 3k + 1 and 4k 3 − 6k 2 + 4k − 1 respectively.

The first two examples of constrained bitstrings were introduced in [8] .

• A bitstring is solus if all of its 1s are isolated.

• A bitstring is multus if each of its 1s possess at least one neighboring 1.

Counts of solus n-bitstrings have a quadratic character:

whereas counts of multus n-bitstrings have a cubic character:

The remaining two examples are new, as far as is known.

• A bitstring is bimultus if each of its 1s possess at least one neighboring 1 and each of its 0s possess at least one neighboring 0. Both isolated 1 bits and isolated 0 bits are avoided in such bitstrings; a certain 0 ↔ 1 symmetry holds here.

• A bitstring is persolus if all of its 1s are isolated and each of its 0s possess at least one neighboring 0. That is, while 1s in solus bitstrings are alone, 1s in persolus bitstrings are very alone.

Counts of bimultus n-bitstrings have a quadratic character [9] ∞ n=0 d n z n = 2z 2 1 − z − z 2 = 2z 2 + 2z 3 + 4z 4 + 6z 5 + 10z 6 + 16z 7 + · · · , whereas counts of persolus n-bitstrings have a cubic character ∞ n=0 d n z n = z (1 + 2z 2 ) 1 − z − z 3 = z + z 2 + 3z 3 + 4z 4 + 5z 5 + 8z 6 + 12z 7 + · · · .

2. Bitsums Given a set Ω of finite bitstrings, what can be said about the bitsum S n of a random ω ∈ Ω of length n? If Ω is unconstrained, i.e., if all 2 n strings are included in the sample, then E(S n ) = n/2, V(S n ) = n/4 because a sum of n independent Bernoulli(1/2) variables is Binomial(n,1/2). Expressed differently, the average density of 1s in a random unconstrained string is 1/2, with a corresponding variance 1/4. We previously covered solus and multus bitstrings in [8] .

If Ω consists of bimultus bitstrings, then the total bitsum a n of all ω ∈ Ω of length n has generating function [9] ∞ n=0 a n z n =

and the total bitsum squared b n has generating function

Standard techniques [1] give asymptotics

for the average density of 1s in a random bimultus string and corresponding variance.

If Ω instead consists of persolus bitstrings, then the total bitsum a n of all ω ∈ Ω of length n has generating function ∞ n=0 a n z n =

and the total bitsum squared b n has generating function

We obtain asymptotics [8] . While insisting on 0 ↔ 1 symmetry forces equiprobability, it also increases the variance, but only slightly.

Given a set Ω of finite bitstrings, what can be said about the duration R n,1 of the longest run of 1s in a random ω ∈ Ω of length n? We have already discussed the case when Ω is unconstrained. Preliminary coverage for constrained Ω (for means, but not mean squares) occurred in [8] .

If Ω consists of solus bitstrings, then it makes little sense to talk about 1-runs. For 0-runs, over all ω ∈ Ω, we have

the Taylor expansion of the numerator series for E(R n,0 ) is z + 4z 2 + 9z 3 + 18z 4 + 34z 5 + 62z 6 + 110z 7 + 192z 8 + 331z 9 + 565z 10 + · · · and the Taylor expansion of the numerator series for E(R 2 n,0 ) is z + 6z 2 + 19z 3 + 48z 4 + 106z 5 + 218z 6 + 424z 7 + 798z 8 + 1463z 9 + 2631z 10 + · · · .

Let us abbreviate such series as num 1 0 and num 2 0 for simplicity -likewise num 1 1 and num 2 1 -and let ϕ = (1 + √ 5)/2 = 1.6180339887... denote the Golden mean. It is conjectured that, up to small periodic fluctuations,

If Ω consists of multus bitstrings, then we can talk both about 1-runs:

,

num 1 1 = 2z 2 + 7z 3 + 16z 4 + 32z 5 + 62z 6 + 118z 7 + 221z 8 + 409z 9 + 751z 10 + · · · num 2 1 = 4z 2 + 17z 3 + 46z 4 + 104z 5 + 220z 6 + 448z 7 + 889z 8 + 1729z 9 + 3313z 10 + · · · and 0-runs:

num 1 0 = z + 2z 2 + 5z 3 + 11z 4 + 23z 5 + 45z 6 + 87z 7 + 165z 8 + 309z 9 + 573z 10 + · · · , num 2 0 = z + 4z 2 + 11z 3 + 27z 4 + 63z 5 + 135z 6 + 281z 7 + 565z 8 + 1115z 9 + 2161z 10 + · · · . Letting ψ = 1 3

If Ω consists of bimultus strings, there is symmetry (just as for the unconstrained case). We have

,

num 1 0 = num 1 1 = 2z 2 + 3z 3 + 8z 4 + 15z 5 + 28z 6 + 50z 7 + 87z 8 + 150z 9 + 255z 10 + · · · , num 2 0 = num 2 1 = 4z 2 +9z 3 +24z 4 +51z 5 +102z 6 +196z 7 +361z 8 +656z 9 +1165z 10 +· · · . It is conjectured that, up to small periodic fluctuations,

V(R n,0 ) ∼ V(R n,1 ) ∼ 1 12 + π 2 6 ln(ϕ) 2 = 7.1868910445... as n → ∞. The same asymptotic variance occurred for solus bitstrings.

If Ω consists of persolus strings, then it makes little sense to talk about 1-runs. For 0-runs, we have

num 1 0 = 2z 2 + 7z 3 + 12z 4 + 18z 5 + 30z 6 + 49z 7 + 76z 8 + 118z 9 + 183z 10 + · · · , num 2 0 = 4z 2 + 17z 3 + 38z 4 + 70z 5 + 128z 6 + 227z 7 + 384z 8 + 636z 9 + 1037z 10 + · · · . Letting

V(R n,0 ) ∼ 1 12 + π 2 6 ln(θ) 2 = 11.3414222234... as n → ∞. The constants ϕ and ψ also appeared in [8] ; θ was called Moore's constant in [10] and is the limit of a certain fundamental iteration.

Let us return to the unconstrained case. Exhibiting E(R n,0 R n,1 ) in a manner parallel to old formulas in our introduction seems impossible: no analogous summation identity for ∞ i=0 ∞ j=0 i j · h i,j (z) apparently exists. Thus new formulas are somewhat less tidy, but nevertheless workable. The number of bitstrings with no runs of i 1s and no runs of j 0s has generating function

where d n = 2 n . The Taylor expansion of the numerator series for E(R n,0 R n,1 ) is 2z 2 + 10z 3 + 34z 4 + 96z 5 + 248z 6 + 604z 7 + 1418z 8 + 3240z 9 + 7260z 10 + · · · and the correlation coefficient

is prescribed numerically in Table 1 for n = 10, 20, . . . , 50. These results complement those in [11] . For multus bitstrings, since 1s are clumped (but 0s are not necessarily so), the associated generating function

is unsurprisingly asymmetric in i and j. The associated Taylor expansion is 4z 3 + 16z 4 + 45z 5 + 106z 6 + 232z 7 + 484z 8 + 977z 9 + 1927z 10 + · · · and, again, the corresponding ρ is prescribed in Table 1 . Correlations are all negative but approach zero as n increases. We observe a slightly stronger dependency between R n,0 and R n,1 for multus strings than for unconstrained strings. Calculating f i,j (z) for bimultus strings remains open. Simulation suggests that dependence is greater still for the bimultus case. Table 1 : Correlation ρ(R n,0 , R n,1 ) as a function of n.

Let us return to the solus case. Being isolated, each 1 acts as barrier to gathering 0s; we wonder to what extent the (random) number of such walls affects the largest crowd size. To calculate E(R n,0 S n ) seems to be difficult. The number of bitstrings with less than two 1s and no runs of k 0s has generating function f 2,k (z) = ∞ n=1 a n z n (a polynomial!) with a n = 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1} when k = 7.

The number of bitstrings with less than three 1s and no runs of k 0s has generating function f 3,k (z) with The number of bitstrings with less than four 1s and no runs of k 0s has generating function f 4,k (z) with a n =

δ k,n is 1 when k = n and is 0 otherwise. For example, An expression for f 5,k (z), the generating function corresponding to bitstrings with less than five 1s and no runs of k 0s, exists but awaits simplication. For example, when k = 7. For arbitrary k ≥ 2, clearly a n is equal to we obtain the Taylor expansion of the numerator series for E(R n,0 S n ): 2z 2 + 7z 3 + 18z 4 + 43z 5 + 94z 6 + 196z 7 + 392z 8 + 764z 9 + 1454z 10 + · · · (every exhibited coefficient is correct). We would need f 6,k (z), f 7,k (z), . . . to achieve the precision necessary to adequately estimate ρ(R n,0 , S n ) for large n. Simulation suggests that correlations are all negative but, unlike the previous section, tend to a nonzero quantity (possibly −1/2?) as n approaches infinity. We have not yet attempted to study the persolus case.

6. Acknowledgements R, Mathematica and Maple have been useful throughout. I am indebted to a friend, who wishes to remain anonymous, for giving encouragement and support (in these dark days of the COVID-19 pandemic). I also recogize the editors of the On-Line Encyclopedia of Integer Sequences for tireless & dedicated work.

Introduction to the Analysis of Algorithms

On-Line Encyclopedia of Integer Sequences, A119706 and A334833

Losing runs in Bernoulli trials

The longest run of heads

The longest run of heads

Resolving conflicts and electing leaders

The maximum of an asymmetric simple random walk with reflection

Cantor-solus and Cantor-multus distributions

On-Line Encyclopedia of Integer Sequences, A006355, A099920 and A179070

The Golden mean: Generalized continued fractions, Mathematical Constants

Longest success runs and Fibonacci-type polynomials, Fibonacci Quart