Research associate Interview Questions in New York, NY

scheme: guess when the first one is black, p(guess) x p(right) x 1=1/2 x 26/51=13/51

0.5, just turn the first card to see if it's red. I think it's more about trading psychology. If you don't know where the price is going, just get out of the market asap. Don't expect anything.

The problem should be random draw card and dont put it back. Every draw you have one chance to guess. So the strategy is after first draw you random guess it's red. If correct you get one dollar, next draw you know there is less red than black. So you guess black on next draw. Else if first guess you are wrong, you guess red on next round. It's all about conditioning on the information you know from the previous drawings

This should be similar to the brainteaser about "picking an optimal place in the queue; if you are the first person whose birthday is the same as anyone in front of you, you win a free ticket." So in this case we want to find n such that the probability P(first n cards are black)*P(n+1th card is red | first n cards are black) is maximized, and call the n+1th card?

The problem statement is not very clear. What I understand is: you take one card at a time, you can choose to guess, or you can look at it. If you guess, then if it's red, you gain $1. And whatever the result, after the guess, game over. The answer is then $0.5, and under whatever strategy you use. Suppose there is x red y black, if you guess, your chance of winning is x/(x+y). If you don't, and look at the card, and flip the next one, your chance of winning is x/(x+y)*(x-1)/(x+y-1) + y/(x+y)*x/(x+y-1) = x/(x+y), which is the same. A rigorous proof should obviously done by induction and start from x,y=0,1.

The answer above is not 100% correct, for second scenario, if you don't guess, and only look, the total probability of getting red is indeed the same. However, the fact that you look at the card means you know if the probability of getting red is x/(x+y)*(x-1)/(x+y-1) or y/(x+y)*x/(x+y-1). Therefore, this argument only holds if you don't get to look at the card, or have any knowledge of what card you passed

Doesn't matter what strategy you use. The probability is 1/2. It's a consequence of the Optional Stopping Theorem. The percent of cards that are left in the deck at each time is a martingale. Choosing when to stop and guess red is a stopping time. The expected value of a martingale at a stopping time is equal to the initial value, which is 1/2.

My strategy was to always pick that colour, which has been taken less time during the previous picks. Naturally, that colour has a higher probability, because there are more still in the deck. In the model, n = the number of cards which has already been chosen, k = the number of black cards out of n, and m = min(k, n-k) i.e. the number of black cards out of n, if less black cards have been taken and the number of red cards out n if red cards have been taken less times. After n takes, we can face n+1 different situations, i.e. k = 0,1,2, ..., n. To calculate the expected value of the whole game we are interested in the probability that we face the given situation which can be computed with combination and the probability of winning the next pick. Every situation has the probability (n over m)/2^n, since every outcome can happen in (n over m) ways, and the number of all of the possible outcomes is 2^n. Then in that given situation the probability of winning is (26-m)/(52-n), because there are 26-m cards of the chosen colour in the deck which has 52-n cards in it. So combining them [(n over m)/2^n]*[(26-m)/(52-n)]. Then we have to sum over k from 0 to n, and then sum again over n from 0 to 51. (After the 52. pick we don't have to choose therefore we only sum to 51) I hope it's not that messy without proper math signs. After all, this is a bit too much of computation, so I wrote it quickly in Python and got 37.2856419726 which is a significant improvement compared to a basic strategy when you always choose the same colour.

dynamic programming, let E(R,B) means the expected gain for R red and B blue remain, and the strategy will be guess whichever is more in the rest. E(0,B)=B for all Bs, E(R,0)=R for all Rs. E(R,B)=[max(R,B)+R*E(R-1,B)+B*E(R,B-1)]/(R+B). I don't know how to estimate E(26,26) quickly.

The question, to me, is not clear. Perhaps on purpose. If so, the best answers would involve asking for clarification.

http://wolfr.am/1i1XT4P

How'd you get 0.98 and 0.46?

NND correlation matrix --> det(\Sigma)>=0 --> 0.98 and 0.46

minimum: 0.9*0.8+sqrt(1-0.9^2)*sqrt(1-0.8^2) = 0.9815 maximum: 0.9*0.8-sqrt(1-0.9^2)*sqrt(1-0.8^2) = 0.4585

How do you know this

@curious_cat I think that only implies that the third deck is better than the second deck (the second has 13/13 while the first has 26/26).

1) P(win | 52-card deck) = 25/51. P(win | even 26-card deck) = 12/25. 52-card deck is better. 2) P(win | n-red cards in random 26-card deck) = (n/26 * ((n-1) / 25)) + ((26-n) / 26 * ((26-n-1) / 25)) = (n^2) / 325 - (2n / 25) + 1. Taking the derivative and solving for the root: P' = 2n / 325 - 2 / 25 = 0 -> n = 13, which is a minimum. Interpretation: having equal numbers of red and black cards in the deck MINIMIZES your chances of winning. Because the last deck is the same as the second deck (26 cards, split evenly red/black) except it may have an uneven number, this last (randomly selected) deck is better than the evely-split deck, but is it better than the 52-card deck? For this, we use the Hypergeometric Distribution (like the Binomial distribution, but for trials without replacement) to look at the odds of getting a 26-card deck with n red cards: P(selecting n red cards for random 26-card deck) = [ (52-26) C (26-n) ] * [ 26 C n ] / [52 C 26] = (2^43 * 3^17 * 5^12 * 7^4 * 11^4 * 13^4 * 17 * 19^2 * 23^2) / (29 * 31 * 37 * 41 * 43 * 47 * (n!)^2 * ((26-n)!)^2). From here, all that's left to do is combine these probabilities with the probability of winning [from above, P(win | n-red cards in deck) = (n^2) / 325 - (2n / 25) + 1] with each deck that contains 0 through 26 red cards (n => {0,26}). If this is larger than 25/51, then we can say definitively that we would prefer the randomly selected 26-card deck to the even 52-card deck. However, doing this out reveals that the probability of winning with the randomly selected deck = 25/51. Therefore, odds of winning are THE SAME with either the first (even 52-card deck) or the last (26-card deck, randomly selected from an even 52-card deck). Imagine, all that math to prove a simple equality! :) Q.E.D.

the 3rd deck is the same as the 1st deck we do not need to calculate it by hand P(I randomly pick 2 cards in a 52 deck) = P(I always pick 2 cards on the top of the 52 cards’ deck) = P(You shuffle the deck, then I pick 2 cards on the top) = P(You shuffle the deck, you throw away the bottom half deck, then I pick 2 cards on the top) = P(Picking a 26 cards’ random deck, then I pick 2 cards on the top) = P(Picking a 26 cards’ random deck, then I randomly choose 2 cards in the 26 cards deck)

in this logic - even if you only pick a 4 cards' deck randomly from the 52 cards deck for me to choose 2 cards - it's the same probability as if I choose 2 randomly from the 52 cards' deck directly .

The 3rd deck is better. Suppose the 3rd deck has k red cards. The probability of getting 2 cards of the same colour is (C(k,2) + C(26-k,2))/C(26,2). It is easy to see that this is minimum for k = 13, which is the first deck. So essentially any random 26 cards is at-least as good as a 13-13 split.

Split a blind draw into two draws doesnt change your distribution.

These answers are all overkill, the answers are obvious by intuition which are good enough (perhaps even better) for an interview. 1. Obviously deck 1 is better , because taking away your first card has a smaller impact on the ratio of cards left of the same colour. 2. Obviously they're the same. Deck 1 is equivalent to shuffling a deck and taking the top 2 cards, Deck 3 is equivalent to shuffling a deck, taking the top 13 cards of that and then taking the top 2 cards of that.

First option is slightly better. One way to argue if the 26 random cards are even, then its the same as the 2nd situation, but if its uneven (12R 14B), then probability is 12/26 * 11/25 + 14/26 * 13/25 > the probability of the 2nd option. And the probability just gets better as the draw is more skewed. Another way to argue is the 1st option is picking from a deck of 52 even cards, and 2nd option is picking from 26. First option probability is 25/51, second option is 12/25. As u choose from more and more cards, the probability increases and tends towards 1/2.

Intuitive Solution. 26 is an arbitrary selection. For a two card case: Case 2: deck of two cards. 1 black and 1 white card gives P = 0. Case 1: pick two cards from 52. P > 0.

Random is better. Here is the solution: For latter game(fixed 26 cards with equal red and black), the probability to win is: p2=1-13*13/C(2,26)=0.48. (1-probability of picking two different color cards) For the random game, although the expectations of number of red card and black card are equal, but they may not be the exactly same. Assume R is the number of red cards, and B is the number of black cards. with constraints: R+B=26 then the probability to win for this game becomes: p1=1-R*B/C(2,26) With the constraints R+B=26, then R*B = p2 always.

fix is better, since in random case more colors are mixed in. The prob of hitting same color pair got lowered. Keep in mind a deck of cards is composed of 4 colors and each of 13 cards. So that 12+14 is not happening.

oops I got this wrong. random is better. 12+14 is happening. We are talking about colors...

add an extra 1 to the previous answer

For part A), the answer is 1+1/2+1/3+...+1/10. For part B), the answer is 1+1/3+1/5+...+1/19. Explanations: For part A), ctofmtcristo has the right approach but with a typo in the equation for E[n]. To obtain the expected number of loops, we note that the first red has a 1/n chance of connecting with its opposite blue end (and forming a loop) and a (n-1)/n chance of connecting with a different rope's blue end (and not yet forming a loop), so E[n] = 1/n*(1+E[n-1]) + (n-1)/n*E[n-1] = 1/n + E[n-1], with base case E[1]=1. Then, by induction, we get E[n] = 1+1/2+1/3+...+1/n. Part B) is similar. We note that the first end now has 2n-1 possible ends to connect to, of which 1 of them is its opposite end and 2n-2 of them belong to a different rope. Then, E[n] = 1/(2n-1)*(1+E[n-1]) + (2n-2)/(2n-1)*E[n-1] = 1/(2n-1) + E[n-1], with base case E(1)=1. By induction, E[n] = 1+1/3+1/5+...+1/(2n-1).

Ed's anwser is not right. Just check for the case of 3 pairs. So total cases is 3!=6. 1 case with 3 loops, 2 cases with all wrongly attached, and 3 cases with 1 loop. so expected value is (3/6)*(1) + (1/6)*(3) = 6/6 = 1... and Eds anwser gives 1+1/2 +1/3 = 11/6, which is wrong clearly.

Timi, you are missing the fact that if they are "all wrongly attached" then they form a loop. Similarly, the case you are thinking of "with 1 loop" actually has 2 loops. The correct answer is still 11/6.

it's like you need to give heads another 'chance' (to double it's probability to match tails) if you get a tail, stop if you get a head, roll again and take the second result

Swift and anon are both correct, but Swift's solution is twice as efficient because 8/9 of the time, Swift only requires 2 flips, while 4/9 of the time, anon requires only two flips. Indeed, for Swift, we can show that the expected number of flips is 2.25, while for anon, the expected number of flips is double that, 4.5. Let X be the expected number of flips. Then, for Swift, EX = 2 + 1/9*EX ==> EX = 18/8 = 2.25, while for anon, EX = 2 + 5/9*EX ==> EX = 18/4=4.5.

All of these type of problems can be solved by symmetry. Take two processes to flip each coin until it’s getting head.

Here is another approach to this problem using conditional expectation. Let X be the minimum number of flips needed to get the first run of HHT. Let HH denote the event that the first two flips land on heads and similarly define TH, HT, TT. Then using a well known theorem, we can write E[X] as E[X] = E[X | HT] P(HT) + E[X | TT] P(TT) + E[X | HH] P(HH) + E[X | TH] P(TH) where E[X | Z] is the conditional expectation of random variable X with respect to random variable Z and P is the probability measure. It is easy to see that E[X | HT] = E[X | TT] = E[X] + 2, and P(HH) = P(HT) = P(TT) = P(HT) = 0.25. Using the above theorem for E[X | HH], E[X | TH] and a little observation, we obtain E[X | HH] = 4 and E[X | TH] = 0.5 * E[X] + 4 The first equation then implies E[X] = 8.

8 is the correct answer...this can be solved by viewing it as a renewal reward process. Suppose we get a reward 1 each time we get HHT, then intuitively in the long run we can get 1/8 (=p(H)p(H)p(T)) unit of reward per unit time. By the central limit theorem for renewal reward process, this should be equal to the expectation of reward for each period over the expectation of hitting time. But the expected reward for each period is just 1, so the expectation of hitting time is 8. This can be generalized to HTH, which is more interesting, because the reward for each period is not 1 anymore: if we get a HTH from previous period, then if the start of the new period is TH, we actually get HTH TH, the reward here should be 2. So the expected reward in this case is 1+p(T)p(H) = 5/4, and thus the expected hitting time is 10.

HHT = HH + T. After 2 consecutive heads (with E[HH] = 6), if we get H, we continue as we still have 2 consecutive H's, else we get desired HHT. So, E[T] = 2 and therefore, E[HHT] = E[HH+T] = E[HH] + E[T] = 6 + 2 = 8