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 !



Conditional probability with permutations
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$).


