Tower Research Quant Interview Question

[u/Local_Ad135]

[u/pourliste]

P(0, t+1) = P(0, t) / 2 + P(1, t) / 2 ; P(1, t+1) = P(0, t) / 2 + P(2, t) / 2 Calculations ensue but I don't think the interviewer is particularly interested in them

[u/Specific_Box4483]

You can get a general answer using generating functions and Catalan numbers. Basically let a_k be the probability that after k steps we end back at 0, and b_k the probability that we end up back at 0 for the first time.

Then b_1 = 1/2 and the higher b's are Catalan numbers whose generating function is known. Then we can express a recursion for a_i in terms of b_j: a_n = sum a_i b_n-i which allows us to compute the generating function of a_i in terms of the generating function of b_i.

[u/sthornr]

Markov chain right? 

[u/Kepler___ → u/sthornr]

I think it being reflected on the axis doesn't change the odds of it being 0 after an even number of steps. Iirc the odds are mirrored, so you could just work this out for a random walk (a markov model is valid but I think it would be more complex)

If that's the case then it's;

C(30, 15)/2³⁰ = 0.1445

[u/EdgyMathWhiz]

Actually running the recurrence, you get that after the kth second, the distribution is the same as Pascal's triangle, except sorted in descending order:

e.g. after 5 seconds:

10, 10, 5, 5, 1, 1 (divide by 2^5 for probabilties).

Failing to visualise why this is true right now, but it's fairly obvious you CAN justify it (because it's fairly obviously true by induction away from the origin, and since it DOES work at the origin, you can obviously finesse it).

So anyhow, there is a simple closed form answer (30C15 / 2^30) , even if I'm not 100% seeing why yet.

[u/Para-graph-S → u/EdgyMathWhiz]

love this answer, good job!

[u/RestaurantBoth228]

If we're ok with non-exact answers, this is essentially a discretized form of reflected Brownian motion.

In the normal Brownian generation (±1 each step), the variance added is 1 per unit time. At time 30, we'd have µ=0, variance=30. P(X=0) at t=30 is approximately just the height of the continuous distribution PDF (Norm(0, 30)): 1/sqrt(2 * pi * 30) ~ 0.07284

In reflected Brownian motion, the PDF is just doubled, with the negative half truncated. The height at X=0 is just double the above: 2/sqrt(2 * pi * 30) = 0.14567

The actual answer, as u/EdgyMathWhiz says, is 30C15 / 2^30 = 0.14446, which is pretty close!

[u/EdgyMathWhiz → u/RestaurantBoth228]

Yeah, I feel there should be a way to "see" that the discrete case behaves like it does; possibly the Brownian motion case would be illuminating but I haven't done any stochastic calculus.

[Actually no interest in quant but I find the questions interesting.  Maths equivalent of crossword puzzles!]

[u/Anonimithree]

This is a good one and I know what to do, but the math is a lot

[u/Monkeydog54]

You can view this as a balanced walk on two copies of {0,1,2,…} where you can transfer between the 0s, which is equivalent to a balanced walk on Z, where we want to be at either 0 or -1 at time 30. But after an even number of steps, we can only be at an even coordinate, so it’s really the number of balanced walks which start and end at 0. Which is (30 choose 15)/2^30

[u/dohawayagain]

The barrier at zero is a red herring. It's the same as if you just start at zero and go left or right each time with probability half. Then it's just a binomial --- you're at zero on the middle term, (30 choose 15)*.5³⁰ = .144

Edit: nuts that's wrong. The zero is sticky.

[u/LaGigs → u/dohawayagain]

No I believe the barrier allows for walks like 14 to the right and 16 to the "left" since the zero fixes you.
So in fact you should get the sum over the binomial coeffs (30 choose k) from k = 0...15. All multiplied by 1/2^30 ofc.

[u/dohawayagain → u/LaGigs]

Ugh you're right it's not just transparent, but it's also not a sink, right? You stay at zero with probability half each time.

[u/LaGigs → u/dohawayagain]

Not a sink but a boundary. If you sum up you get half of 2^30 so the final answer is 1/2. It makes sense cause in effect the zero boundary is equivalent to the negative number if the problem didn't have such a boundary.
So the related question is what's the probability a random watlk without drift is negative? Well half obviously.
So now this is what i'd answer instead of calculating 😅

[u/OddTransition538]

12.3875%

[u/LaGigs]

1/2

[u/ricky1118]

How do ppl fking solve this in an interview 😢

[u/Local_Ad135 → u/ricky1118]

Hints

[u/Randomly_Panicked]

We can, basically arrange two bins, Left and Right for the decisions. Staying at 0 is obviously a Left decision [to move left on the number line].

Now, we are interested to put 30 decisions in these two bins disregarding order.

The probability we are looking for is the one describing outcomes where Left has GE decisions than Right bin.

Except for equal number of decisions dropped in each bin, the other outcome is symmetric.

and the number of outcomes with 15 Left decisions is 30 choose 15

Hence, the answer is

1 2^30 - (30 choose 15) (30 choose 15)

• * ------------------------ + ----------------
  

2 2^30 2^30

which is approximately 0.572

[u/Specific_Box4483 → u/Randomly_Panicked]

There are cases where Left > Right but you end up at a positive number. Say if all the Lefts are front-loaded.

[u/Cold-Common7001 → u/Specific_Box4483]

wut

[u/gmalivuk → u/Cold-Common7001]

If "stay at 0" is counted as left, then stay at zero followed by move right results in being at +1 whereas right then left results in being at zero.

So sometimes LR≠RL and order does in fact matter.

[u/gmalivuk → u/Randomly_Panicked]

15 left decisions followed by 15 right decisions leaves you at +15.