随机算法 (Fall 2011)/Problem set 4: Difference between revisions

From TCS Wiki
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>\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>.
* 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].