Checking if a coin is Fair | Quant Interview Questions
ฝัง
- เผยแพร่เมื่อ 20 ก.ค. 2024
- 🔢 Support this channel: / atypicalquant
🔢 Code and more: atypicalquant.net/quant-inter...
🔢 Buymeacoffee: www.buymeacoffee.com/atypical...
For business inquiries, please use the email address displayed in the about tab (in the channel overview).
------------------
Question: You receive a coin that is either fair (with a 50% probability of getting heads) or unfair (with a 42% probability). How can you detect the fair coin? And after how many flips can you assuredly say that?
------------------
Special thanks to our Patreons:
Shehryar Saroya
------------------
Timecodes
00:00 - Question
00:18 - Understanding
02:14 - Solution
04:10 - Coding Check
05:04 - Outro
------------------
Book recommendations: atypicalquant.net/quant-books/
These should cover all the types of interview problems that one encounters at hedge funds such as Two Sigma (2sigma), Citadel, WorldQuant, BlackRock, Optiver, Jane Street, Akuna Capital, Hudson River Trading, etc.
------------------
These animations are largely made using manim: github.com/3b1b/manim. Special thanks to 3Blue1Brown and the manim community!
------------------
Social media:
Reddit: / atypicalquant
#quant #trader #researcher #analyst #developer #quantitativeresearch #finance #interviewquestions #datascientist #faang #datascience
#coin #fair #biased #confidencemathematics #confidenceinterval
#3blue1brown #manim
#python #pythonprogramming
Nice video. One minor thing: you choose alpha-level to be 0.1 to construct CI, but the resulting confidence level is 95%. I suppose it's because the criterion in making decisions is essentially one sided, so effective alpha-level is indeed 0.05. It might be a bit harder to sort this logic out.
This is amazing! I have an interview at D.E shaw this week, and I'm so happy that you released another video. Do you have any last-minute tips? :)
Hey! Happy to hear and best of luck tomorrow :).
Here are, from the top of my head, some last minute tips:
1) On question/problem solving:
i) I think the most essential thing that will help you find the solution is to spend some time understanding it thoroughly, potentially by looking at particular cases/simplifications (i.e. moving 3d to 2d). I do emphasize this in most videos.
ii) From my experience (both as an interview and as an interviewer), It's usually better if you think out loud and share partial ideas and results rather than working on a piece of paper until you have a 100% solution. This way, you'll get tips and be informed if you're going way off.
2) On communication:
Formally or not, your communication skills are taken into account. It's usually a good idea to be humble, engaged in conversation and explain your ideas clearly.
If you have the option to ask questions, you really should do so. Inquiring about things such as the future team, the technologies, use ML, MLOps, AUM, will show that you're interested.
3) On preparation:
Consider reviewing anything you've struggled with in the past / you're not 100% comfortable with (i.e. financial concepts, data structures & algorithms, statistics, ML).
@Rickard_Martensson Hey! I am new to the quant space and just recently started applying for quant roles. My interview prep is reasonably good but I am not getting call backs for OAs/interviews. Do you have any tips?
@@atypicalquant Hey! I am new to the quant space and just recently started applying for quant roles. My interview prep is reasonably good but I am not getting call backs for OAs/interviews. Do you have any tips?
Great video and explanation. I have been wondering about similar questions for a little while. I never felt comfortable using confidence intervals because it depends on the CLT, which is an asymptotic result. But the question asks us to find the number of coin tosses, which is finite. I could never wrap my head around this hand wavy argument. So I use Concentration inequality based confidence intervals which hold for finite samples. Check Hoeffding's inequality. But my interviewers at quant finance firms have hardly heard of concentration bounds. So, I use them at my own peril 😥.
A similar idea to what you are suggesting is to use the Berry-Esseen theorem which also provides a measure of the rate of comvergence (and error) for the limit in the CLT.
But, more importantly, while the CLT is an asymptotic result, this does not negate its usefulness in practice, especially for large enough sample sizes. But, if you feel more comfortable using a more quantitative result, I think that works as well :D
Can we do it more efficiently? What if, instead of choosing n=418, we chose a slightly smaller n to begin with? Let's call this n1. Then, if the fraction of heads lies within the fair coin's 95% interval BUT NOT in within the unfair coin's 95% interval, we know it's the fair coin. Likewise, if we had the opposite result, we know that we had tossed an unfair coin. It's only when the fraction of heads lies in the region common to both confidence intervals that we have a problem, right? If the fraction of heads lies in this region, we can just toss the coins the remaining (418-n1) times and do the nice analysis detailed in the video. But on average, we would need fewer than 418 tosses; if the region common to both confidence intervals is small, the expected number of tosses would be pretty close to n1.
In this case, we broke up the whole process into two parts - one where we tossed coin n1 times, and one where we tossed it 418-n1 times. But we can also break it up into more and finer parts. We can monitor the fraction of heads as it changes for every single toss, and as soon as this fraction lies in the confidence interval of one coin but the other, we exit the process. Else, we continue with more coin tosses. Won't this lead to fewer coin tosses on average?
Well the larger n gets, the smaller the interval becomes due to law of large numbers. Following the logic in the video, n=418 is the minimal coin tosses which distinguishes values will fall into one interval over the other. Perhaps if you decreased the confidence level you could achieve it quicker, but then the hypothesis chosen in the video is 95% confidence
As per @George's comment, reducing the value of new only decreases our confidence.
For example, after two toss, the proportion of heads is 0, 1 or 0.5 regardless of which coin you have. In this case, following your suggestion, you can make a decision, since 0.5 and 1 are pointing towards the fair one, and 0 towards the unfair. Clearly, this strategy will not have a success rate that is very high.
Thanks for the video. In the question we are given that the probability of the biased coin has a smaller chance of heads than the fair coin. Can I ask why we perform a two-tailed test rather than a one-tailed test? If we find a large proportion of heads it may not be in the confidence interval of the biased coin but should still be in the confidence interval of the fair coin
I chose the two tailed test for its ease of use. You can try and create a strategy with the one tailed one, and check the minimum number of tosses needed to get the desired accuracy. It might not be that different from the one resulting from the two-tailed test.
Would using concentration inequalities to solve this be a valid approach too?
Yes, this is also an alternative to the solution we provided!
hello, can you list some books about statistics, probability, and combinatorics?
am pretty good at calculus and kinda suck at stats but im starting to think quant stuff is interesting and want to learn more
thank you!
Some good started books can be found here: atypicalquant.net/quant-books/, where I give some suggestions for both theoretical books and some interview question books. Hope this helps and good luck on your quant journey!
Hi thanks a lot for the videos! Here are some interesting comments that I learned from the video. The 418 is empirical. When you use the central limit theorem there is an approximation error of O(1/sqrt{n}) to the probability that changes the lower bound on n if you want to answer the question rigorously. In particular, you can use two sided Hoeffding’s inequality to obtain a rigorous confidence interval. Let X_i be 1 with prob p and 0 otherwise. Consider the empirical mean S_n = (1/n) * sum_{i=1^n} X_i, the confidence interval is [p - t, p + t], where t= sqrt(log (2/epsilon) / (2*n)), with probability 1 - epsilon. Pick epsilon = 0.05. For n = 1200 the interval for the 0.42 coin is [0.38, 0.4598] and for the 0.5 coin is [0.4601, 0.5398]. So with probability 95% the intervals do not overlap. Now note that 1160 seems worse than 418 but that's because there is no approximation errors hidden in the above answer. This is actually a very interesting case that shows how empirical evaluations could differ from rigorous bounds obtained by Hoeffding’s inequality. You can probably avoid the two-side inequality and improve the lower bound on n a little bit but it will still be around 940 instead of 418.
As stated in the beginning of the video, there can be no “rigorous” answer to this question. Also, depending on the strategy you decide to use, the minimum number of tosses needed to achieve a particular level of confidence can change.
Regarding the value of 940 that you get, have you tried simulating tosses with it? If we get 95% correct guesses after 418 flips, you would expect to get a higher value after 940. So this number doesn’t actually provide the minimum number of tosses for an accuracy of 95%.
@@atypicalquant Hi, by rigorous I guess you mean an "exact" threshold. If that's the case, then that's true. However, the answer by Hoeffding’s is rigorous mathematically but as you have noticed it is a bit loose. It guarantees the result with very high probability though.
@@randomdude6205 I think OP has a great point there about the outcome of the simulation. It doesnt matter what method you use to calculate the number of tosses, the simulation turns out that at 418 tosses we have a 95% accuracy. your 940 answer will have a much higher accuracy.
@@jackliu1579 Yeah, but it's just a simulation... Anyway, I got rejected, so I can't be bothered more really🙂.
Hi mam, I love your content!, could you please suggest where one can learn finance?
I do have some resources for finance on my website, in the section of books I recommend
hey!
Im a CS under grad
and i want to prepare for Quant analyst interview
considering i have a couple years in my hand
other than getting good with my own curriculum
what else should i focus on like for example finance ,problem solving, trading and maths
and how so i go about it as in what all steps should i follow and resources should i use?
I'd really appreciate your help
thank you
Hey.
It's great that you already made up your mind and you have plenty of time to learn and prepare.
I would suggest you start with the books that I recommend here atypicalquant.net/quant-books/. If you are looking for some recommendations in a different particular area, I can also try to help with that; but, for a start, it's really crucial to get good foundations (via Maths & Stats).
If you're in CS you would be comfortable with the coding part. You're likely to find dynamic programming questions. It would be wise to take electives on probability and statistics, regression & time series analysis. Usually you won't be asked questions on finance but it's good to know some basics on options, types, put call parity, Black Scholes model, Ito's lemma. Apart from that you should practice questions on conditional probability, distributions, Bayes theorem, random walk, Martingale's.
hey sanja im currently undergrad cs and finance pls if you have any tips what i should learn as cs im confortable with coding part but i lack some math and stat pls if you can help me any recommended books course, subject ...
Does confidence interval calculated are mismatched for fair and biased??
I'm not sure I understand the question, what exactly do you want to know about the two confidence intervals?
@@atypicalquant lol i dont understand his question either