Conditional probability with permutations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:33:51Z http://mathoverflow.net/feeds/question/108825 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108825/conditional-probability-with-permutations Conditional probability with permutations Rodolphe 2012-10-04T14:47:30Z 2012-11-30T09:22:00Z <p>Hello,</p> <p>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.</p> <p>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$</p> <p>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}$$</p> <p>Thank you !</p> http://mathoverflow.net/questions/108825/conditional-probability-with-permutations/108843#108843 Answer by David Feldman for Conditional probability with permutations David Feldman 2012-10-04T18:44:44Z 2012-10-04T19:25:55Z <p>My second comment indicates that I think you need to amend your conjecture, or else I don't understand. </p> <p>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.</p> <p>One should think of permutations here in terms of their cycle structures.</p> <p>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.</p> <p>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. </p> <p>The particular equations don't matter to your conjecture, only the resulting $T$ and $H$. </p> <p>As per my comment, take $x_1=y_1=0$. </p> <p>Now your probability conditions on either $(k_0,k_1)\in T\times H$ or $(k_0,k_1)\in G$.</p> <p>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$.</p> <p>That makes four cases to consider and I confess I have not yet worked out the details.</p> <p>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$).</p> http://mathoverflow.net/questions/108825/conditional-probability-with-permutations/108866#108866 Answer by Rodolphe for Conditional probability with permutations Rodolphe 2012-10-04T22:40:52Z 2012-10-04T22:40:52Z <p>Thank you for your answer. I think I solved the problem but it's just the beginning. I had something wrong in the conjecture.</p> <p>First, let's note $C_i$ the event $P(x_i+k_0)=y_i+k_1$.</p> <p>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}.$$</p> <p>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²$).</p> <p>Now I have to prove something like $$Pr[C_3|C_2,C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-2}$$</p>