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