User rodolphe - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:45:31Z http://mathoverflow.net/feeds/user/22976 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121470/minimum-number-of-solutions-in-a-system-of-equalities-and-non-equalities Minimum number of solutions in a system of equalities and non-equalities Rodolphe 2013-02-11T13:43:14Z 2013-02-11T13:43:14Z <p>Let $k <p>Find the minimum number of solution of the system </p> <p>$$P_{2i} + P_{2i+1} = \lambda_i, \forall i\leq k$$</p> <p>with the condition that the$P_1, ..., P_{2k+1}$are pairwise distinct.</p> <p>The law "+" on the$n-$bits strings is the "xor" ie we consider the n-bit strings as element of$(\mathbb{Z}/2\mathbb{Z})^n$.</p> http://mathoverflow.net/questions/116143/conditional-probability-deviation-from-the-uniform-distribution Conditional probability, deviation from the uniform distribution Rodolphe 2012-12-12T05:34:10Z 2012-12-12T05:34:10Z <p>Let$N\in\mathbb{N}$and$G$the group$\mathbb{Z}/n\mathbb{Z}$.</p> <p>Let$q&lt; N$and:</p> <ul> <li>$a_1, ..., a_q$pairwise distinct elements of$G$</li> <li>$b_1, ..., b_q$pairwise distinct elements of$G$</li> <li>$x_1, ..., x_q$pairwise distinct elements of$G$</li> <li>$y_1, ..., y_q$pairwise distinct elements of$G$.</li> </ul> <p>Let$P$be a random permutation of$G$verifying$P(a_i)=b_i, \forall i\leq q$.</p> <p>Let$Q$be a random permutation of$G$.</p> <p>Let$k_0, k_1$be random elements of$G$.</p> <p>Let$E$denote the function$E(x)=P(x + k_0)+k_1$</p> <p>I want to prove that $$\Pr[E(x_q)=y_q|E(x_\ell )=y_\ell, \forall \ell &lt; q]$$ is greater than $$\left(1-\frac{2q}{N}\right)\Pr[Q(x_q)=y_q|Q(x_\ell)=y_\ell, \forall \ell &lt; q]$$</p> <p>The first probability is over the randomness of$k_0, k_1$and$P$. The second probability is over the randomness of$Q$.</p> <p>If we hadn't equations$P(a_i)=b_i$on$P$, then the two probabilites would be equal. So this result would show that, adding conditions to$P$doesn't change too much the distribution of$(E(x_1), ..., E(x_q))$, it should still be close of the uniform distribution.</p> <p>Thank you</p> http://mathoverflow.net/questions/115972/apparently-simple-probability Apparently simple probability Rodolphe 2012-12-10T12:49:46Z 2012-12-10T21:27:36Z <p>Hello,</p> <p>Let$x\in[0;1]$and$(B_i)_i$be events defined by$P(B_i)\leq x, \forall i$. Furthermore, this inequality is independent of the other events$B_i$but the events are not necessarily independent.</p> <p>I want to upperbound the probability of$A_k = (B_1\cup B_2)\cap (B_2\cup B_3)\cap\cdots\cap (B_k\cup B_{k+1})$. The first terms give (I simplified each$A_i$):</p> <p>$$P(A_1)\leq 2x$$</p> <p>$$P(A_2)=P((B_1\cap B_3) \cup B_2)\leq x^2 + x$$</p> <p>$$P(A_3)=P((B_2\cap B_3)\cup(B_2\cap B_4)\cup(B_1\cap B_3))\leq 3x^2$$</p> <p>What's the upperbound for any$k$?</p> <p>Thank you very much</p> 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/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> 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> http://mathoverflow.net/questions/94292/distance-from-uniform-distribution Distance from uniform distribution Rodolphe 2012-04-17T13:53:47Z 2012-04-17T13:53:47Z <p>Hello,</p> <p>This problem comes from my own research. I'm trying to compute the distance to the uniform distribution of some family of functions.</p> <p>Suppose you have a set$E$of cardinal$N$and a set of functions$F$.</p> <p>I have already proved that it exists$\alpha$such that, for every$x,y\in E$, we have : $$|Pr(f(x)=y) - \frac{1}{N}|\leq \alpha.$$</p> <p>The probability is taken over functions$f$randomly chosen in$F$.</p> <p>Now, I'd like to show that for every$x_1, x_2, ..., x_q$pairwise distinct and$y_1, ..., y_q$pairwise distinct, we have : $$|Pr(\forall i\leq q, f(x_i)=y_i)-\frac{1}{N\times(N-1)\times\cdots\times(N-q+1)}|\leq q\times \alpha.$$</p> <p>I don't know if it's true and/or easy to prove.</p> <p>Thank you for your help.</p> http://mathoverflow.net/questions/115972/apparently-simple-probability/116021#116021 Comment by Rodolphe Rodolphe 2012-12-12T05:06:06Z 2012-12-12T05:06:06Z Not exactly what I expected but that's it. Thank you http://mathoverflow.net/questions/108825/conditional-probability-with-permutations/108843#108843 Comment by Rodolphe Rodolphe 2012-10-04T21:51:04Z 2012-10-04T21:51:04Z So we know that $$Pr[P(x_1+k_0)=y_1+k_1]\geq (N-q)/N * (N-q)/N * 1/(N-q = (N-q)/N&#178; = (1-q/N) * 1/N$$ With the same reasoning, you can show that : $$Pr[P(x_1+k_0)=y_1+k_1\textnormal{ and }P(x_2+k_0)=y_2+k_1]\geq (1-2q/N) * 1/(N(N-1))$$ That's why, it seems intuitive (and I'm pretty sure it's true) to conjecture what I said in the first post. http://mathoverflow.net/questions/108825/conditional-probability-with-permutations/108843#108843 Comment by Rodolphe Rodolphe 2012-10-04T21:47:31Z 2012-10-04T21:47:31Z Thank you for your answer. Indeed, I forgot to say that$q$should be less or equal to$N/2$(I think, but I'm not sure). I have some ideas that could help : If you want to study $$Pr[P(x_1+k_0)=y_1+k_1]$$ you see that there is$N-q$values of$k_0$and$N-q$values of$k_1$such that both$x_1+k_0$and$y_1+k_1$are new input (and output) to$P$(ie we don't have$x_1+k_0=a_i$and$y_1+k_1=b_j$for some$i$or$j$). Now, if you choose one of those values of$k_0, k_1$, you connect$x_1+k_0$to$y_1+k_1$with probability$1/(N-q)\$.