Sampling with and without replacement comparison for bounded products
ID: sampling-with-and-without-replacement-comparison-for-bounded-products
For arrays of values in , let average a product of entries over all ordered index tuples from coordinates, and let average it over the tuples with distinct indices. Decompose the first average as , where and the repeated-index average lies in . This gives . For uniformly sampled indices, a union bound over the pairs bounds the collision probability by . This deterministic estimate is the bridge between empirical-product limits and the De Finetti theorem.
New to topics? Read the docs here!