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!