# Random Walk - 1 dimension

1. Oct 21, 2017

### showzen

1. The problem statement, all variables and given/known data
Suppose a particle moves along the x-axis beginning at 0. It moves one integer step to the left or right with equal probability. What is the pdf of its position after four steps?

2. Relevant equations

Binomial distribution
$P(k) = {{n}\choose{k}} p^k (1-p)^{n-k}$

3. The attempt at a solution
In this case, $p=0.5$ and $n=4$, so
$P(k) = {{4}\choose{k}}\frac{1}{16}$

But this is intuitively wrong, as $P(0)$ should be maximum, but here $P(0) = \frac{1}{16}$. What am I missing here? Thank you.

2. Oct 21, 2017

### Merlin3189

I think you are on the right track, but:

What are the possible outcomes?

What does k stand for? And how does it relate to the possible outcomes?

3. Oct 21, 2017

### scottdave

That's is not exactly the right formula. How do you plug in negative numbers to it? For 4 steps, it is easy enough to work out by hand what the probability of each outcome is. You should start to see a pattern after doing 3 or 4 steps.

4. Oct 21, 2017

### Merlin3189

That's true scott, but if there were more steps, that would become harder.
His basic idea is sound, so long as he applies it correctly. Then he will be able to use the maths to quickly answer bigger cases.

5. Oct 21, 2017

### scottdave

Yes, but how do you plug in ${{4}\choose{k}}$ when k is negative?
And it needs to account for "missing numbers", like on even turns, only even outcomes are possible. On odd turns, you can only have odd results.
That's what I meant about the formula is not exactly right. You need to somehow get k to be from 0 to n, and have a formula of how that k relates to the actual number results.

6. Oct 21, 2017

### showzen

Outcomes are [-4,4].

The variable k is the number of successes. Lets define success as +1 on the x axis.

The relation between k and the outcomes...

k=0 gives the outcome -4,
k=1 gives the outcome -2,
k=2 gives the outcome 0,
k=3 gives the outcome 2,
k=4 gives the outcome 4.

So $P(w) = P(2k-4)$?

7. Oct 21, 2017

### Merlin3189

Well you don't plug negative numbers into k.
k does not represent the position on the line. It represents something else, which maps to positions.

If you take a more common situation where we use binomial distribution to calculate the probability of outcomes, like rolling a dice, $P(3)= {{n}\choose{k}} p^k (1-p)^{n-k} = {{4}\choose{3}} (\frac 1 6)^3 (1-\frac 1 6)^{4-3}$ , does not represent the probability of rolling a 3 in 4 tries, rather the probability that out of 4 tries you will get your chosen number 3 times.

8. Oct 21, 2017

### Ray Vickson

The binomial distribution is the distribution of the number of positive steps, not the distribution of the final position.

9. Oct 21, 2017

### Merlin3189

Yes, I'd be happy with that. I might choose to say it a little differently, but then I'm always a bit verbose!
So $P(ending \ at \ w) = {{n}\choose{k}} p^k (1-p)^{n-k} \ where \ k = \frac {(4+w)} {2}$

And actually I'm regretting my careless use of the word "outcomes", because I think Ray's use for the number of positive steps is more appropriate.

10. Oct 21, 2017

### showzen

This problem had 4 steps with equal probability. So in general with $n$ steps and $p$ probability, we have $P(ending \ at \ w) = {{n}\choose{k}} p^k (1-p)^{n-k} \ where \ k = \frac {(n+w)} {2}$?

11. Oct 22, 2017

### haruspex

Yes, as long as n+w is even.
If it takes k steps in the w direction from the origin then it takes n-k steps the other way. To end at w we need k-(k-n)=w. The k towards w can be any of the n.