Subadditivity, Limits and Lim Inf

Consider a sub-additive sequence $a_n$ for $n \geq 1$, where sub-additivity is defined as follows :
$$a_{n+m} \leq a_n + a_m$$

Fekete's Lemma says that for any such sequence $\lim_{n \rightarrow \infty} a_n/n = \lim \inf_{n \rightarrow \infty} a_n/n $, which can be easily proved. The proof is as follows-

Let $\lim \inf_{n \rightarrow \infty} a_n/n  = l$. Therefore, $\exists K$ s.t.
$$\left\vert \frac{a_K}{K} - l \right\vert = \epsilon/2$$

Now consider a large enough $L$ such that $ \frac{a_r}{KL} < \epsilon/2, \forall  r < K$. Thus, for every $n \geq KL$ we can write $n$ as $n = Kq + r$, where $q \geq L$ and $r<K$. Therefore,

\begin{align}
\frac{a_n}{n} & \leq \frac{q a_K}{Kq+r} + \frac{a_r}{Kq+r} \\
                        & \leq \frac{q a_K}{Kq} + \frac{a_r}{Kq} \\
                        & \leq \frac{a_K}{K} + \frac{a_r}{Kq} \\
                        & \leq  l + \frac{\epsilon}{2} + \frac{\epsilon}{2}\\
\end{align}

Since this is true for all $n > KL$ the limit exists and is equal to $l$. An alternate but similar proof is given here.

Pairwise Independence, Mutual Independence and Coding Theory

Consider a set of variables $\{X_1, X_2, ..., X_n\}$. A pair of variables $X_i, X_j$ are pairwise independent  iff $P(X_i,X_j) = P(X_i)  P(X_j)$. And any subset $A_k =\{X_{i_1},X_{i_2},...X_{i_k}\}$ of random variables is mutually independent if

                            $P(X_{i_1},X_{i_2},...,X_{i_k}) = \prod_j P(X_{i_j}) $

Bernstein gave an example of a set of random variables, of which any two are pairwise independent, but the set as a whole is not. A general class of examples which can be easily constructed from this set is the following -

$X_1 = A_1$
$X_2 = A_2$
$X_3 = A_3$
$\vdots$
$X_k = A_k$
$X_{k+1} = A_1+A_2+...+A_k$

where $A_i$'s are a set of i.i.d. mutually independent random variables, uniformly distributed in $\mathbb{F}_2$. Now it can be easily seen that any size $k$ subset $S_k$ of  $\{X_1, X_2, ..., X_{k+1}\}$ is a mutually independent set, but the $k+1$  set  $\{X_1, X_2, ..., X_{k+1}\}$  has a degenerate probability distribution given $A_k$ i.e.
                               $P(X_1, X_2, ..., X_{k+1} | A_k) \in \{0,1\}$

Now one can observe from the example that this is an example of parity check codes (wiki).  Also it is easy to observe that parity check codes are MDS codes. (wiki)

Now, given a general set of $n$ random variables which is $k$ independent (any $k$ subset is mutually independent) is it possible to construct an MDS code from these?

I give below conditions in which MDS code are constructable :

• The random variables $X_i$ are uniformly distributed in a field $\mathbb{F}_q$.
• The set $A_n = \{X_1, X_2, ..., X_n\}$ is $k$ independent i.e. any $k$ subset $A_k$ is mutually independent
• The probability distribution of $A_n$ given $A_k$ is degenerate i.e.

                                                    $P(A_n | A_k) \in \{0,1\}$

Now, given these conditions it can be easily seen from the proof of the Singleton bound (for general non-linear codes) that $\{X_1, X_2,...,X_n\}$ is an MDS code [length, information bits, min. distance] = $[ n, k, n-k+1]$.