Random Summation until One | Quant Interview Questions
ฝัง
- เผยแพร่เมื่อ 20 ก.ค. 2024
- 🔢 Support this channel: / atypicalquant
🔢 Code and more: atypicalquant.net/quant-inter...
🔢 Buy me a Coffee: www.buymeacoffee.com/atypical...
For business inquiries, please use the email address displayed in the about tab (in the channel overview).
------------------
Question: You play a game where you sum independent identically distributed uniform random variables over the interval [0,1]. The first time the sum exceeds one, record the count of needed variables.
What is the expected number of variables?
------------------
Special thanks to our Patreons:
Anik Roy
Shehryar Saroya
------------------
Timecodes
00:00 - Question
00:18 - Understanding the Problem
00:58 - Solution
01:57 - Geometric Interpretation
03:21 - Hyperspaces and Final answer
07:05 - Coding Check
07:17 - 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
#probability #hyperspace #uniform #randomvariables #expectation #series #convergence
#3blue1brown #manim
![ไหล่อ่อน (Soft Shoulder) - Atom ชนกันต์ [OFFICIAL MV]](http://i.ytimg.com/vi/HUWl53msBQY/mqdefault.jpg)
The first time I saw this problem, my approach was to use a discretised uniform(0,1) taking 1 of N values (1/N, 2/N, ... , 1) and then finding the expected hitting time of a state greater than or equal to 1 using a Markov chain. Then I took the limit as N goes to infinity and I was left with e. Glad to know there are other nice ways of solving this :)
How to solve using markov chains?? Can you explain
Thank you for another great video.
My approach was to recognise that the the sum of k iid variables taken from U(0,1) follow the Irwin-Hall distribution. Then I looked up the CDF on Wikipedia to calculate the answer. But your answer is much better if the interviewer asks you to derive the answer from first principles.
Great job! A lot of the times the first response will be enough, but it's a good idea to be able to solve almost everything from as basic principles as possible.
A solution I was able to do in 5-10 minutes is slightly different: Let E(x) be number of uniform(0,1) to go above x, for numbers smaller than 1. We quickly get a recursion E(x)=1+integral_from_0_to_x(E(t)dt). And guess e^x to avoid doing calculus 😅
Awesome problem and beautiful solution! Thank you very much!
Thank you, glad to hear you enjoyed it!!
Follow up question: could you make a video on simplexes? I notice that most resources offer the Simplex Algorithm for Linear Programming but not necessarily a geometric intuition tied with what you brought here. Additionally after reading up on the topic a bit, I found two counterintuitive responses for what the volume of a simplex is: one version I saw was 1/n! and another suggested sqrt(n+1)/(n! * sqrt(2^n)).
I didn't cover this during my education so I am not sure if I am asking the right question here, but I am fairly confused about how to approach this. Also thank you for the quality videos! This channel is truly unique!
Hey Robert! Thank you for your kind feedback as well for your suggestion to make a video on simplexes; I'll definitely consider it.
With regards to your question, the latter is the volume of a regular n-simplex (of unit side length), which is not our case; we are also proving, at 6:50, that the former is what we should use here.
Like with most things in math, to better understand why that is, as well as the formulas, take a look at the simple cases (n=2, n=3). Compare our 3:16 figures with www.math.brown.edu/tbanchof/Beyond3d/chapter8/section03.html. For example, in our n=2, we have a square triangle, with area 1/2, while the regular 2-simplex will be an equilateral triangle of area sqrt{3}/4.
So the question asked for the Expected number of iid Uniform(0,1) random variables we need, for the sum to exceed 1, for which we got 'e'. Does this mean we round to 3 since we cannot have a partial random variable? Additionally I would like your opinion on my rather simple approach: The expectation of a X~Uniform(0,1) random variable E[X] = 0.5. If we need "n" number of random variables, then we must find "n" such that n * E[X] > 1, which consequently is between 2 and 3, but we choose to 3 since the condition is to exceed, not equal, 1. What are your thoughts/flaws of this approach?
While you cannot sum 'e' random variables, this does not imply that you need to round this value. For example, the average(read 'expected') number of cars per household in UK is 1.45. You do not round this to 1 (or 2) since you cannot have half a car. In this case, the expectation measures the average number of RVs needed for the sum to exceed one.
As for your solution, you are right that it points to an expected value larger than 2, but this is not enough to conclude the exact value of it.
Thanks for the video! I wonder if there's another simple way to obtain the formulae for hyperpyramid volume, maybe using induction. Yet another problem to think about!
Thank you for watching!
There is actually (at least) another way to find the volume of the hyperpyramid, using induction and integration. I considered including it in the video, but I think I decided that this solution is just a bit more interesting. If you want to read a bit about the solution using induction, here is a great explanation ( www.mathpages.com/home/kmath664/kmath664.htm ) for it!
@@atypicalquant Thanks for your answer! The link doesn't work though.
@@alpatovivan Hey, updated the link above; it was not working as it was including the ')'.
is it solvable for X~N(0,1)?
I am trying to sum CDF(1) for every N(0, 1*n), but my sum diverges
You are correct, there is no limit to the series. You can check that by simulating as well, when summing N(0,1), you have no guarantee that you will reach one. Since the mean is always 0, and the standard deviation increases, it is in line with the intuition.
Actually, the rearringing part is somewhat tougher ig, rest is doable
It might be, depend on how easily you can wrap your head around it.
So even knowing the answer, it takes 6 minutes to explain. Good luck solving it in 5!
You can really see while watching the video that I'm explaining the things in a lot more detail than needed for an interview. This is because the intention of the video is not the emulate the interview setting(in which you wouldn't go through particular cases or examples, most of the time), but give a thorough proof for the problem.
Moreover, even when asked to solve it in 5 minutes, interviewers would not stay at your side with a stopwatch and eject you from the room when the 5 minutes pass. If they look at the time, it would be more to see how long it takes you to get on the right track towards the solution.
@@atypicalquant my comment was a little tongue in cheek as the problem clearly builds on a familiar quant problem about sum of N uniform random variables. But for someone who isn’t familiar with the building blocks 5 minutes would be nothing!
By the way, I’ve been watching your channel as part of my interview prep and I just got my dream quant job, so thank you!!
@@adaelasm6467 hey adaela i am also preparing for quant role would be cool if you can guide me a little
If you are free please do reply