Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose There is a random walk starting in origin while probability to move right is 1/3 and probability to move left 2/3.What is the probability to return to the origin.

Thank you

share|improve this question
    
If you let the random walk continue ad infinitum? One, I would think. –  Noldorin Jan 18 '11 at 16:41
3  
@Noldorin: No, an asymmetric walk like this one goes off to leftward infinity with probability 1. Thus it almost surely returns to the origin only finitely many times, and has a positive probability of never returning at all. –  Chris Eagle Jan 18 '11 at 16:46
    
@Chris: Ah right. The analysis seems very complex indeed for the asymmetric case. –  Noldorin Jan 18 '11 at 16:53
1  
@Noldorin: proving what I've just said isn't very hard. See e.g. sections 1.5 and 1.6 of this book. I can't see immediately how to adapt that kind of approach to get a precise probability rather than an estimate though. –  Chris Eagle Jan 18 '11 at 17:16
    
@Chris: Given I have zero formal training in Markov chains, I would consider it very difficult. :) –  Noldorin Jan 18 '11 at 17:34
add comment

3 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
I am not sure. I must miss something, but with your computation: $P_{1}=\frac{\frac{1}{3}}{\frac{2}{3}}=0.5$. But I think it should be $\frac{1}{3}\cdot\frac{2}{3}+\frac{2}{3}\cdot\frac{1}{3}=0.4444$. What is the problem with my computation? –  daroczig Jan 18 '11 at 20:06
    
"i" could be negative so we could get probability greater then one which is not possible –  Yakov Jan 18 '11 at 20:44
    
@daroczig: Your $P_n$ is the probability of returning to the origin from the origin in exactly $2n$ steps. My $P_n$ is the probability of ever returning to the origin starting from position $(-n)$. And my calculation is specifically for non-negative $n$... the probability of returning to the origin starting from any position to the right of the origin is 1. –  mjqxxxx Jan 18 '11 at 20:46
add comment

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).

share|improve this answer
add comment

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 :)

share|improve this answer
    
The number of steps doesn't play a role.I am not limited by it –  Yakov Jan 18 '11 at 16:46
    
@Yakov: that sounds tough :) I am trying to work out a solution, but see no easy way. Till then, please see my edited answer above, that may help finding the way. –  daroczig Jan 18 '11 at 18:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.