Quality Control Algorithms for Pattern Counting

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $Θ(k\log k)$. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires $Θ(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $Θ(k/\log k)$ characterization. For every integer $2\leα\le c_0\log k$, we prove the matching fixed-accuracy bound $Θ_{c_0}(αk^{1-1/α})$. Previous results gave $Ω_α(k^{1-1/α})$ for fixed integer $α>1$ and $O_{c_0}(α^2k^{1-1/α})$ for all integer $α>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $α$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $α$ is unavoidable. For every real $1.001\leα\le c_0\log k$, we prove the uniform lower bound $Ω_{c_0}(αk^{1-1/α})$. Finally, since $0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$, min-entropy uniformly approximates $H_α$ when $α$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $Θ_\varepsilon(k\log k)$ sample complexity in the high-order regime.