## Interview Question

Quantitative Trader Interview

-New York, NY

Jane Street## If we flip a coin 100 times, what is the probability of getting even number of heads?

AnswerAdd Tags

## Interview Answers

11 Answers

▲

4

▼

1/2. Whether even or odd heads is ultimately determined by the nth flip, for any n. Probability even to odd or vice versa is n.

Anonymous on

▲

1

▼

( (2^99)+1) / (2^100) Even numbers include 0 heads to 100 heads. There exist 50% even complements and 50% odd complements from 1 heads to 100 heads.. So half our sample space. Now we do our zero case which is no heads and there is only 1 outcome.

Anonymous on

▲

0

▼

1. 0-99 flips: 50% even; 50% odd 2. P(even after 100 flips) = P(odd after 99)*0.5 + P(even after 99)*0.5 = 0.5*0.5+0.5*0.5 = 0.5

ky on

▲

0

▼

(Sum[i range from 0-50(inclusive)] 100 Choose 2i)*(1/2^100)

Joe G. on

▲

0

▼

Ans: 1/2 Lemma 1: For any n >= 1, sum_(i even, 0 = 1) coin tosses, P(getting even number of Heads) = 2^(n-1)/2^n = 1/2

c.s. on

▲

0

▼

Ans: 1/2 Lemma 1: For any n >= 1, sum_(i even, 0 = 1) coin tosses, P(getting even number of Heads) = 2^(n-1)/2^n = 1/2

c.s. on

▲

0

▼

Ans: 1/2 Lemma 1: For any n larger than 1, sum_(i even, i from 0 to n) n Choose i = sum_(j odd, j from 0 to n) n Choose j Proof of Lemma 1: For odd n, it is obviously true since "n Choose r = n Choose (n-r)". If n is odd and r is even, then (n-r) is odd, vice versa. Hence, with n odd, sum w.r.t. all even i is equal to sum w.r.t. all odd j. For even n, we may deduce that "sum_(i even, i from 0 to n) n Choose i = sum_(r from 0 to (n-1)) (n-1) Choose r = sum_(j odd, j from 0 to n) n Choose j" In other words, for n even, sum of (even number)-terms at the nth layer of the Pascal's Triangle is equal to sum of all terms at the (n-1)th layer of the Pascal's Triangle. For example, 1 3 3 1 3rd layer of Pascal's Triangle 1 4 6 4 1 4th layer of Pascal's Triangle 1+6+1 = 1+3+3+1 = 4+4 Since sum_(i even, i from 0 to n) n Choose i = sum_(j odd, j from 0 to n) n Choose j, and obviously sum_(i even, i from 0 to n) n Choose i + sum_(j odd, j from 0 to n) n Choose j = 2^n, we have sum_(i even, i from 0 to n) n Choose i = 2^(n-1) Therefore, in n (larger than or equal to 1) coin tosses, P(getting even number of Heads) = 2^(n-1)/2^n = 1/2

c.s. on

▲

0

▼

There is a bijection between the set of coin tosses with an even number of heads and those with an odd number of heads. (One can easily prove this by induction, being true for n=1, and the induction step is trivial because the even sets are carried over to the odd sets and vice versa.) Hence p=1/2.

Maximilian on

▲

2

▼

1/2. Let p_(e,n) be the probability that we have an even number of heads given n tosses of a coin. We have the recursion relation p_(e,n) = (prob to get heads on toss N AND we have odd number of heads after n-1 tosses) + (prob to get tails on toss N AND we have even number of heads after n-1 tosses) = 1/2 p(o, n-1) + 1/2 p(e,n-1). But p(o, n-1) = 1 - p(e, n-1), so p_(e,n) = 1/2 (1-p(e, n-1)) + 1/2 p_(e, n-1) = 1/2.

fermi on

▲

0

▼

( (2^50)+1) / (2^100) Even numbers include 0 heads to 100 heads. There exist 50% even complements and 50% odd complements from 1-100. So half our sample space. Now we do our zero case which is no heads and there is only 1 outcome.

Anonymous on

▲

0

▼

all your answers are wrong. Just consider a game with 4 coins: Overall you have 2^4 = 16 differten combinations. The fisable combinations with 50/50 head tails are: 1100 1010 1001 0110 0101 0011 So just 6 out of 16 which gives us a prob of 3/8 The formula of Anonym tells us 1) (2^2 + 1)/(2^4) = 5/16 or 2) (2^3 + 1) /(2^4) = 9/16 and the solution of ky tells us P(odd after 3)*0.5 + P(even after 3)*0.5 but forgets about 111x. However, we can calculate the probability distribution of all tosses. Just model 0 = tail, 1 = head and look at the sum of all coin-tosses S. The law of large numbers tells us that the expression [S-E(Coin-toss)]/sqrt(100*0.25) approximately normal distributed. Thus, S ~ N(1/2,100*25) and consequently we see on average 1:1 head and tails.

phunfactory on

## Add Answers or Comments

To comment on this, Sign In or Sign Up.