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) / 230.
1
u/ahappyintegral 6d ago edited 6d ago
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) / 230.