2 fixed a typo

Let $G$ be a finite abelian group, $n$ a positive integer and let $G^n$ denote the direct product of $n$ copies of $G$. We say an element of $G^n$ is full if it acts as a nonidentity element of $G$ in each of the factors of $G^n$.

Now consider the following random process. Sample a full group element $(g_1,g_2,\ldots,g_n)$ uniformly at random from $G^n$. Now generate a subgroup $H$ of $G^n$ consisting of all elements of the form $\bigl(g_1^{a_1},\ldots,g_n^{a_n}\bigr)$ for integers $a_i$. If we do this $k$ times (sampling with or without replacement, more on this below), then we can let $H_j$ denote the subgroup generated on the $j$th iteration. Now we take the union of these subgroups and define $$N_k = \left| \bigcup_{j=1}^k H_j \right| \ ,$$ where $|\cdot|$ denotes the cardinality of the set. Finally, let $\mu_k = \mathbb{E}(N_k)$.

When $G$ is also a cyclic simple group, this is easy to calculate, so . So let's specialize to the simplest nontrivial case, $G = \mathbb{Z}/2 \times \mathbb{Z}/2$. (The other simplest case is $\mathbb{Z}/4$, but I'm not as interested in that one.) Then my question is,

How does $\mu_k$ grow as a function of $k$?

I am principally interested in lower bounds on $\mu_k$ in the case where the sampling is done uniformly without replacement on the set of full elements of $G^n$. Clearly sampling with replacement gives a lower bound, and it's much easier to work with. If you can say something about the variance of $N_k$ too, that would be outstanding.

1

# Generating a group by randomly sampling generators

Let $G$ be a finite abelian group, $n$ a positive integer and let $G^n$ denote the direct product of $n$ copies of $G$. We say an element of $G^n$ is full if it acts as a nonidentity element of $G$ in each of the factors of $G^n$.

Now consider the following random process. Sample a full group element $(g_1,g_2,\ldots,g_n)$ uniformly at random from $G^n$. Now generate a subgroup $H$ of $G^n$ consisting of all elements of the form $\bigl(g_1^{a_1},\ldots,g_n^{a_n}\bigr)$ for integers $a_i$. If we do this $k$ times (sampling with or without replacement, more on this below), then we can let $H_j$ denote the subgroup generated on the $j$th iteration. Now we take the union of these subgroups and define $$N_k = \left| \bigcup_{j=1}^k H_j \right| \ ,$$ where $|\cdot|$ denotes the cardinality of the set. Finally, let $\mu_k = \mathbb{E}(N_k)$.

When $G$ is a cyclic group, this is easy to calculate, so let's specialize to the simplest nontrivial case, $G = \mathbb{Z}/2 \times \mathbb{Z}/2$. Then my question is,

How does $\mu_k$ grow as a function of $k$?

I am principally interested in lower bounds on $\mu_k$ in the case where the sampling is done uniformly without replacement on the set of full elements of $G^n$. Clearly sampling with replacement gives a lower bound, and it's much easier to work with. If you can say something about the variance of $N_k$ too, that would be outstanding.