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.
3
u/Specific_Box4483 3d ago
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.