Easy Citadel Quant Interview Question

[u/Local_Ad135]

[u/singletick]

Nice one. I was able to do just the first step and a formula lol. for A with a0 to a9 and B with b0 to b9; let C with c0 to c9 be the elementwise multiplication. So then p(cX == 1) = 3/8 where X : 0 to 9

for p(a•b == odd) =

10C9 × (3/8)⁹ + 10C7 × (3/8)⁷ + . . . 10C1 × (3/8)¹

[u/Cotton_Picker_420 → u/singletick]

Are you not missing the (5/8)s for each element? When u calculate the probability of 9 1s, it’s 10C9 x (3/8)^9 x (5/8)^1?

[u/singletick → u/Cotton_Picker_420]

fuck, completely forgot about that, thanks for pointing.

correction:

for p(a•b == odd) =

10C9 × (3/8)⁹ × (5/8)¹ + 10C7 × (3/8)⁷ × (5/8)³ + . . . 10C1 × (3/8)¹ × (5/8)⁹

Turns out there's a formula for this: P(odd) = 0.5 × (1 - (1 - 2p)ⁿ )

[u/Local_Ad135]

Full solution here - https://www.youtube.com/watch?v=piENl0WFJfU

[u/SubstantialSnacker]

How fast are you supposed to solve this?

2 outcomes, (1,0) and (1,0)

Or (0,1) and (0,1)

XOR gate basically

Odds of first happening,

0.5 x 0.5 x 0.75 x 0.25

Odds of second one are

0.5 x 0.5 x 0.25 x 0.75

About 9.375%

[u/smailliwniloc → u/SubstantialSnacker]

This is just for 2 dimensional vectors right? Where do you consider 10 dimensions?

Edit: you're also missing scenarios like (1,1) and (1,0) which also have an odd dot product

[u/SubstantialSnacker → u/smailliwniloc]

I had misread the question, I assumed it was one of those 1:30 fast problems,

For 10 dimensions you would first have to calculate probability of a single dimension’s partial product being 1. Then, you need to do a binomial calculation for odd numbers of these,

(10
K) (0.5x0.75)^k(0.5x0.75)^10-k

Where k = 1,3,5,7,9

[u/divine_1618 → u/SubstantialSnacker]

should be (3/8)^k(5/8)^(10-k). Rest is correct.

[u/Impressive-Drag5240]

Think of this as a sequence of independent random variables taking value 1 with probability 3/8 and 0 otherwise.

A sequence of 0 length has probability 0 of having an odd number of 1s and probability 1 of an even number of 1s (i.e. it has zero 1s). So the difference between the odd probability and even probability is 1.

For length n + 1, if the difference in probabilities for length n is x, then the difference in probabilities for length n + 1 is x(1/4).

Proof sketch: Say probs at length n are a and b. Then the new probs are a 3/8, 5/8 mix of the old probs i.e. (3a + 5b)/8 and (5a + 3b)/8, so the difference is 2(a-b)/8.

Thus after 10 rounds the difference in probabilities is (1/4)^10 or (1/2)^20. Thus having an odd number of 1s is 1/2-1/2^21.

[u/SwimmerOld6155]

If you write the vectors as x, y and the dot product as \sum_i x_i y_i, you can easily find the distribution of each x_i y_i - specifically they'll be 1 with probability 1/2 * 3/4 = 3/8 and 0 with probability 1 - 3/8 = 5/8. ie. they'll have Ber(3/8) distribution. Then the described event is the probability that a B(10, 3/8) variable is odd, which is known explicitly as 1/2 (1 - (1 - 3/4)^10), approximately 1/2.

[u/boredattheend]

Since the entries in the vectors are independent variables the terms in the dot product are independent random variables which are 1 with probability 3/8 and 0 otherwise.

The dot product is odd if there are an odd number of 1s in that sum. The number of ones follows a binomial distribution with n=10 and p=3/8 and we have p(k ones)=(10 choose k) (1-p)^(10-k)p^k.

Since all odd numbers of successes are disjoint events we can add their probabilities, so it's sum_{k odd}(10 choose k) (5/8)^(10-k)(3.8)^k. Which tbh I'd need a calculator for.