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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a $1$D random walk on x axis a particle can turn left with probability $\frac{3}{4}$ and right with probability $\frac{1}{4}$. What is the probability that $|x|\leq 1 $ for $1\leq t\leq 4$ total steps.

I am not looking for answers, but ways to think about it. How to approach this kind of a question? What is a good source that discusses random walks from the basics.

share|cite|improve this question
I assume you are starting at the origin. Draw a tree diagram. With such a small range of values of $t$, you can calculate all the relevant probabilities with not much effort. – André Nicolas Jun 6 '11 at 17:58
up vote 3 down vote accepted

user6312's suggestion to use a tree diagram is good, but I'm a bit lazy and prefer to do the calculations using linear algebra. Matrix multiplication automatically adds up the contributions from the branches of the tree diagram.

You start the particle at some state in the set $A=\{ -1, 0, 1\}$. Let $Q$ be the matrix of transition probabilities from this set into itself, i.e., $$ Q=\pmatrix{0&1/4&0\cr 3/4&0&1/4\cr 0&3/4&0}.$$

Then $Q_{ij}^n$, the $(i,j)$th entry in the $n$th power of $Q$, is the probability that the walk is in state $j$ at time $n$, starting at state $i$, without leaving the set $A$.

Since you don't want the answer, I will simply say that the row sums of $Q^4$ give you what you want, each row sum corresponding to one of the three possible initial states.

share|cite|improve this answer

Your Answer


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.