Picking a special function from the set of random functions Consider a fixed integer $q$. Consider the set of all functions from $\{0, 1\}^{n+1}$ to $\{0, 1\}^{m}$. Let us pick one function from this set uniformly at random.
Now, let's say we want functions $f$ with the following property.
There exists a $b_f \in \{0, 1\}^{m}$ (depending on the function $f$) such that for every $x \in \{0, 1\}^{n}$,
$$f(0, x) - f(1, x) = b_f~~~mod~q.$$
What is the probability we pick such a function?
 A: First note that $\ f(0,x)-f(1,x)\in\{-1,0,1\} \ $.   If $\ b\in\{0,1\}\ $ and  $\ q\ge3\ $, then
$$
f(0,x)-f(1,x)\equiv b\text{ mod}(q)\iff
f(0,x)-f(1,x)= b\ ,
$$
so the probability you're looking for will be the same for all $\ q\ge3\ $.  It's not the same for $\ q=2\ $, however, because $\ {-1}\equiv1\pmod{2}\ $.
Note also that if $\ X_{y,i}=f(y)_i\ $ for $\ (y,i)\in\{0,1\}^{n+1}\times$$\{1,2,\dots,m\}\ $, and $\ f\ $ is chosen uniformly at random, then $\ X_{y,i}\ $ will be independent Bernoulli variates with $\ P\big(X_{y,i}=0\big)=P\big(X_{y,i}=1\big)=\frac{1}{2}\ $.  Therefore, if $\ Y_{x,i}=X_{(0,x),i}-X_{(1,x),i}= f(0,x)_i-f(0,x)_i\ $ for $\ (x,i)\in\{0,1\}^n\times$$\{1,2,\dots,m\}\ $, then $\ Y_{x,i}\ $ will be independent random variables, with
$$
P\big(Y_{x,i}=-1\big)=P\big(Y_{x,i}=1\big)=\frac{1}{4}
$$
and
$$
P\big(Y_{x,i}=0\big)=\frac{1}{2}\ .
$$
If $\ q\ge3\ $, the probability you're looking for is
\begin{align}
P\left(\bigcup_{b\in\{0,1\}^m}\bigcap_{x\in\{0,1\}^n}\bigcap_{i=1}^m\big\{Y_{x,i}=b_i\big\}\right)&=\sum_{b\in\{0,1\}^m}P\left(\bigcap_{x\in\{0,1\}^n}\bigcap_{i=1}^m\big\{Y_{x,i}=b_i\big\}\right)\\
&=\sum_{b\in\{0,1\}^m}\left(\prod_{i=1}^m\left(\frac{1}{2}\right)^{1-b_i}\left(\frac{1}{4}\right)^{b_i}\right)^{2^n}\\
&=\sum_{b\in\{0,1\}^m}\left(\frac{1}{2^{2^n}}\right)^{m+|b|}\ \ \ \big(\text{where $\ |b|=\big|\{i\,|\,b_i=1\}\big|\ $}\big)\\
&=\sum_{k=0}^m\sum_{b\in\{0,1\}^m,\\|b|=k}\left(\frac{1}{2^{2^n}}\right)^{m+k}\\
&=\left(\frac{1}{2^{2^n}}\right)^m\sum_{k=0}^m{m\choose k}\left(\frac{1}{2^{2^n}}\right)^k\\
&=\left(\frac{1}{2^{2^n}}\right)^m\left(1+\frac{1}{2^{2^n}}\right)^m\\
&=\left(\frac{1}{2^{2^n}}+\frac{1}{2^{2^{n+1}}}\right)^m\ .
\end{align}
If $\ q=2\ $, then the probability you're looking for is instead
$$
P\left(\bigcup_{b\in\{0,1\}^m}\bigcap_{x\in\{0,1\}^n}\bigcap_{i=1}^m\big\{Y_{x,i}=b_i\text{ mod}(2)\big\}\right)\ ,
$$
and $\ P\big(Y_{x,i}=0\text{ mod}(2)\big)=P\big(Y_{x,i}=1\text{ mod}(2)\big)=\frac{1}{2}\ $.  So for $\ q=2\ $
\begin{align}
P\left(\bigcup_{b\in\{0,1\}^m}\bigcap_{x\in\{0,1\}^n}\bigcap_{i=1}^m\big\{Y_{x,i}=b_i\text{ mod}(2)\big\}\right)&=\sum_{b\in\{0,1\}^m}P\left(\bigcap_{x\in\{0,1\}^n}\bigcap_{i=1}^m\big\{Y_{x,i}=b_i\text{ mod}(2)\big\}\right)\\
&=\sum_{b\in\{0,1\}^m}\left(\frac{1}{2}\right)^{2^nm}\\
&=2^m\left(\frac{1}{2}\right)^{2^nm}\\
&=\left(\frac{1}{2}\right)^{(2^n-1)m}\
\end{align}
