随机算法 (Fall 2011)/Problem set 4: Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone |
||
| Line 1: | Line 1: | ||
== Problem 1== | == Problem 1== | ||
Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. | Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. | ||
* Give an explicit construction of a coupling <math> | * Give an explicit construction of a coupling <math>\mu</math> of <math>p</math> and <math>q</math> such that <math>\Pr_{(X,Y)\sim\mu}[X\neq Y]=\|p-q\|_{TV}</math>. | ||
Revision as of 06:35, 28 November 2011
Problem 1
Let [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] be two probability distributions over [math]\displaystyle{ \Omega }[/math].
- Give an explicit construction of a coupling [math]\displaystyle{ \mu }[/math] of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] such that [math]\displaystyle{ \Pr_{(X,Y)\sim\mu}[X\neq Y]=\|p-q\|_{TV} }[/math].