I am looking for a proof of this fact regarding randomized strategies of the CHSH game:

"... allowing randomized strategies can not help them to get a better success probability. This is because any classical randomized strategy for the CHSH game (where say Alice’s answer is a function of the question x, as well as some random string r that might be possibly shared with Bob, and similarly for Bob’s answer) can be converted into a deterministic strategy that has the same winning probability..."

More generally, how about other nonlocal games? How do you prove in general that the correlations arising from random strategies are linear combinations of correlations from deterministic strategies?


1 Answer 1


Any probability distribution can be considered as a convex mixture of deterministic probability distributions. Consider a discrete probability distribution over finitely many outcomes, and let $p_i$ be the probability of the $i$-th outcome. Let $\mathbf p\in\mathbb{R}^n$ be the corresponding probability vector. You can always decompose it as $$\mathbf p=\sum_{i=1}^n p_i \mathbf e_i,$$ where $\mathbf e_i$ are the standard basis vectors, $(\mathbf e_i)_j=\delta_{ij}$, which in this context can be thought of as representing a deterministic probability distribution, where only the $i$-th outcome is observed with non-vanishing probability.

Pretty much the same argument carries over when you consider Bell-like scenarios, though now you are dealing with conditional probability distributions among multiple parties. Nevertheless, you can always take the joint probability distribution and apply the above reasoning.

In particular, if you have a local behaviour, which is a joint conditional probability distribution $p(ab|xy)$ that factorises as $$p(ab|xy)=\sum_\lambda p_\lambda p(a|x,\lambda)p(b|y,\lambda),$$ then you can decompose each $p(a|x,\lambda)$ and $p(b|y,\lambda)$ as a convex mixture of deterministic probabilities, using the strategy above. Note that in doing that you get a bunch of extra sums over auxiliary indices. But you can imagine all of these extra indices as extra "hidden variables", and if you then put everything together you end up writing $p(ab|xy)$ as a convex mixture of local deterministic behaviours. In other words, you can always assume $p(a|x,\lambda)$ is nonzero for one and only one $a$, for each value of $x$ and $\lambda$ (and same goes for $p(b|y,\lambda)$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.