随机算法 (Fall 2011)/Problem set 4: Difference between revisions
Jump to navigation
Jump to search
imported>Etone Created page with "== Problem 1== Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. # Give an explicit construction of a coupling <math>(X,Y)</math> o…" |
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>(X,Y)</math> of <math>p</math> and <math>q</math> such that <math>\Pr[X\neq Y]=\|p-q\|_{TV}</math>. | |||
Revision as of 06:34, 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{ (X,Y) }[/math] of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] such that [math]\displaystyle{ \Pr[X\neq Y]=\|p-q\|_{TV} }[/math].