Tag Info

New answers tagged


$P(D(X_n, 1^n) = 1)$ means the probability that the following algorithm returns $1$: Sample $x$ according to $X_n$. Run $D(x, 1^n)$. Output whatever $D$ outputs. Say for example that $X_n$ is the uniform distribution on $\{1,2,3,4\}$, and $D(x,1^n)$ is the following: If $x$ is odd, output $x$ or $x+1$, each with probability $1/2$. If $x$ is even, ...

Top 50 recent answers are included