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

<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.</p>

<p>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.</p>

<p>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$.</p>

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

<p>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:</p>

<p>$$\left\{ {0,1} \right\},\left\{ {0,2} \right\},\left\{ {0,3} \right\},\left\{ {1,2} \right\},\left\{ {1,3} \right\},\left\{ {2,3} \right\}$$</p>

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

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

<p>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.</p>

<p>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$?</p>

<p>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 &lt; {\max _i}\left( {{M_i}} \right)$), but this does not take into account additional properties of GF($q$).</p>

<p>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$$</p>

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

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

CC BY-SA 3.0
2013-08-25T18:57:28.987Z
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).
dspyz
CC BY-SA 3.0
2013-08-25T19:30:01.330Z
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.
Peter Taylor
CC BY-SA 3.0
2013-08-26T04:39:49.987Z
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).
D.W.
CC BY-SA 3.0
2013-08-26T07:47:31.027Z
@dspyz: you are right.
MJK
CC BY-SA 3.0
2013-08-26T07:48:20.873Z
@PeterTaylor: $1 \le M_i \le q$. I reformulated my question.
MJK
CC BY-SA 3.0
2013-08-26T07:52:38.203Z
@D.W.: I reformulated my question. The birthday paradox (or balls and bins) was my first estimate, but due to the arithmetic of GF($q$) this estimate is problematic. For example, if the size of one set is larger than $1$, there is no option that the number of distinct sums for some assignment will be $1$. In other words, the number of sums ($\prod\limits_{i = 1}^p {{M_i}}$) is not the only factor - the cardinalities of the sets are also important.
MJK
<combinatorics>
Combinations over GF($q$)
MJK
# Combinations over GF($q$)

(Asked by: username_0 on 2013-08-25)

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).

**Tags:** combinatorics
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_3**: 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).  
> **username_0**: @dspyz: you are right.  
> **username_0**: @PeterTaylor: $1 \le M_i \le q$. I reformulated my question.  
> **username_0**: @D.W.: I reformulated my question. The birthday paradox (or balls and bins) was my first estimate, but due to the arithmetic of GF($q$) this estimate is problematic. For example, if the size of one set is larger than $1$, there is no option that the number of distinct sums for some assignment will be $1$. In other words, the number of sums ($\prod\limits_{i = 1}^p {{M_i}}$) is not the only factor - the cardinalities of the sets are also important.  

---

## 0 answers

