Skip to content

Odd dot product of two random 0-1 vectors

Question

Two random vectors of length 1010 are generated: every entry of v1v_1 is an independent Bernoulli(12)\text{Bernoulli}(\tfrac12) variable, and every entry of v2v_2 is an independent Bernoulli(34)\text{Bernoulli}(\tfrac34) variable. The probability that the dot product v1⋅v2v_1\cdot v_2 is odd can be written as 12−1an\frac12-\frac{1}{a^n} with aa prime. What is a⋅na\cdot n?

Short answer

4242. Each coordinate product is 11 with probability q=38q=\tfrac38, so the parity of a sum of 1010 independent bits is odd with probability 12(1−(1−2q)10)=12−12⋅4−10=12−2−21\tfrac12\left(1-(1-2q)^{10}\right)=\tfrac12-\tfrac12\cdot4^{-10}=\tfrac12-2^{-21}. Hence a=2a=2, n=21n=21.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free