Conditional probability on permutations and keys

2012-10-27T11:46:21Z

Hello,

Let $N\in\mathbb{N}$ and $q_E, q_1$ two integers such that $2 q_1 q_E < N $. Let $P$ be a random permutation of $\mathbb{Z}/N\mathbb{Z}$ with the condition that $P$ verifies $q_1$ equations : $P(a_i)=b_i, i\leq q_1$. Let $k_0, k_1$ be random and we note $E$ the function defined by $E(x)=P(x+k_0)+k_1$.

Let $(x_i)_{i\leq q_E}$ be pairwise distinct element of $\mathbb{Z}/N\mathbb{Z}$ and $(y_i)_{i\leq q_E}$ be pairwise distinct element of $\mathbb{Z}/N\mathbb{Z}$.

Prove that : $$Pr[E(x_{q_E})=y_{q_E}|E(x_i)=y_i,i\leq q_E-1] \geq \bigg(1-\frac{2q_1}{N}\bigg) \frac{1}{N-q_E}$$

You can see that if we had no equations on $P$, we would easily see that the left part of the inequality is equal to $\frac{1}{N-q_E}$. The goal is to study how adding equations to P will decrease this term.

Thank you !

Conditional probability on permutations and keys - MathOverflow

Conditional probability on permutations and keys