1D random walk-probability to go back to 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?
 A: 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). 
A: 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.
