Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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$? –  Ye Li May 22 '13 at 14:50
    
@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$. –  Douglas Zare May 22 '13 at 20:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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