Given $n, k \in \mathbb{N}$, we create a set $S \subseteq \mathbb{Z}_m^k$ by treating it as an $n\times k$ grid and choosing each $S_{ij}$ by sampling from $\mathbb{Z}_m$, such that $P(S_{ij} = z) = p_z$. We'll define the occupant count $o$ to be the total number of non-zero elements from every vector, and we'll call the quantity $o/nk = 1 - \alpha$. We can think of $\alpha$ as the probability, if we were to probe our grid at random, that we would find a zero. I want to constrain my sets to some known $\alpha$ and then have $p_{z\neq 0} = p_{0\neq x\neq z}$. Clearly if $\forall x, y \in \mathbb{Z}_m, p_z = p_x$, this condition is met, but more generally, we can reason that

$\sum_{z \neq 0}p_z + \alpha$ = 1$

$\sum_{z \neq 0}p_z = (n - 1)p_z$

$(n - 1)p_z + \alpha = 1$

$p_z = \frac{1 - \alpha}{n-1}$

Then I can construct a graph $G$ where $V = S$ and the edge relation is defined as:

$E = \{ (x, y) \mid \langle x,y\rangle = 0 \}$

What I want to know is if we choose uniformly $x, y \in S$, what is $P((x, y) \in E)$?

A question I'd be quite willing to hear answered as well is the case when $S = \mathbb{Z}_n^k$.

I suspect that this probability will rise with $n$'s compositeness where $k > n$. It'd be curious if you could compute the number.

  • $\begingroup$ What is m in the above question, and how does it relate to n? $\endgroup$
    – daniello
    Mar 23, 2017 at 18:23
  • $\begingroup$ That was a screwup on my part, there is only $n$. I'll fix it when I get back to a computer or someone else could. $\endgroup$ Mar 23, 2017 at 19:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.