Testing Closeness of Discrete Distributions

DOI10.1145/2432622.2432626zbMath1281.68227arXiv1009.5397OpenAlexW1928812145MaRDI QIDQ5395704

Tuğkan Batu, Ronitt Rubinfeld, Warren D. Smith, Patrick White, Lance J. Fortnow

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

statistical distancetesting properties of distributionstesting Markov chains for mixing

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (29)

Sampling Correctors ⋮ Unnamed Item ⋮ Analysis of COVID-19 evolution based on testing closeness of sequential data ⋮ Optimal Identity Testing with High Probability ⋮ Unnamed Item ⋮ A lower bound on the complexity of testing grained distributions ⋮ A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs ⋮ Normal approximation and fourth moment theorems for monochromatic triangles ⋮ Statistical Fault Attacks on Nonce-Based Authenticated Encryption Schemes ⋮ Unnamed Item ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ Erasure-Resilient Property Testing ⋮ Empirical Distribution of Equilibrium Play and Its Testing Application ⋮ Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs ⋮ On the power of conditional samples in distribution testing ⋮ Recovering Structured Probability Matrices ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Quantum spectrum testing ⋮ Unnamed Item ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Unnamed Item ⋮ Two Party Distribution Testing: Communication and Security ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Monochromatic subgraphs in randomly colored graphons ⋮ Optimal Stopping Rules for Sequential Hypothesis Testing ⋮ Mixing time estimation in reversible Markov chains from a single sample path ⋮ Communication Complexity of Statistical Distance ⋮ Testing Probability Distributions using Conditional Samples ⋮ On the consistency of the crossmatch test

This page was built for publication: Testing Closeness of Discrete Distributions