en
0.25
0.5
0.75
1.25
1.5
1.75
2
Competitive Closeness Testing
Published on Aug 02, 20113158 Views
We test whether two sequences are generated by the same distribution or by two diff erent ones. Unlike previous work, we make no assumptions on the distributions' support size. Additionally, we comp
Related categories
Chapter list
Competitive Closeness Testing00:00
Closeness Testing00:01
Related Problems and Applications00:36
Closeness Tests and their Error Probability01:15
Composite Hypothesis Testing and GLRT02:00
GLRT (continued)03:27
A Small Alphabet Example04:28
A Large Alphabet Example04:41
Example (continued)05:08
Known Results06:35
Patterns and Symmetric Tests08:28
Pattern Probabilities10:16
Joint Pattern Probabilities10:47
A Competitively Optimal Test11:19
Large Alphabet Example Revisited13:48
Skewed Patterns and Mixed Distributions (Detour)14:13
Large Alphabet Example Revisited14:15
Profiles of Patterns14:37
Joint Profiles15:32
Joint Profiles of a Given Length16:02
Likelihood of Rare Profiles16:29
Error probability of Δˆ P(Y)16:32
Error probability of Δˆ P(Y) . . .16:35
Towards a Computationally Efficient Test16:38
An Explicit Expression for N(φ)17:02
Case 2: (p1, p2) is (n, d)-different17:49
Sample Complexity17:52
Conclusions17:56
Ongoing Work18:21
Thank You18:48
A Test Based on N(φ) and its Error Analysis19:19