0
$\begingroup$

Hi all,

Suppose that $\mathbf{f}=[f_1, f_2,\ldots,f_m]$ and $\mathbf{g}=[g_1,g_2,\ldots,g_m]$ are two $m$-dimensional vectors. All $f_i$'s are chosen uniformly randomly from a finite field $\mathbb{F}_q$, where $q$ is the finite field size. For convenience, we denote the elements of $\mathbb{F}_q$ as $\{0, 1, 2,\ldots,q-1\}$. Each $g_i$ is distributed as $\mathrm{Pr}(g_i=0)=1-p_i$ and $\mathrm{Pr}(g_i=r)=p_i/(q-1),r=1,2,\ldots,q-1$. Note that $p_i$ might not be equal for each $i\in\{1,2,\ldots,m\}$.

My question is, is that possible to determine the probability that $\mathbf{f}$ and $\mathbf{g}$ are orthogonal, i.e., $\sum_{i=1}^mf_ig_i=0$? If a closed form is not possible, is that possible to bound the probability? What I want to know is, whether such a probability would approach $0$ when I use a sufficiently large $q$. Any suggestions or references are appreciated.

Thanks sincerely.

$\endgroup$
3
$\begingroup$

If $\vec g = \vec 0$, then all vectors $\vec f$ are orthogonal to $\vec g$.

If $\vec g \ne \vec 0$, then $1/q$ of the vectors $\vec f$ are orthogonal to $\vec g$. Given the previous coordinates of $\vec f$, there is a unique choice for the last coordinate of $\vec f$ paired with a nonzero coordinate of $\vec g$ so that $\vec f \cdot \vec g = 0$.

So, $Prob(\vec f \perp \vec g) = \prod (1-p_i) + \frac{1}{q}\bigg( 1 - \prod (1-p_i)\bigg).$ If you fix the set $\lbrace p_i \rbrace$, the limit as $q \to \infty$ is $\prod(1-p_i)$, not $0$.

$\endgroup$
  • $\begingroup$ Thanks Douglas. It seems that the probability does not depend on $p_i$ too much because they only define the probability that $\mathbf{g}$ is a zero vector? Let's say, if we are told $\mathbf{g}\neq\mathbf{0}$ a priori, is the probability that $\mathbf{f}$ orthogonal to $\mathbf{g}$ is simply $1/q$? $\endgroup$ – leeyee May 22 '13 at 14:50
  • $\begingroup$ @Ye Li: Yes, and yes. For example, if you set one of the $p_i$ to $1$, so that coordinate is never $0$, then the other $p_i$ would not matter, and the probability that $\vec f \perp \vec g$ would be $1/q$. $\endgroup$ – Douglas Zare May 22 '13 at 20:27
  • $\begingroup$ What happens if we have vectors $f \in \mathbb{Z}_m^k, composite(m)$? $\endgroup$ – Samuel Schlesinger Mar 24 '17 at 7:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.