Long Binary Blocks in Uniformly Random Sequences

Definitions and mathematical statement

Let $N\in{\mathbb{N}}$ with $N\geq 1$, and let $X^{(N)}=(X_1,\ldots,X_N)$ be uniformly distributed on $\{0,1\}^N$; thus \[ \mathbb P\left(X^{(N)}=x\right)=2^{-N}\qquad(x\in\{0,1\}^N). \] Under the convention that a block occurrence is a contiguous occurrence contained entirely within the sampled sequence, define, for integers $1\leq k\leq N$ and words $w=(w_1,\ldots,w_k)\in\{0,1\}^k$, \[ C_{N,k}(w)=\#\left\{i\in\{1,\ldots,N-k+1\}:(X_i,\ldots,X_{i+k-1})=w\right\}. \] This convention permits overlapping occurrences and does not identify the two ends of the sequence. It is an explicit framework for interpreting the question; these occurrence conventions are not specified in the supplied source.

Source question. What can be said about the occurrence of binary blocks whose length $k$ is larger than $\log N$ in a uniformly sampled binary sequence of length $N$? In the framework above, this asks for information about block occurrence counts $C_{N,k}(w)$, or occurrence events derived from them, in the stated length regime.

Unresolved qualifications. The source does not specify the logarithm base. For a specified base $b>1$, the length condition would read $k>\log_b N$, but no particular $b$ is selected here. The source also does not specify whether a word is fixed in advance, varies with $N$, or is quantified over all words; whether the target concerns occurrence probabilities, counts, repeated blocks, or simultaneous coverage; or whether a finite-sample bound, limiting distribution, or other asymptotic characterization is sought. If an asymptotic interpretation is intended, the growth conditions on $k=k(N)$, beyond the stated logarithmic inequality, remain unspecified. Thus the supplied question is a research direction rather than a uniquely determined proposition. The displayed definitions do not resolve these missing choices.

Short English statement

The problem asks about the occurrence of binary words longer than $\log N$ in a uniformly random binary string of length $N$. Contiguous occurrence counts provide a possible precise framework, but the logarithm base, occurrence conventions, word quantifiers, and desired probabilistic or asymptotic conclusion remain unspecified. This is a statement-only draft requiring human mathematical review.

Sources

• Local registry: data/unsolvedmath/problems.json, supplied record for permanent UnsolvedMath ID $30004672$, titled "Long Binary Blocks in Uniformly Random Sequences," exact source problem code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2021.
• Supplied report citation: Computability Theory (2022), Oberwolfach Reports, DOI 10.4171/owr/2021/21, pp. 1149--1190. https://doi.org/10.4171/owr/2021/21. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2022 designation and its 2021 report identifier are retained without resolving their relationship.
• Supplied literature source: "Oberwolfach Report 21/2021." https://ems.press/content/serial-article-files/46899.
• Supplied literature source: Álvarez, Becher and Mereb, Poisson generic sequences. https://doi.org/10.1093/imrn/rnac234.
• Supplied literature source: Álvarez et al., Poisson genericity in numeration systems. https://arxiv.org/abs/2411.04116.
• Supplied literature assessment, checked 2026-08-22: the record labels the problem "partially solved" and states that Poisson genericity describes the logarithmic critical regime, with computable examples and metric results, while no general characterization of all block lengths larger than logarithmic size is established. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. The status and cited claims require independent verification.