Random points in a Triangle
An interesting and hard question asked in Quant Interview at Tower Research Capital
Before we begin this week’s Newsletter
The Puzzledquant crew has been having a blast with a new finance trivia game called Uncovered Shorts.
Uncovered Shorts sends an informative recap of each day’s quiz – sign up after playing the game. Share your results with friends through a fun snapshot and see if you can top our scores!
Now for this Week’s problem
Meet Sara, a mathematician with a special tool that generates random numbers from a uniform distribution between [0, 1]. Sara is tasked with drawing a triangle on a 2D plane with vertices at (0,0), (1,0), and (x,y). She needs to come up with an algorithm that allows her to sample points uniformly from within or on the triangle. However, she can only use the random number tool twice for each point she samples.
Question: How should Sara approach the problem to ensure all sampled points are uniformly distributed within the triangle?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
Let the random samples be m and n.
Set a=min(m,n) and b=max(m,n)
For each iteration, Sara takes two random samples, a and b, and uses them to calculate the weighted coordinates of the point.
The formulas for the coordinates are:
X=(0⋅a)+(1⋅(1−b))+((b−a)⋅x)Y=(0⋅a)+(0⋅(1−b))+((b−a)⋅y)
Thus, every point (X_0,Y_0) sampled inside the triangle has a unique solution for a and b within the range [0, 1], ensuring uniform distribution of points within the triangle.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
Another fairly natural construction, and I am not sure what precise code might benchmark in as fastest in C or C++, would be to imagine the spanned subregion formed by the 2 vectors [1,0] and [x,y] so basically if m and n were your 2 random values then if m+n<=1 we could just take [m+nx,ny] otherwise if m+n>1 then [[1+x]-[m+nx],[y]-[ny]]. Edit later: I was curious about what GPT might say if we instead ask to do this with only 1 random input which can be formalised in to a long double and it was interesting enough. Firstly, it proposed splitting 1 in to 2 by taking every other digit. Then it said instead one could convert the real number in to base 4 and basically note that because triangles can be split in to 4 similar subtriangles under constraints on Lebesgue measure uh one can go through shrinking the output region's area by a factor of 4 each time whilst zeroing in on the final output point. But I know the discretisation permits other natural enough solutions.
Good one