MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Distance from uniform distribution

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.

Suppose $E$ is the set $\{1,2,\dots,N\}$, $F$ is the set of the $N$ cyclic permutations $f_k(x)=x+k\pmod n$, and the probability distribution is uniform on $F$. Then your assumption is satisfied with $\alpha=0$, but your conclusion is not (when $N$ is at least 3). – Andreas Blass Apr 17 2012 at 14:57