Estimating Error in Natural Distribution Estimation

Balasundaram, Haricharan; Thangaraj, Andrew

Permalink

https://hdl.handle.net/2142/130303 Copy

Description

Title

Estimating Error in Natural Distribution Estimation

Author(s)

• Balasundaram, Haricharan
• Thangaraj, Andrew

Issue Date

2025-09-17

Keyword(s)

• Distribution estimation
• Missing mass
• Good-Turing estimator
• Concentration
• Estimation

Abstract

Given i.i.d. samples from an unknown discrete distribution, the goal of distribution estimation is to construct an accurate estimate of the underlying distribution. Natural distribution estimators assign one probability estimate to all letters occurring with the same frequency, and this is well-justified for i.i.d. models. However, natural estimators can be significantly erroneous for low frequency or missing (frequency 0) letters in large alphabet scenarios. In this work, we introduce a statistic that captures the unavoidable error at a particular frequency of any natural distribution estimator. For this proposed error statistic, which depends on the distribution and the samples, we provide an estimator that is non-linear in the prevalences (frequencies of frequencies). We show that the proposed estimator has low bias and is consistent, and can be used to ascertain if the distribution restricted to letters of the same frequency is close to uniform. Our approach is validated through simulations on synthetic and natural language data.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130303&&

Copyright and License Information

Copyright 2025 is held by Haricharan Balasundaram and Andrew Thangaraj.

Owning Collections