Smallest covering regions and highest density regions for discrete distributions

DOI10.1007/S00180-021-01172-6zbMATH Open1505.62305arXiv2211.02203OpenAlexW4226352668MaRDI QIDQ2155016FDOQ2155016

Ben O'Neill

Publication date: 15 July 2022

Published in: Computational Statistics (Search for Journal in Brave)

Abstract: This paper examines the problem of computing a canonical smallest covering region for an arbitrary discrete probability distribution. This optimisation problem is similar to the classical 0-1 knapsack problem, but it involves optimisation over a set that may be countably infinite, raising a computational challenge that makes the problem non-trivial. To solve the problem we present theorems giving useful conditions for an optimising region and we develop an iterative one-at-a-time computational method to compute a canonical smallest covering region. We show how this can be programmed in pseudo-code and we examine the performance of our method. We compare this algorithm with other algorithms available in statistical computation packages to compute HDRs. We find that our method is the only one that accurately computes HDRs for arbitrary discrete distributions.

Full work available at URL: https://arxiv.org/abs/2211.02203

zbMATH Keywords

computationdiscrete distribution0-1 knapsack problemhighest density conditionsmallest covering region

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Density estimation (62G07) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bandwidth selection for kernel density estimators of multivariate level sets and highest density regions
• On nonparametric estimation of density level sets
• Optimal rates for plug-in estimators of density level sets
• Asymptotics and optimal bandwidth selection for highest density region estimation
• Distribution-Free Prediction Sets
• Measuring mass concentrations and estimating density contour clusters -- An excess mass approach
• Estimation of a Convex Density Contour in Two Dimensions
• Convergence rates in nonparametric estimation of level sets
• The Highest Confidence Density Region and Its Usage for Joint Inferences about Constrained Parameters
• Where are the hard knapsack problems?
• Discrete associated kernels method and extensions
• New trends in exact algorithms for the \(0-1\) knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A kernel estimator for discrete distributions
• Improved interval estimation of long run response from a dynamic linear model: a highest density region approach
• Kernel methods for the estimation of discrete distributions
• Novel binary differential evolution algorithm for knapsack problems
• On finite sample properties of nonparametric discrete asymmetric kernel estimators
• Kernel smoothed probability mass functions for ordered datatypes

Cited In (1)

• A generalised matching distribution for the problem of coincidences

Uses Software

• mclust
• R
• hdrcde
• HDInterval
• stat.extend
• pdqr

This page was built for publication: Smallest covering regions and highest density regions for discrete distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155016)