For a random permutation $P$, what's the probability of the following event?
Assuming the $x_i$ are chosen independently of $P$, and the witdth $k$ of $x$ is not too narrow, it makes sense to use the approximation that $x\mapsto P(x)\oplus x$ behaves like a random function, at least as far as collisions are concerned.

Note: I wish I had a proof or convincing argument of that. The best I have right now is that without knowledge of $P$, we need nearly $2^{k/2}$ queries to $x\mapsto P(x)\oplus x$ in order to get a significant advantage distinguishing that from a random function. But that argument does not explain why the approximation still holds for e.g. $k=10$, $q=100$, when it does.

If further assuming that the $x_i$ are distinct, the problem becomes a straightforward application of the birthday problem for cryptographic hashing.