随机算法 (Fall 2011)/Problem set 4

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].