I had the following question:
Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as small as possible.
I tried to answer it, but I just couldn't arrive at a correct solution. I solved the cases for $k=3$ and $k=6$, but I didn't arrive at a correct generalization. I made two different attempts (below), in both of which I think I had the general idea, but did not create the Events correctly. Can anyone please guide me to the correct solution?
Assume we are given some $k \geq 3$. If $k$ is even, proceed. If $k$ is odd, let $k=k+1$.
First, we define $\Omega = \{A_1,\ldots,A_k\}$, ensuring that $|\Omega|$ is even. We then define the probability distribution $P$ such that $p(A_i) = \frac{1}{k} \forall i$. Because $|\Omega|$ is even and probability is uniformly distributed, we can then select $k$ subsets of $\Omega$, each of size $\frac{k}{2}$ as such:
\begin{align*}
E_1 = \{A_1,\ldots,A_{k/2}\}\\
E_2 = \{A_2,\ldots,A_{k/2+1}\}\\
\ldots \\
E_{k/2} = \{A_{k/2},A_{k/2+1},\ldots,A_k\}\\
E_{k/2 + 1} = \{A_{k/2+1},A_{k/2+2}\ldots,A_k,A_1\}\\
\ldots\\
E_k = \{A_k,A_1,\ldots,A_{k/2-1}\}
\end{align*}
As each event contains $\frac k2$ outcomes, and each outcome has probability $\frac 1k$, it is clear that $\forall i, P(E_i) = \sum_{a \in E_i} P(a) = \sum_{i=1}^{\frac k2} \frac 1k = \frac k2 \cdot \frac 1k = \frac12$. In other words, each event has probability $\frac 12$.We note that because all events are distinct, have size $\frac k2$, but there are $k$ events, it is the case that $E_1 \cap E_2 \cap \ldots \cap E_k = \emptyset$. (Though this is apparent just from how we have selected our events.) Consequently, $P(E_1 \cap E_2 \cap \ldots \cap E_k) = 0$. However, as each event $E_i$ has probability $\frac 12$, we have that $P(E_1)P(E_2)\ldots P(E_k) = \left(\frac 12 \right)^k \neq 0$. Since $P(E_1)P(E_2)\ldots P(E_k) \neq P(E_1 \cap E_2 \cap \ldots \cap E_k)$, it is the case that our $k$ events are not mutually/fully independent.
Now all that remains is to show that the $k$ events are ($k-1$)-wise independent: this is actually not true. Sorry.
And another attempt: this one is more hurried as I was running out of time…
In order to ensure $(k-1)$-wise independence, we will create events as such:
\begin{align*}
E_1 = \{A_1,A_2\}\\
E_2 = \{A_1,A_3\}\\
\ldots \\
E_{l -1} = \{A_1,A_l\}\\
E_{l} = \{A_2,A_3\}\\
E_{l+1} = \{A_2,A_4\}\\
\ldots\\
E_{2l-2} = \{A_2,A_l\}\\
E_{2l-1} = \{A_3,A_4\}\\
\ldots\\
E_k = \{A_{l-1},A_l\}\\
\end{align*}
This means if we want $k$ events, we need some $l$ such that $k = \frac{l^2-l}{2}$. This comes down to a simple summation $\sum_{i=1}^{l-1}l-i$ that equals $\frac{l(l-1)}{2}$, i.e. $\frac{l(l-1)}{2} =k$.So knowing $k$ we find $l$ and define our sample space $\Omega = \{A_1,A_2,\ldots,A_l\}$, again with uniform probability distribution $P$ such that $\forall i, P(A_i) = \frac 1l$.
Then for any pair $E_a,E_b$ we will have $P(E_a \cap E_b) = p(A_x)$, where $A_x \in \Omega$. Because of the way we created the events, any two events will share exactly $1$ or $0$ outcomes $\ldots$ and here this attempt fails as well.
Best Answer
Given any $k\ge2$, for $k$ possible events, assume all combinations of an even number of events are equally likely, while an odd number of events has probability 0. One way to construct it, if $X_1,\ldots,X_k\in\{0,1\}$, draw $X_1,\ldots,X_{k-1}$ independently with probability $1/2$, and pick $X_k$ such that $\sum_{i=1}^k X_i$ is even.
A similar example can be made with $X_1,\ldots,X_k\sim\text{Uniform}[0,1]$. Draw $X_1,\ldots,X_{k-1}$ independently, and then let $X_k$ be that value in $[0,1)$ that makes $\sum_{i=1}^k X_i\in\mathbb{Z}$.