TL;DR
This paper introduces a novel estimator for the regularity index ($\beta$) of discrete heavy-tailed distributions, commonly known as generalized Zipf’s laws. Unlike traditional methods that fail due to "ties" in discrete data, this approach uses exponentially separated tail events to provide a robust, consistent, and asymptotically normal estimator that extends effectively to non-stationary, null-recurrent Markov chains.
What Problem Does This Paper Address?
Heavy-tailed distributions are everywhere—from word frequencies in linguistics to rank-size distributions in social sciences. In the continuous case, we often use the Hill estimator to find the "tail index" (how fast the probability of extreme events decays). However, the Hill estimator relies on order statistics and the spacing between values.
When data is discrete (integers), many observations take the same value, leading to "ties." These ties result in zero-length spacings, causing traditional estimators to behave erratically or fail entirely. Furthermore, the paper tackles the even harder problem of null-recurrent Markov chains. These are systems that are guaranteed to return to a starting state but have an infinite expected return time. Because they are non-stationary and do not "mix" well, standard statistical inference tools often break down.
Methods
The authors propose a "plug-in" estimator $\hat{\beta}_n(k)$ that avoids order statistics entirely. Instead, it focuses on the survivor function—the probability $P(S > n)$.
- Exponential Thresholding: The estimator looks at the probability of the random variable exceeding thresholds that grow exponentially, specifically $e^k$ and $e^{k+1}$.
-
The Formula: The estimator is defined as: $$\hat{\beta}_n(k) = \ln(\hat{p}_k^{(n)}) - \ln(\hat{p}_{k+1}^{(n)})$$ where $\hat{p}_k^{(n)}$ is the empirical proportion of data points exceeding $e^k$.
-
Markovian Extension: For regenerative Markov chains, the authors treat the durations between visits to a specific state (an "atom") as the discrete random variables. Even though these durations are technically dependent on the total observation time, the authors prove that the estimator remains consistent.
- Averaging: They also introduce an "averaged" version of the estimator to reduce variance, though they note this comes at the cost of increased asymptotic variance.
Datasets
The paper relies on sophisticated synthetic simulations to validate the theory:
- Zeta Distributions: A standard discrete power-law distribution used to compare the new estimator against the Hill estimator.
- Bessel Random Walks: Used to simulate $\beta$-null-recurrent Markov chains with varying drift parameters.
- Split Chain Construction: A technique used to test the estimator on "pseudo-regenerative" chains (where a clear starting "atom" state isn't naturally present) by artificially constructing a regenerative extension.
Key Insights and Ideas
- Thresholds over Order Statistics: By fixing thresholds ($e^k$) rather than using the $k$-th largest value, the method becomes immune to the "ties" that plague discrete data.
- Bias-Variance Tradeoff: The choice of the hyperparameter $k$ is critical. A small $k$ leads to high bias (because you aren't far enough into the "tail"), while a large $k$ leads to high variance (because fewer data points exceed the threshold). The authors suggest $k \approx \ln(n)$ as a heuristic.
- Inference for the "Un-mixable": The extension to null-recurrent chains is significant because these processes violate the "mixing" assumptions required for most frequentist statistics. This paper provides a rare bridge for performing inference on such unstable systems.
Key Results
- Consistency and Normality: The authors provide rigorous proofs that the estimator is strongly consistent (converges to the true value) and asymptotically normal under mild conditions.
- Superiority over Hill: In simulations with $10^6$ realizations of a Zeta distribution ($\beta=0.8$), the new estimator showed a stable plateau around the true value, whereas the Hill estimator fluctuated wildly and failed to provide a clear estimate (see Fig 1 in the paper).
- Markov Chain Performance: In Bessel random walk simulations, the estimator's bias and variance decreased significantly as the sample path length $n$ increased from $10^3$ to $10^7$, outperforming both the Hill estimator and simple log-log plot regressions.
Limitations and Future Work
- Hyperparameter Selection: While the paper establishes the theory for $k$, choosing the "optimal" $k$ in practice remains somewhat of an art, similar to choosing the number of order statistics in a Hill plot.
- Unknown Transition Kernels: The extension to general (non-atomic) Harris chains requires estimating the transition density. The authors note that in the null-recurrent case, the only known consistent estimator for this is the Nadaraya–Watson estimator, which has its own difficult bandwidth selection issues.
- Convergence Rates: While consistency is proven for the Markovian case, the authors acknowledge they haven't yet established a formal rate of convergence for these dependent sequences, leaving this as an open research path.
Summary updated