Conditional probability with permutations 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 !
 A: My second comment indicates that I think you need to amend your conjecture, or else I don't understand.  
Allow me to sketch some relevant ideas for getting non-trivial lower bounds.  If my sketch does not suffice, I'll try to flesh it out when I have more time.
One should think of permutations here in terms of their cycle structures.
Your $q$ equations join some of the elements of ${\Bbb Z}/N{\Bbb Z}$ into cycles and others into finite order segments, each with, let's say, a head and a tail.  Write $H$ for the set of heads, $T$ for the set of tails.  Write $G$ for the graph of the partial function the equations determine.
Specifying a permutation satisfying the equations amounts to giving a bijection from $T$ to $H$.  Since $|T|=|H|=N-q$,  $(N-q)!$ permutations satisfy the equations and crucially, any given tail will have probability $1/(N-q)$ of joining any particular head. 
The particular equations don't matter to your conjecture, only the resulting $T$ and $H$. 
As per my comment, take $x_1=y_1=0$.  
Now your probability conditions on either $(k_0,k_1)\in T\times H$ or $(k_0,k_1)\in G$.
Your probability calculation reduces to estimating the probabilities that either $(x_2+k_0,y_2+k_1)\in T\times H$ or $(x_2+k_0,y_2+k_1)\in G$.
That makes four cases to consider and I confess I have not yet worked out the details.
This helps with one case: given $T$, $H$ both of cardinality $N-q$, how small can we have the intersection $T\times H \cap ((T+x_2)\times (H+y_2))$.  If $q$ is not too small,
the pigeon-hole principle gives a lower bound (but this does not exploit the product structure of $T\times H$).
A: Thank you for your answer.
I think I solved the problem but it's just the beginning.
I had something wrong in the conjecture.
First, let's note $C_i$ the event $P(x_i+k_0)=y_i+k_1$.
We have to slightly change the conjecture (I forgot a factor 2) :
$$Pr[C_2|C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-1}.$$
We have $$Pr[C_2|C_1]=Pr[C_2\cap C_1]/Pr[C_1]$$ and I know that $Pr[C_1]=1/N$ (easy computation) and for $C_2\cap C_1$, if $x_1+k_0$ and $x_2+k_0$ are not one of the $a_i$ and $y_1+k_1, y_2+k_1$ are not one of the $b_i$ then the two equations occur with probability $\frac{1}{(N-q)(N-1-q)}$ so we have :
$$Pr[C_2|C_1]\geq (N-2q)/N\times (N-2q)/N \times \frac{1}{(N-q)(N-1-q)} \times N$$
which almost solve the conjecture (I don't mind the term in $q²/N²$).
Now I have to prove something like $$Pr[C_3|C_2,C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-2}$$
