Suppose there is a random walk starting at the origin such that the probability to move right is $\frac13$ and the probability to move left is $\frac23$.
What is the probability to return to the origin?
Suppose there is a random walk starting at the origin such that the probability to move right is $\frac13$ and the probability to move left is $\frac23$.
What is the probability to return to the origin?
Let $P_{i\ge 0}$ be the probability of ever reaching position $x+i$ when starting from position $x$ (this is independent of $x$, since the transition probabilities are). Clearly $P_0=1$, and $P_i\rightarrow 0$ as $i\rightarrow\infty$ provided that the right-hop probability $q < 1/2$ (in this case $q = 1/3$). Otherwise, $ P_i = qP_{i-1} + (1-q)P_{i+1}, $ You can guess the solution to be of the form $P_i = \alpha^i$ for some $0 < \alpha < 1$. This turns out to satisfy the conditions if $ \alpha = q + (1-q) \alpha^2, $ which has the solution $\alpha = q/(1-q)$ in this case.
For the problem specified, you want to know the total probability of returning to the origin after the first step. If the first step is to the right (which happens with probability $q$), then you must return to the origin; if it is to the left (with probability $1-q$), then you will return to the origin with probability $P_1 = \alpha = q/(1-q)$. So the solution is $ P_{\text{return}} = q + (1-q)\alpha = q + (1-q)\frac{q}{1-q} = 2q $ for general $q<1/2$, and $P_{\text{return}} = 2/3$ in this case.
The problem you refer to is the study of return probability for a random walk on a lattice. In your case, the lattice is the 1-D lattice of integers. This problem is very well studied on general lattices. A famous theorem by Polya says that while the probability of return is $1$ for symmetric random walks (i.e., all moves are equally likely unlike in this question) in $1$ and $2$ dimensional lattices, it is strictly less than $1$ in all higher dimensions. See here for more details.
The solution posted by mjqxxxx is very clever and is perfectly valid. If you are interested in other solutions, a very systematic way of studying this problem is through the use of generating functions. See this lecture notes for more information (In fact, these notes have the solution to the problem you posed).
You can find a detailed answer for your question on WolframMathWorld.
To give an exact answer, you should define the number of steps you are interested in returning to the origin. Of course the number of steps should be even.
I have made a little "simulation" (rather: test run) in R:
results <- NULL for (i in 1:50) { N=i*2 n1=N/2 p=1/3 q=1-p results <- c(results, ((factorial(N)/(factorial(n1)*factorial(N-n1)))*(p^n1)*(q^(N-n1)))) }
And got the following results (sorry for ugly table):
N| probability ---+-------------- 1 0.4444444444 2 0.2962962963 3 0.2194787380 4 0.1707056851 5 0.1365645481 6 0.1112748170 7 0.0918458807 8 0.0765382339 9 0.0642543198 10 0.0542592034 11 0.0460381120 12 0.0392176509 13 0.0335193598 14 0.0287308798 15 0.0246872745 16 0.0212584864 17 0.0183406549 18 0.0158499487 19 0.0137180842 20 0.0118890063 21 0.0103163865 22 0.0089617094 23 0.0077927908 24 0.0067826142 25 0.0059084106 26 0.0051509221 27 0.0044938086 28 0.0039231662 29 0.0034271337 30 0.0029955687 31 0.0026197805 32 0.0022923080 33 0.0020067342 34 0.0017575319 35 0.0015399328 36 0.0013498176 37 0.0011836238 38 0.0010382665 39 0.0009110715 40 0.0007997183 41 0.0007021917 42 0.0006167398 43 0.0005418386 44 0.0004761612 45 0.0004185515 46 0.0003680018 47 0.0003236328 48 0.0002846770 49 0.0002504641 50 0.0002204084
As you can see here, I computed the probabilities of getting back to the original point for all possible steps (N), where N<=100. That is done by computing the probability for all even N, where the number of steps to the right is equal to the number of steps to the left with the following formula: $P(n_{1}|N)=\frac{N!}{n_{1}!^2}p^{n_{1}}(1-p)^{n_{1}}$
where N is the number of steps, $n_{1}=\frac{N}{2}$ and $p=\frac{1}{3}$.
Note: the sum of all above is 1.998366. That is higher than 1, as the probability of arriving back to the original point could also include a lower N's probability.
That's all I could do, I like to play with simulations, but not good at all with Markov chains extrapolated to infinite :)