# Given an input x, can a distinguisher D output 1/2?

Consider a PPT distinguisher $$D$$. Now if I give it an input (a bit string) $$x$$, it outputs 1 if $$x$$ ends with $$1$$ and $$0$$ otherwise. We know such a distinguisher exists and is often given as an example many times.

Now consider another distinguisher strategy, where on input $$x$$, it checks if $$x$$ is $$0^n$$ or $$1^n$$. If yes, it outputs $$0$$. Otherwise it tosses a coin. If the result is heads, it outputs $$1$$, else it outputs $$0$$.

My question is - Is such a distinguisher valid according to the assumptions we make in cryptography?

I think it should be valid as our distinguisher being PPT, has access to a random number generator (hence the coin tosses). Can someone please confirm.

Such a distinguisher is certainly valid. In fact, in many proofs of security, we use this strategy. In particular, assume that there is some event that can be detected by $$D$$ with some non-negligible probability $$\epsilon=\epsilon(n)$$ when $$D$$ is given distribution $$X$$, but not when given distribution $$Y$$. You can use this to build a distinguisher but the problem is that the distinguisher needs to distinguish with probability non-negligibly greater than $$1/2$$ over all possible samples. In order to bridge this gap, we typically have $$D$$ output 1 if the detected value is received and output a random bit otherwise. This means that $$D$$ outputs 1 on distribution $$X$$ with probability $$\epsilon \cdot 1 + (1-\epsilon)\cdot\frac12 = \frac12 + \frac\epsilon2$$. If this detected event never happens on distribution $$Y$$, then $$D$$ will output 1 with probability $$\frac12$$ on random, and so it distinguishes with non-negligible probability $$\frac\epsilon2$$. Note that sometimes the detected event does happen on distribution $$Y$$ as well. But if it is with negligible probability then it's still OK. Letting $$\mu=\mu(n)$$ be a negligible function, we would have that $$D$$ outputs 1 on distribution $$Y$$ with probability $$\frac12 + \frac\mu2$$ (using the same computation as above) and the distinguishing probability is $$\frac\epsilon2 - \frac\mu2$$. Since $$\epsilon$$ is non-negligible and $$\mu$$ is negligible, this is still a non-negligible probability.