Conditional probability on permutations and keys - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T07:52:41Z http://mathoverflow.net/feeds/question/110822 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110822/conditional-probability-on-permutations-and-keys Conditional probability on permutations and keys Rodolphe 2012-10-27T11:46:21Z 2012-10-27T11:46:21Z <p>Hello,</p> <p>Let $N\in\mathbb{N}$ and $q_E, q_1$ two integers such that $2 q_1 q_E &lt; 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$.</p> <p>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}$.</p> <p>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}$$</p> <p>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.</p> <p>Thank you !</p>