User rodolphe - MathOverflow

Minimum number of solutions in a system of equalities and non-equalities

2013-02-11T13:43:14Z

Let $k

Find the minimum number of solution of the system

$$P_{2i} + P_{2i+1} = \lambda_i, \forall i\leq k$$

with the condition that the $P_1, ..., P_{2k+1}$ are pairwise distinct.

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$.

Conditional probability, deviation from the uniform distribution

2012-12-12T05:34:10Z

Let $N\in\mathbb{N}$ and $G$ the group $\mathbb{Z}/n\mathbb{Z}$.

Let $q< N$ and:

$a_1, ..., a_q$ pairwise distinct elements of $G$
$b_1, ..., b_q$ pairwise distinct elements of $G$
$x_1, ..., x_q$ pairwise distinct elements of $G$
$y_1, ..., y_q$ pairwise distinct elements of $G$.

Let $P$ be a random permutation of $G$ verifying $P(a_i)=b_i, \forall i\leq q$.

Let $Q$ be a random permutation of $G$.

Let $k_0, k_1$ be random elements of $G$.

Let $E$ denote the function $E(x)=P(x + k_0)+k_1$

I want to prove that $$\Pr[E(x_q)=y_q|E(x_\ell )=y_\ell, \forall \ell < q]$$ is greater than $$\left(1-\frac{2q}{N}\right)\Pr[Q(x_q)=y_q|Q(x_\ell)=y_\ell, \forall \ell < q]$$

The first probability is over the randomness of $k_0, k_1$ and $P$. The second probability is over the randomness of $Q$.

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.

Thank you

Apparently simple probability

2012-12-10T12:49:46Z

Hello,

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.

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(A_1)\leq 2x$$

$$P(A_2)=P((B_1\cap B_3) \cup B_2)\leq x^2 + x$$

$$P(A_3)=P((B_2\cap B_3)\cup(B_2\cap B_4)\cup(B_1\cap B_3))\leq 3x^2$$

What's the upperbound for any $k$ ?

Thank you very much

Conditional probability with permutations

2012-10-04T14:47:30Z

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 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 !

Answer by Rodolphe for Conditional probability with permutations

2012-10-04T22:40:52Z

Thank you for your answer. I think I solved the problem but it's just the beginning. I had something wrong in the conjecture.

First, let's note $C_i$ the event $P(x_i+k_0)=y_i+k_1$.

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}.$$

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²$).

Now I have to prove something like $$Pr[C_3|C_2,C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-2}$$

Distance from uniform distribution

2012-04-17T13:53:47Z

Hello,

This problem comes from my own research. I'm trying to compute the distance to the uniform distribution of some family of functions.

Suppose you have a set $E$ of cardinal $N$ and a set of functions $F$.

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.$$

The probability is taken over functions $f$ randomly chosen in $F$.

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.$$

I don't know if it's true and/or easy to prove.

Thank you for your help.

Comment by Rodolphe

2012-12-12T05:06:06Z

Not exactly what I expected but that's it. Thank you

Comment by Rodolphe

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² = (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.

Comment by Rodolphe

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)$.