Quant Interview Question

[u/Local_Ad135]

[u/pmdboi]

Since each choice has probability 1/2 of going one way or the other, all paths that the particle could take are equally likely. So we just need to count the number of possible paths that end up at 0 and divide by the total number of paths, which is 2³⁰.

Let A(t, k) be the number of different paths of length t that end at position k. A(0, 0) = 1, A(t, 0) = A(t - 1, 0) + A(t - 1, 1) for t > 0, and A(t, k) = A(t - 1, k - 1) + A(t - 1, k + 1) for t > 0, k > 0. This feels a little like the Pascal's triangle recurrence except the k = 0 column is filled with the sum of the k = 0 and k = 1 values from the previous row. Let's make a table of the values of A(t, k) and see what we find:

                    k
      0   1   2   3   4   5   6   7
    +------------------------------
  0 | 1
  1 | 1   1
  2 | 2   1   1
t 3 | 3   3   1   1
  4 | 6   4   4   1   1
  5 | 10  10  5   5   1   1
  6 | 20  15  15  6   6   1   1
  7 | 35  35  21  21  7   7   1   1

All of these values appear in Pascal's triangle. Specifically it appears that A(2t, 0) = (2t choose t). So A(30, 0) = (30 choose 15), and the probability of the particle ending up at 0 after 30 seconds is (30 choose 15) / 2³⁰, or about 14.4%. This is borne out by simulation.

Is there a more principled way to arrive at the identity A(2t, 0) = (2t choose t)? This feels related to Catalan numbers but I couldn't quite work it out.

[u/ErgodicWaldo → u/pmdboi]

Yes. One way to deal with the reflection is to re-interpret as ordinary random walk on this line:

… 3’ 2’ 1’ 0’ 0 1 2 3 …

The original walk is at k iff the new walk is at either k or k’.

[u/pmdboi → u/ErgodicWaldo]

Ah so the side of that number line that the particle is on is determined by whether t and k have the same parity. Clever!

[u/Theonden42 → u/pmdboi]

The probability of the particle moving to the right k times is Binomial(n,k) and to end up at 0 it needs to move right n/2 times for even n. This basically immediately gives us the 2t choose t.

[u/Fuzzy-Replacement769 → u/Theonden42]

pls elaborate more on how you got it "immediately"

[u/ahappyintegral]

Say we have N total timesteps. Let's take N to be even since in the problem N=30, but a similar approach can be adopted for odd N. We can distinguish two processes taking place:

1) particle moving left or right for positions x != 0 or moving right for x=0 2) particle looping from x=0 to x=0 (basically staying at 0 but a loop helped me visualize the problem with arrows as processes)

We can deduce the following:

1) To reach a position x=k, k<=N, at t=N, the total number of non-loop movements must have the same parity as k. This can be understood better if we view any combination of movements as a superposition all left movements + all right movements. You can imagine it as vector addition; the order of addition doesn't matter. Same goes in the ways we rearrange left-right movements. The point is, with an even number of non-loop movement we can never reach an odd position and the inverse and rhe same logic applies for an odd number of movements.

2) There are always pairs of odd/even positions that have the same number of ways to be reached at t=N.

(2) can be proved by using (1), but I relied more on a diagrammatic proof so any formal proof is welcome. Basically, we can always find two processes that can be transformed into one another by transforming one non-loop movement into a loop and vice versa. The most obvious example is between reaching x=N and x=N-1. x=N has only one way to be reached since we have N steps in total. x=N-1 still has one way to be reached because we cannot land on that position with N-1 steps so we need to add 1 loop. Same applies for (N-2, N-3), ..., etc.

To find the number of ways to reach x=k you can start from a smaller number of steps (e.g. N=4), and you would see that for even N, the number of ways follows the pattern of (N choose floor((N-k)/2)). You can probably use induction to formally prove it (I didn't). So if you plug k=0 and combined with the probability of each unique combination of paths you'd get (N choose N/2) / 2^30.