Let $m\in\mathbb{N}$ and $p\in(0,1)$ be arbitrary. Is there a sequence $X\_1,\dots,X\_m$ of random variables with the following specs on their distribution:


* Each $X\_i$ is unbiased Bernoulli: $X\_i\sim {\rm Ber}(1/2)$ for $1\le i\le m$.
* $\mathbb{P}\bigl[X\_i=X\_j\bigr] = p$ for all $1\le i<j\le m$.



Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different
$\newcommand{\R}{\mathbb R}\renewcommand{\le}{\leqslant}\renewcommand{\ge}{\geqslant}$Let $n:=m\ge2$.
We will show that the desired condition holds if and only if
$$p\ge\frac{\lceil n/2\rceil-1}{2 \lceil n/2\rceil-1}.$$


Suppose for a moment that there exist random variables $X\_1,\dots,X\_n$ such that $X\_i\sim {\rm Ber}(1/2)$ for all $i$ and $P(X\_i=X\_j)=p\in(0,1)$ if $i\ne j$. That is, there is a nonnegative function $g\colon\{0,1\}^n\to\R$ such that


(i) $\sum\_{x\in\{0,1\}^n}g(x)=1$,


(ii) $\sum\_{x\in\{0,1\}^n}1(x\_i=0)g(x)=\frac12$ for all $i$,


(iii) $\sum\_{x\in\{0,1\}^n}1(x\_i=x\_j)g(x)=p$ if $i\ne j$.


Then, by symmetry, conditions (i)--(iii) will hold with $\tilde g(x):=\frac1{n!}\sum\_{\pi\in S\_n}g(\pi(x))$ in place of $g(x)$, where $S\_n$ is the set of all permutations of the set $[n]:=\{1,\dots,n\}$. Note that $\tilde g(x)=f(\sum\_1^n x\_i)$ for some function $f\colon\{0,\dots,n\}\to\R$ and all $x=(x\_1,\dots,x\_n)\in\{0,1\}^n$. Moreover, the conditions (i)--(iii) can be rewritten as


(I) $\sum\_{k=0}^n \binom nk f(k)=1$,


(II) $\sum\_{k=0}^n \binom{n-1}k f(k)=\frac12$ for all $i$,


(III) $\sum\_{k=0}^n a\_{n,k} f(k)=p$,


where
\begin{equation}
 a\_{n,k}=\binom{n-2}k+\binom{n-2}{k-2}; 
\end{equation}
of course, $\binom{n-2}k=0$ if $k\ge n-1$ and $\binom{n-2}{k-2}=0$ if $k\le1$.


Thus, for any given $n\ge2$ and $p\in(0,1)$, we want to see whether there is a nonnegative function $f\colon\{0,\dots,n\}\to\R$ such that conditions (I)--(III) hold.


Consider the ratios
\begin{equation}
r\_k:= r\_{n,k}:=\frac{a\_{n,k}}{\binom nk}
 =\frac{(n-k)(n-k-1)+k (k-1)}{n (n-1)}. 
\end{equation}
Note that $r\_{k+1}\le r\_k$ if $0\le k\le\frac{n-1}2$ and $r\_{k+1}\ge r\_k$ if $\frac{n-1}2\le k\le n-1$. Also, $r\_k=r\_{n-k}$.


It follows that


* the maximum, say $\overline p\_n$, of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(0)=f(n)=\frac12$ and $f\_1=\cdots=f\_{n-1}=0$, and hence $\overline p\_n=1$; moreover, then condition (II) happens to hold as well;
* if $n=2m$ is even, then the minimum, say $\underline p\_n$, of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(m)=1/\binom nm=1/\binom{2m}m$ and $f\_k=0$ for $k\in\{0,\dots,n\}\setminus\{m\}$, and hence $\underline p\_n=\underline p\_{2m}=\frac{m-1}{2m-1}$; moreover, then condition (II) happens to hold as well;
* if $n=2m+1$ is odd, then the minimum $\underline p\_n$ of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(m)=f(m+1)=\frac12/\binom{2m+1}m=\frac12/\binom{2m+1}{m+1}$ and $f\_k=0$ for $k\in\{0,\dots,n\}\setminus\{m,m+1\}$, and hence $\underline p\_n=\underline p\_{2m+1}=\frac m{2m+1}$; moreover, then condition (II) happens to hold as well.


So,


* the maximum of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\overline p\_n=1$;
* if $n=2m$ is even, then the minimum of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\underline p\_n=\frac{m-1}{2m-1}$;
* if $n=2m+1$ is odd, then the minimum of $\sum\_{k=0}^n a\_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\underline p\_n=\frac m{2m+1}$.


The set of all values of $\sum\_{k=0}^n a\_{n,k} f(k)$, where $f\colon\{0,\dots,n\}\to\R$ is a nonnegative function such that conditions (I) and (II) hold, is convex and therefore coincides with the interval $[\underline p\_n,\overline p\_n]=[\underline p\_n,1]$.


Thus, the following two conditions are equivalent to each other:


* there is a nonnegative function $f\colon\{0,\dots,n\}\to\R$ such that conditions (I)--(III) hold;
* $\underline p\_n\le p\le1$.



> 
> That is, for each natural $n\ge2$ and each $p\in[0,1]$, the following two conditions are equivalent to each other:
> 
> 
> * there exist random variables $X\_1,\dots,X\_n$ such that $X\_i\sim {\rm Ber}(1/2)$ for all $i$ and $P(X\_i=X\_j)=p$ if $i\ne j$;
> * $p\ge \underline p\_n$.
> 
> 
> 


One may also note that


* $\underline p\_n=\dfrac{m\_n-1}{2m\_n-1}$, where $m\_n:=\lceil n/2\rceil$;
* $\underline p\_n\le\underline p\_{n+1}<\frac12$ for all $n\ge2$;
* $\underline p\_n\to\frac12$ as $n\to\infty$.


