$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

Question

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.

Answer 1

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}$.

Answer 2

Here is the way I would go about it. Given $k \geq 3$, first construct $(\Omega, P)$ and $k-1$ events $E_i$ with $P(E_i) = 1/2$ which are all mutually independent. This is actually the key to the construction, to show that you understand what it actually takes for this many events to be mutually independent. Taking $P$ as a uniform probability measure on $\Omega$ is a good start; in this case $P(E_i)$ is just proportional to $|E_i|$. The way to think about independence is that independent events are "orthogonal" in some sense: if you draw a big chart of $\Omega$ where your events are lines, planes, hyperplanes, &c, independent events should be mutually perpendicular. Consider different numbering schemes for the outcomes in $\Omega$; you'll know when you've found the right one.

Now, all you have to do is construct one more event $E_k$ which satisfies the requirement: independence with any set of $k-2$ of your original events, but not with all $k-1$ of them. The case for $k=4$ is the first instructive one.