key: cord-0553037-utfp4xk2
authors: Finch, Steven
title: Cantor-solus and Cantor-multus Distributions
date: 2020-03-20
journal: nan
DOI: nan
sha: 40f87305e38ba9c62bf8860d754d61c3b0b13b29
doc_id: 553037
cord_uid: utfp4xk2

The Cantor distribution is obtained from bitstrings; the Cantor-solus distribution (a new name) admits only strings without adjacent 1 bits. We review moments and order statistics associated with these. The Cantor-multus distribution is introduced -- which instead admits only strings without isolated 1 bits -- and more complicated formulas emerge.

A bitstring is solus if all of its 1s are isolated. Such strings were called Fibonacci words (more fully, words obeying the Fibonacci restriction) in [1] . We shall reserve the name Fibonacci for a different purpose, as in [2, 3] .

A bitstring is multus if each of its 1s possess at least one neighboring 1. Such strings were called good sequences in [4] . Counts of solus n-bitstrings have a quadratic character, whereas counts of multus n-bitstrings have a cubic character. More on the meaning of this and on other related combinatorics will appear later.

Let 0 < ϑ ≤ 1/2; for instance, we could take ϑ = 1/3 as in the classical case. Let ϑ = 1 − ϑ. Consider a mapping [5] F (ω 1 ω 2 ω 3 · · · ω m ) =θ ϑ m i=1 ω i ϑ i from the set Ω of finite bitstrings (m < ∞) to the nonnegative reals. The 2 m bitstrings in Ω of length m are assumed to be equiprobable. Consider the generating function [1] G n (z) = ω∈Ω F (ω) n z |ω| where |ω| denotes the length of the bitstring. Clearly

is the n th Cantor moment for strings of length m; let µ n denote the limit of this as m → ∞. Denote the empty string by ε. From values

and employing the recurrence [6] 

as n → ∞. We merely mention a problem involving order statistics. Let ξ n denote the expected value of the minimum of n independent Cantor-distributed random variables. It is known that [12] 

In the special case ϑ = 1/3, it follows that

and, up to small periodic fluctuations [13] ,

as n → ∞. If η n denotes the expected value of the maximum of n variables, then 1 − η n ∼ c n − ln(3)/ ln (2) by symmetry. A final problem concerns the sum of all moments of the classical Cantor distribution [14] :

answering a question asked in [15] .

We examine here the set Ω of finite solus bitstrings (m < ∞). Let

denote the Fibonacci numbers. The f m+2 bitstrings in Ω of length m are assumed to be equiprobable. Clearly

and employing the recurrence [6]

The purpose of using multinomial coefficients here, rather than binomial coefficients as in Section 1, is simply to establish precedent for Section 3. Let ϕ = (1 + √ 5)/2 = 1.6180339887... be the Golden mean. Dividing both sides by G 0 (z), we have [1] 

and the singularity z 0 = 1/ϕ of G n (z) is a simple pole. In particular, when ϑ = 1/3,

and, up to small periodic fluctuations,

as n → ∞. An integral formula in [1] for the preceding numerical coefficient involves a generating function of exponential type:

(we believe that the fifth decimal given in [1] is incorrect, perhaps a typo). Unlike the formula for C earlier, this expression depends on the sequence µ 1 , µ 2 , µ 3 , . . . explicitly.

With regard to order statistics, it is known that [16] 

In the special case ϑ = 1/3, we have, up to small periodic fluctuations,

as n → ∞.

We examine here the set Ω of finite multus bitstrings (m < ∞). Let

denote the second upper Fibonacci numbers [17] . The f m+2 bitstrings in Ω of length m are assumed to be equiprobable. Clearly

F (11ω) =θ +θϑ + ϑ 2 F (ω),

and employing the recurrence

be the second upper Golden mean [17, 18] . Dividing both sides by G 0 (z), we have

and the singularity z 0 = 1/ψ of G n (z) is a simple pole. In particular, when ϑ = 1/3, 

We turn to a more fundamental topic: 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. Let us impose constraints. If Ω consists of solus bitstrings, then the total bitsum a n of all ω ∈ Ω of length n has generating function [19, 20] ∞ n=0 a n z n = z (1 − z − z 2 ) 2 = z + 2z 2 + 5z 3 + 10z 4 + 20z 5 + · · · and the total bitsum squared b n has generating function

where f n is as in Section 2. Standard techniques [6] give asymptotics

for the average density of 1s in a random solus string and corresponding variance. If instead Ω consists of multus bitstrings, then the total bitsum a n of all ω ∈ Ω of length n has generating function [21] ∞ n=0 a n z n = z 2 (2 − z) (1 − 2z + z 2 − z 3 ) 2 = 2z 2 + 7z 3 + 16z 4 + 34z 5 + · · · and the total bitsum squared b n has generating function

hence c n = f n+2 b n − a 2 n has generating function

where f n is as in Section 3. We obtain asymptotics lim n→∞ E(S n ) n = lim n→∞ a n nf n+2 for the average density of 1s in a random multus string and corresponding variance. Unsurprisingly 0.588 > 1/2 > 0.276 and 0.281 > 1/4 > 0.089; a clumping of 1s forces a higher density than a separating of 1s.

A famous example of an infinite aperiodic solus bitstring is the Fibonacci word [2, 3] , which is the limit obtained recursively starting with 0 and satisfying substitution rules 0 → 01, 1 → 0. The density of 1s in this word is 1 − 1/ϕ ≈ 0.382 [22] , which exceeds the average 0.276 but falls well within the one-sigma upper limit 0.276 + √ 0.089 = 0.575. We wonder if an analogously simple construction might give an infinite aperiodic multus bitstring with known density.

We turn to a different topic: 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? If Ω is unconstrained, then [6] E(R n,1 ) =

the Taylor expansion of the numerator series is [23] 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 [24, 25] , (2) as n → ∞. Of course, identical results hold for R n,0 , the duration of the longest run of 0s in ω.

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

and the Taylor expansion of the numerator series is [23] z + 4z 2 + 9z 3 + 18z 4 + 34z 5 + 62z 6 + 110z 7 + 192z 8 + 331z 9 + 565z 10 + · · · where f n is as in Section 2.

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

num = 2z 2 + 7z 3 + 16z 4 + 32z 5 + 62z 6 + 118z 7 + 221z 8 + 409z 9 + 751z 10 + · · · and 0-runs:

num = z + 2z 2 + 5z 3 + 11z 4 + 23z 5 + 45z 6 + 87z 7 + 165z 8 + 309z 9 + 573z 10 + · · · where f n is as in Section 3. Proof: the number of multus bitstrings with no runs of k 1s has generating function [26] 1 + z 2 − z k−1 − z k 1 − 2z + z 2 − z 3 + z k+1 z if k > 1; z 1 − z if k = 1;

we conclude by use of the summation identity

Study of runs of k 0s proceeds analogously [27] . The solus and multus results here are new, as far as is known. Asymptotics would be good to see someday.

6. Acknowledgements I am thankful to Alois Heinz for helpful discussions and for providing the generating function associated with 4, 19, 66, 236, . . . via the Maple gfun package; R and Mathematica have been useful throughout. I am also indebted to a friend, who wishes to remain anonymous, for giving encouragement and support (in these dark days of the novel coronavirus outbreak).

The Cantor-Fibonacci distribution, Applications of Fibonacci Numbers

Mathematical Constants

Substitution dynamics, Mathematical Constants II

Binary sequences without isolated ones, Fibonacci Quart

The moments of the Cantor distribution

Introduction to the Analysis of Algorithms

Calculation of moments for a Cantor-Vitali function

Potential theory and analytic properties of a Cantor set

The Cantor function

Asymptotics for the moments of singular distributions

Asymptotic analysis of the moments of the Cantor distribution

Moments of order statistics of the Cantor distribution

Explicit and asymptotic formulae for the expected values of the order statistics of the Cantor distribution

On Cantor's singular moments

Cantor's singular moments

Order statistics for the Cantor-Fibonacci distribution

A new generalization of the golden ratio, Fibonacci Quart

Feller's coin tossing constants, Mathematical Constants

On-Line Encyclopedia of Integer Sequences, A000045, A001629 and A224227

Binomial coefficients and Fibonacci and Lucas numbers, Fibonacci Quart

On-Line Encyclopedia of Integer Sequences, A005251, A259966 and A332863

Infinite self-similar words

On-Line Encyclopedia of Integer Sequences, A119706, A333394, A333395 and A333396

Losing runs in Bernoulli trials

The longest run of heads

On-Line Encyclopedia of Integer Sequences, A000930, A006498, A000570, A079816, A189593 and A189600

On-Line Encyclopedia of Integer Sequences, A000931, A003410 and A179070