5
$\begingroup$

For example when $k=2$, consider $n+1$ disjoint events :

$E=\{ e_0,e_1,...,e_n\}$ with the probability that $P(e_0)=a,P(e_i)=b,1\leq i\leq n.$

We define $n$ events $E_1,E_2,...,E_n$ such that $E_i=\{e_0\} \cup\{ e_i \}$.For any $1\leq i<j<k\leq n$ we obtain:

$P(E_i)P(E_j)P(E_k)=(a+b)^3,P(E_i)P(E_j)=(a+b)^2,P(E_i \cap E_j)=a,P(E_i\cap E_j\cap E_k)=a.$

We can easily prove the existence of (a,b) satisfying $(a+b)^2=a,0<a,b<1,a+nb<1$ for any given n, which means that for any $2$ events are independent while any $3$ are not.

So a more genreal question is that given $n>2$ and $1<k<n$. Is it possible to exist $n$ events, s.t. for any $k$ among them are independent while any $k+1$ are not?

Beased the proof above, we know that k=2 is OK.

$\endgroup$
1
  • $\begingroup$ +1 : Very interesting question, nice work shown. $\endgroup$ Commented Sep 22, 2021 at 7:46

2 Answers 2

2
$\begingroup$

Yes, it is possible.

Let $F$ be a finite field with $|F|>n$. I will denote $|F|=q$, and identify $F$ with the set $\{0,1,\dots,q-1\}$.

Let $P$ be a uniformly randomly chosen polynomial whose degree is less than $k$. There are $q^k$ equally likely options for $P$, of the form $P(x)=\sum_{j=0}^{k-1}a_jx^j$ with $a_j\in F$ for each $j\in \{0,\dots,k-1\}$.

Then, for each $i\in \{0,1,\dots,n-1\}$, let $E_i$ be the event that $P(i)=0$. We can see that $P(E_i)=1/q$, since $P(i)$ is equally likely to be any element of $F$.

Note that $E_0,E_1,\dots,E_{k-1}$ is an independent set, since Lagrange interpolation implies that the vector $(P(0),P(1),\dots,P(k-1))$ assumes all $q^{k}$ possible vectors in $F^k$ as $P$ ranges over all $q^k$ possible polynomials of degree less than $k$. However, the collection $E_0,\dots,E_{k-1},E_{k}$ is not independent, since $$ P(E_0\cap \dots \cap E_{k})=(1/q)^k\neq (1/q)^{k+1}=P(E_0)\cdots P(E_k) $$ as the only polynomial of degree less than $k$ with $k$ distinct roots is the zero polynomial.

$\endgroup$
4
  • $\begingroup$ Your idea looks very elegant. Anyway, I am afraid it does not implicate independence for any group of K variables. For instance for k=2 and n=9 if you choose q=10, you have not independance of $E_0$ and $E_5$. Actually, I have created a python script to check it. I put it in my answer so you can check whether it is correct. $\endgroup$
    – Arnaud
    Commented Sep 23, 2021 at 16:15
  • $\begingroup$ @ArnaudMégret There do not exist any finite fields with a size of $q=10$. You might be confusing "finite field of size $q$" with $\Bbb Z/q\Bbb Z$; the two are not the same. $\endgroup$ Commented Sep 23, 2021 at 16:17
  • $\begingroup$ Oh yes, actually I didn't know the term finite fields. I supposed it was an algebra with modulo n operations. $\endgroup$
    – Arnaud
    Commented Sep 23, 2021 at 16:24
  • $\begingroup$ using n=11 (prime number) seems to provide any independence for 2 variables. $\endgroup$
    – Arnaud
    Commented Sep 23, 2021 at 16:30
1
$\begingroup$

Thanks for @Mike Earnest. I now can write a complete proof.

\textbf{Question:}\ Given $n>2$ and $1<k<n$. Proof the existence of $n$ events whose probability is greater than 0, s.t. for any $k$ among them are independent while any $k+1$ are not. \

\textbf{Lemma: }\ Given $k$ different integers $\{ i_1,i_2,...,i_k\}$, $k$ integers $ C=( A_1,A_2,...,A_k )^T$ a $k \times k $ matrix $A$: \begin{equation} \left[ \begin{array}{ccccc} 1 & i_1 & i_1^2 & \dots & i_1^{k-1} \\ 1 & i_2 & i_2^2 & \dots & i_2^{k-1} \\ \dots & \dots & \dots & \dots & \dots \\ 1 & i_k & i_k^2 & \dots & i_k^{k-1} \\ \end{array} \right ] \end{equation} Then given a prime number $p $ such that $p > k$. Then the following equation have and only have one solution for $x=( x_1,x_2,...,x_k)^T$,where $x_j \in \{0,1,...,p-1\} $: $$Ax=C.$$

\textbf{Proof of Lemma: }

\qquad We write it in the form of augmented matrix :

\begin{equation} \left[ \begin{array}{cccccc} 1 & i_1 & i_1^2 & \dots & i_1^{k-1} & A_1\\ 1 & i_2 & i_2^2 & \dots & i_2^{k-1} &A_2\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 1 & i_k & i_k^2 & \dots & i_k^{k-1} & A_k \\ \end{array} \right ] \end{equation} We use elementary matrix transformation, \textbf{But once we get a $A_i$ out of range$(A_i>p$ or $A_i<0)$ in operation, we keep the remainder of modulo p instead of $A_i$}. Notice that this new defined matrix transformation dose not affect the properties of matrix $A$. Thus verifying the $det(A) \neq 0$ can conduct that $Ax=C$ has only one solution. Since we have$$det(A)=\prod_{i>j}^{}{(x_i-x_j)}\neq 0$$, thus we proved.

\textbf{Proof:}

\qquad We now try to show that there exist $n$ events such that for any $k$ among them are independent while any $k+1$ are not.

\qquad For any given $n$, we find a prime number $p$ ,$p>n$. And define a set $T= \{ 0,1,...,p-1 \}$. We also define a polynomial $$f(x)=\sum_{i=0}^{k-1}{a_ix^i}$$where $a_i \in T, 0\leq i \leq k-1$. All the coefficients of $f$ is randomly chosen from $T$.

\qquad Then we define $n$ events set $E=\{E_0,E_1,E_2,...,E_{n-1}\}$. We define $P(E_i)$ is the probability of $p | f(i)$. We now show that any $K (K\leq k)$of them are independent.

\qquad $P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})$ means the randomly choose cause $p | f(s_t),1\leq t \leq K $. We now calculate the quantity of $ \{ a_0,a_1,...,a_{k-1} \} $ satisfying the condition $p | f(s_t)$ \textbf{for any given $s_j$} . Since $K\leq k$ so we seperate the coefficients into 2 groups $A=\{a_0,a_1,...,a_{K-1}\}$ and $B=\{a_K,a_{K+1},...,a_{k-1}\}$ (B may be empty). We let coefficients in B be randomly chosen. \textbf{For any given randomly choose of B}, there is one and only one solution for the coefficients $a_0,...,a_{K-1}$ satisfying the K equations below, according to the lemma (if $K>k-1$, the RHS=0).

$$\sum_{i=0}^{K-1}{a_is_r^i}=-\sum_{i=K}^{k-1}{a_is_r^i} \ \textup{(mod p)}, 1\leq r\leq K.$$ \qquad Which means that $p | f(s_t),1\leq t \leq K$. So the quantity of coefficient satisfying the conditions is exactly what we randomly chose coefficients in $B$. There are obviously $|T|^{|B|}=p^{k-K+1}$. Thus $P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})=\frac{|T|^{|B|}}{|T|^{k+1}}=p^{-K}.$

\qquad Notice that this also works for $K=1$, Thus $P(E_{s_j})=p^{-1}$, Thus $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})=p^{-K}=P(E_{s_1})P(E_{s_2})...P(E_{s_K}).$$

\qquad We have shown that any $K, K\leq k$ of them are independent. Now we will show that any $R, R>k$ of them are not. We notice that $P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_R})$ needs $R$ different roots on the field. The only polynomial still satisfy is zero polynomial(Actually for $K=k$ it has been zero polynomial but product of probabilities still hold). Thus, $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_R})=p^{-k}>p^{-R}=P(E_{s_1})P(E_{s_2})...P(E_{s_R})$$ \qquad Which means that any $R$ of them are not independent. Thus we proved.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .