2
$\begingroup$

Assume that we have $p$ finite sets ${m_1},{m_2},...,{m_p}$, with known cardinalities ${M_1},{M_2},...,{M_p}$, where $1 \le {M_i} \leq q$ ($i=1,2,...,p$).

Each set contains (distinct) elements, taken from GF($q$) (I am interested in particular in the case where $q$ is a power of $2$). Now, we consider all possible assignments of elements to $\left\{ {{m_i}} \right\}_{i = 1}^p$. It is clear that we have $\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}} q \\ {{M_i}} \end{array}} \right)} $ such assignments.

For each assignment $A_k$ ($k=1,2...,\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}} q \\ {{M_i}} \end{array}} \right)} $) we consider all possible combinations of elements from the sets in the assignment, when one element is taken from each set (that is, we have $p$ elements for each combination), and we sum the elements of each combination, using GF($q$) arithmetic. There are $\prod\limits_{i = 1}^p {{M_i}} $ possible combinations/sums for each assignment.

Given the sums $S_{kj}$ ($j=1,2,...,\prod\limits_{i = 1}^p {{M_i}}$) for each assignment $k$, we count the number of distinct elements of GF($q$) among these sums, and we write down this number, $d_k$.

Repeating this process, we end with $\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}} q \\ {{M_i}} \end{array}} \right)} $ numbers.

As an example, consider the case $q = 4,p = 2,{M_1} = {M_2} = 2$. Possible assignments to $m_1$, as well as for $m_2$ in this case, are:

$$\left\{ {0,1} \right\},\left\{ {0,2} \right\},\left\{ {0,3} \right\},\left\{ {1,2} \right\},\left\{ {1,3} \right\},\left\{ {2,3} \right\}$$

Assume a specific assignment ${m_1} = \left\{ {0,1} \right\},{m_2} = \left\{ {1,2} \right\}$. We have $4$ combinations/sums:

$0 + 1 = 1,0 + 2 = 2,1 + 1 = 0,1 + 2 = 3$ and for this specific assignment the number of distinct elements is $4$.

Another possible assignment is ${m_1} = \left\{ {0,1} \right\},{m_2} = \left\{ {0,1} \right\}$. Now the combinations/sums are $0 + 0 = 1,0 + 1 = 1,1 + 0 = 1,1 + 1 = 0$ and we have $2$ distinct elements. Repeating this, we obtain $\left( {\begin{array}{*{20}{c}} 4 \\ 2 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} 4 \\ 2 \end{array}} \right) = 36$ numbers.

Denote by $d$ the random variable that counts the number of distinct elements for each assignment. My question is: what is the probability that $d=n$ ($n=1,2,...,q$)? in other words, given cardinalities ${K_1},{K_2},...,{K_p}$, what is the probability that the number of distinct sums for a randomly chosen assignment equals $n=1,2,...,q$?

I tried to formulate this as the probability that union of $\frac{{\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}} q\\ {{M_i}} \end{array}} \right)} }}{{{{\max }_i}\left( {{M_i}} \right)}}$ sets of cardinality ${\max _i}\left( {{M_i}} \right)$ is of size $n$ (this way the probability is zero for $d < {\max _i}\left( {{M_i}} \right)$), but this does not take into account additional properties of GF($q$).

It is interesting to note that in the example above, we have zero probability for $d=3$: $$\Pr \left( {d = 1} \right) = 0,\Pr \left( {d = 2} \right) = 1/3,\Pr \left( {d = 3} \right) = 0,\Pr \left( {d = 4} \right) = 2/3$$

I also noted that when $M_i=2$ and $q=4$, we have for each $p$: $\Pr \left( {d = 2} \right) = 1/3^{p-1}$.

(This probability distribution was calculated using a computer, computing $d_k$ explicitly for each assignment).

$\endgroup$
  • $\begingroup$ To see if I understand right, for n=1 the probability is 0 except for when all the M_i are 1 (in which case it's 1). $\endgroup$ – dspyz Aug 25 '13 at 18:57
  • $\begingroup$ If any of the $M_i$ is $0$ the random selection described is impossible. Assuming that all of the $M_i$ are at least $1$ the sum appears to be structured such that for any $x \in \mathrm{GF}(q)$ it guarantees to include a case where the first set contains $x$ and each of the other sets contain $0$, meaning that $P(n=q) = 1$. I conclude that the question is misformulated. $\endgroup$ – Peter Taylor Aug 25 '13 at 19:30
  • $\begingroup$ The question doesn't make sense to me. There are $\prod_i {q \choose M_i}$ ways to choose the $p$ sets. Then, given a choice of the sets, there are $\prod_i M_i$ sums (obtained by picking one element from each set and summing the resulting $p$ elements). What's the probability space here? Are you asking, for a random choice of sets, what's the probability that all of the $\prod_i M_i$ sums obtained from those sets are distinct? If so, you might be able to get a reasonable estimate for this probability by using the birthday paradox (as a heuristic). $\endgroup$ – D.W. Aug 26 '13 at 4:39
  • $\begingroup$ @dspyz: you are right. $\endgroup$ – MJK Aug 26 '13 at 7:47
  • $\begingroup$ @PeterTaylor: $1 \le M_i \le q$. I reformulated my question. $\endgroup$ – MJK Aug 26 '13 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.