PaperlayerView exact revision on arXiv

Source-linked AI summary

Recursive overlap Bernoulli distributions and an entropy concavity conjecture

Jörg Neunhäuserer

arXiv:2609.05546v2cs.ITmath.DSmath.IT

TL;DR

The paper asks whether the Shannon entropy of recursively generated distributions is concave across all allowed overlap sequences. It constructs the distributions using left and right embeddings, proves concavity in two extremal cases, and reports no proof for other increasing infinite sequences.

  • Problem

    The paper poses whether the entropy is concave for every strictly increasing sequence, noting that a positive answer would imply concavity of the associated dimension function.

    Source: §1 · p. 2, §3 · p. 3

  • Method

    The paper recursively generates probability distributions by embedding each probability vector on the left and right according to a sequence that determines overlap.

    Source: §1 · p. 1

  • Results

    Concavity is proved for a_n=n+1 and for sequences with a_(n+1)≥2a_n, but no proof is given for other increasing infinite sequences.

    Source: §3 · p. 4

  • Takeaways & Limitations

    If the conjecture holds, the dimension function of the corresponding singular Bernoulli measures would be concave.

    Source: §1 · p. 2

    The conjecture remains unproved for increasing infinite sequences outside the cases covered by the proof.

    Source: §3 · p. 4

Abstract

from arXiv · show

We introduce a family of recursively generated finite probability distributions obtained from left and right embeddings with overlaps. The construction interpolates between the classical binomial distribution and the non-overlapping Bernoulli product distribution. We derive explicit formulas for the expectation, variance, and the generating function of higher moments, and formulate a conjecture asserting that the Shannon entropy is concave. The conjecture is proved in the two extremal cases and supported by symbolic computations for numerous overlap sequences.

1 Introduction

The paper recursively builds probability distributions by embedding each vector on the left and right, with a sequence controlling where the copies overlap. This construction interpolates between binomial distributions and separated Bernoulli convolutions.

1 Introduction

  • Each distribution starts from P1(p)=(p,1−p) and is recursively formed by left and right embeddings of the preceding probability vector.The embeddings place the vector at opposite ends of the next vector, with zeros elsewhere.Source: §1 · p. 1
  • When n+1<a_(n+1)<2a_n, the embedded copies overlap and produce distributions between the binomial and non-overlapping Bernoulli cases.Source: §1 · p. 2
  • The construction generalizes random walks on infinite rooted self-similar graphs and is closely related to convolved Bernoulli measures in fractal geometry.For the sequence a_(n+1)=a_n+a_(n−1)+1, it recovers the directed random walk on the Fibonacci graph.Source: §1 · p. 2
  • If the entropy conjecture holds, the dimension function of the corresponding singular Bernoulli measures would be concave.Source: §1 · p. 2

2 Expectation, variance and higher moments

This section derives expectation and variance results for the recursively defined random variables and gives a moment-generating-function formula for higher moments.

2 Expectation, variance and higher moments

  • The section establishes an expectation formula for X_n(p), whose proof follows from a telescoping sum.Source: §2 · pp. 2–3
  • The variance formula is proved by induction, with V(X_1)=p(1−p) as its base case.Source: §2 · p. 3
  • The moment generating function of X_n(p) is given by a product formula obtained by iterating the recursion.Source: §2 · p. 3

3 The entropy concavity conjecture

The section conjectures that entropy is concave for every allowed sequence and proves the claim in two extremal cases. It reports no proof for other increasing sequences.

3 The entropy concavity conjecture

  • For every strictly increasing sequence with a_1=2, the conjecture asserts that h_n is concave on [0,1] and therefore unimodal with a maximum at 1/2.Source: §3 · p. 3
  • Concavity is proved when a_n=n+1 and when a_(n+1)≥2a_n for all n, including the binomial and non-overlapping cases.The binomial case follows from the Shepp–Olkin theorem [3].Source: §3 · p. 4
  • The authors report no proof for other increasing infinite sequences, while noting computational evidence for many classes.Source: §3 · p. 4

4 Computational evidence

Computational tests found no counterexample to entropy concavity among the increasing overlap sequences tested. The experiments covered linear, polynomial, exponential, recursively defined, and stochastic sequences, with the tested sizes varying by sequence family.

Computational evidence

  • No tested increasing overlap sequence produced a counterexample, and stochastic tests suggest any counterexample may require larger n or more irregular overlaps.The stochastic sequences were tested up to n=100, with increments chosen uniformly from 1 to 1000.Source: §4 · pp. 4, 6
  • Linear sequences were tested up to n=200, with h_n and h′′_n displayed for n=10, 50, and 100 when a_n=2n.The computations used a Mathematica program available from the author.Source: §4 · p. 4, Figure 1 · p. 5
  • The first and second cases were considered up to n = 100 and n = 50, respectively; h_n and h′′_n are shown for n = 10, 50, and 100 when a_n = n^2 + 1.Source: §4 · p. 4, Figure 2 · p. 5
  • The exponential sequence a_n=⌈(3/2)^n⌉ and recurrence a_(n+1)=a_n+a_(n−1)+1 were tested up to n=30; the recurrence case is plotted for n=10, 15, and 20.Source: §4 · p. 4, Figure 3 · p. 5
Loading 2609.05546v2…