A universal upper bound for pair discrepancy
A universal upper bound for pair discrepancy
Let denote the total variation discrepancy between the color distributions of a pair selected by the two matching procedures, and define
where the supremum ranges over all probability distributions on a finite or countable set of colors. Universal discrepancy bound. The constant satisfies
Since total variation distance is at most , this conjecture asks for a nontrivial universal bound on the discrepancy; the paper does not establish it.
Sources & referencesView supporting material
Primary source
Richard Arratia and Stephen DeSalvo, “On the Random Sampling of Pairs, with Pedestrian examples”, arXiv:1211.6486 (2013).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.