Discrete Time Markov Chain

Let be a discrete time Markov chain on state space S.
Charikaar tosses a fair coin. If it shows heads he takes one step North. If it shows tails he takes one step South. This process is performed repeatedly.
Show that the probability that after 2k coin tosses Charikaar is back where he started is
I think this is Random walk on integers but I am not sure what is the state space in this example ... can the state space be S={.....,-3,-2,-1,0,1,2,3,.....}? he starts at zero and moves left and right? Can you please help me get started with the answer. Thanks

This looks like one of those problems where you can use a combinatorial argument. Even if your instructor does not accept it, this it will give intuition on how to solve.

Try to describe the sample space and event space.

I don't know what is State space equal to in this case so can't really get started!

thanks

Do it like this:

At time t_0 he is where he started with p=1.

On the next step he moves in one of the two directions, so he is back with p=0

N
|
x_0
|
S

At time 3 he is :
P(gets back at time 3)= p(Goes back|Went North)P(Went North) + p(Goes back|Went South)P(Went South) = (1/2)^2 + (1/2)^2 = 1/2

At time 4 he can be in on of the following places

N (here) p(Gets back|here)=0
|
here p(Gets back|here)= 1/2
|
X_0 (here) p(gets back)=0
|
here p(Gets back|here)= 1/2
|
S (here) p(Gets back|here)=0

You tell me the p(Gets back) for this one. Note that you can use symmetry and the fact that if he can not get back from a certain position, being at that position is not included in the desired probability.

If you must prove this, use induction. Here is your base case. Although you probably don't and can just say the result follows.