1
$\begingroup$

The following theorems are part of this paper

Suppose that $(X_1,\dots,X_k)$ is a family of i.i.d. uniform random variables in $\mathbb{F}^{n}$ (why do we assume that the exponent of the field/set/space is $^n$? Does it mean the product?) and let $\mathcal{H}$ be the vector space (for the finite field $\mathbb{F}$) of all $\mathbb{F}^{n}$-valued random variables. Let also $z\in\mathcal{H}$ be (stochastically) independent from $(X_1,\dots,X_k)$. Denote $H=vect\{X_1,\dots,X_k\}$ and the sub-vector of $\mathcal{H}$ spanned by $(X_1,\dots,X_k)$ and $H_z=vect\{z,X_1,\dots,X_k\}$. Clearly, stochastic independence implies linear independence and thus, $vect\{z,X_1,\dots,X_k\}$ are linearly independent. Conversely, we have the following:

$\textbf{Theorem 1:}$ $1.$ Let $Y_1,...,Y_L$ be $L$ linearly independent vectors in $H$ (i.e., linear combinations of $X_1,...,X_K$). Then, $Y_1,...,Y_L$ are stochastically mutually independent and uniformly distributed.

$2.$ Let $Y_1,...,Y_L$ be $L$ vectors in $H_z$ (i.e., linear combinations of $X_1,...,X_K$ and $z$) such that $z\notin vect\{Y_1,...,Y_L\}$. Then, $Y_1,...,Y_L$ are jointly independent from $z$.

$\textbf{Theorem 2:}$ Let $z$ be a random variable with values in $\mathbb{F}^{n}$. For each integer $M> 1$, there exists a family $(X_1,...,X_M)$ of random variables such that:

$1.$ $\sum_{j=1}^M X_j=z$ almost surely.

$2.$ For each $j$, $X_{-j}:=(X_i)_{i\neq j} $ is uniformly distributed over $\mathbb{F}^{n}$ and independent of $z$.

Could anybody prove the two theorems above and give the intuition behind them?

$\endgroup$
12
  • $\begingroup$ @Sangchul Lee Take a look if it is close to your field of knowledge! $\endgroup$ Jan 5, 2022 at 10:20
  • $\begingroup$ @William M. Also if you have any nice answers for my post I would be glad. I was really impressed by this answer here math.stackexchange.com/questions/4348593/… $\endgroup$ Jan 5, 2022 at 10:22
  • $\begingroup$ can I ask from what book are you seeing this? $\endgroup$
    – Masacroso
    Jan 5, 2022 at 10:23
  • 1
    $\begingroup$ @Masacroso here it is sciencedirect.com/science/article/abs/pii/S0899825614000177 check for lemma $4$ and $5$ in section $3.2.3$ if you like! $\endgroup$ Jan 5, 2022 at 10:33
  • 1
    $\begingroup$ There is a paywall and I don't have access to JSTOR. However, either $k = n$ and they got a typo or each $X_i$ is a $n$-vector itself with entries in $\mathbf{F}$ (this is probably the case). $\endgroup$
    – William M.
    Jan 6, 2022 at 23:46

1 Answer 1

1
$\begingroup$

First, notation: $\mathbb{F}^n$ is the space of $n$-tuples with coordinates from $n$. Thus $\mathbb{R}^2$ is pairs $(a_1,a_2)$, where each $a_j$ is a real number. In your scenario, each $X_j$ is a random variable picking random values from $\mathbb{F}^n$.

$H$ is spanned by $\{X_k\}_{k=1}^K$. Each generator increases the dimension by at most $1$, so $\dim{(H)}\leq K$. But the dimension of a vector space is the size of the largest linearly independent set.

Second, uniform random variables on a vector space are very special. They don't exist on vector spaces with infinitely many elements, so we can't use much of our intuition from $\mathbb{R}^n$ (Euclidean space). The key idea you don't appear to absorbed is the following: suppose $V$ is chosen uniformly from $\mathbb{F}^n$ and $W$ is any random variable on $\mathbb{F}^n$. Then $V+W$ is uniform.

I know of no good way to make this fact intuitive. Sometimes, probability is just confusing (c.f. Monty Hall). You just have to try some calculations and verify that it is in fact correct, and maybe even prove it for yourself. A good place to start is to try calculating the pdf when $V$ is uniform on $\mathbb{Z}/(5)$ and $W$ is uniform on $\{0,2\}$.

For the first theorem, consider the sequence of random variables $\{X_k\}_k$ as one giant random uniform variable on $(\mathbb{F}^n)^K$. Any surjective matrix takes a uniform random variable to a uniform random variable on its image (by symmetry). Since the components of a multivariate uniform joint distribution are each independent of each other, this gives part 1. Part 2 then applies the above "key fact."

For the second theorem, consider the sum $$S=Z_1+\dots+Z_{N-1}+(Z_N+\theta)$$ where each $Z_n$ is uniformly distributed. Each summand in $S$ is uniformly distributed!
Notice that we didn't need the $\{Z_n\}_n$ to be independent. In fact, if $\{Z_n\}_{n<N}$ are all independent, then $-(Z_1+\dots+Z_{N-1})$ is also uniform. In that case, we can take $Z_N=-(Z_1+\dots+Z_{N-1})$ a.s. and each summand in $S$ is still uniform. But $S=\theta$ a.s.

$\endgroup$
4
  • $\begingroup$ what do you mean with the phrase "Each generator increases the dimension by at most 1"? $\endgroup$ Jan 7, 2022 at 1:00
  • $\begingroup$ @HungerLearn: If $V$ is a vector subspace of $W$ and $w\in W$, then the smallest vector space containing both $V$ and $w$ has dimension $\dim{(V)}$ (if $w\in V$) or $\dim{(V)}+1$ (if $w\notin V$). $\endgroup$ Jan 7, 2022 at 4:06
  • $\begingroup$ you say "Zn is uniformly distributed. Each summand in S is uniformly distributed!" In other words, do these two theorems gives us a result that is: "any sum of uniformly distributed random variables is a random variable?" or something like this? $\endgroup$ Jan 10, 2022 at 8:02
  • 2
    $\begingroup$ @HungerLearn: Yes, any sum of random variables is a random variable. $\endgroup$ Jan 10, 2022 at 16:59

You must log in to answer this question.

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