Hello,

This problem looks very simple and I conjecture it's true but I have a hard time proving it. It'd be very useful for my work (I'm doing a PhD) and I'll be glad to cite you in a future article if you help me.

Let $P$ be a random permutation of $\mathbb{Z}/N\mathbb{Z}$ with the condition that $P$ verifies $q$ equations : $P(a_i)=b_i, i\leq q$. Let $k_0, k_1$ be random and $x_1, x_2, y_1, y_2$ fixed numbers with $x_1\neq x_2, y_1\neq y_2$

Prove that : $$Pr[P(x_2+k_0)=y_2+k_1 | P(x_1+k_0)=y_1+k_1] \geq (1-\frac{q}{N}) \frac{1}{N-1}$$

Thank you !