Discrete Probability Distributions: Learn & Test with tools from Fourier Analysis
summary
Algorithm tests membership for sums of independent integer variables (an n-fold sum of k-ary integers) by exploiting DFT sparsity: estimate mean and variance from samples (demo uses initial sample size 100, n=10, k=4), fold the empirical PMF modulo m, compute FFT, collect an effective Fourier support via explicit i,j,zeta thresholds, then accept if the reconstructed L2 error < epsilon^2/5. Sample complexity depends on variance and scales like 1/epsilon^2; simulations show small effective support often but large outliers (e.g. k=8).
AI-written summary · about
chapters (14)
- 0:00Introduction to talk
- 1:32Motivation for distributions
- 4:00Distribution membership testing
- 6:46NKSI IRV explained
- 9:14Fourier transform basics
- 10:38Algorithm overview
- 13:27Variance and Fourier support
- 15:57Effective support computation
- 18:04Final decision step
- 19:50Simulation results
- 20:51Broader applications
- 21:53Open problems and scaling
- 22:55References and papers
- 23:37Q&A session
related talks
01h 05mDistribution Estimation and Applications III
23mTowards Practical Distribution Testing
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
45mTesting and Learning Distributions Under Local Information Constraints
30mStatistical Property Testing and Estimation Beyond the i.i.d. Setting
21mTesting Distribution Families
01h 23mAnalytic Methods for Supervised Learning I
01h 14mRecent Progress in High-Dimensional Learning