Define the joint pmf of a particle moving randomly on a grid

Question

A particle starts at (0,0) and moves in one-unit independant steps with equal probabilities of $\frac{1}{4}$ in each of four directions: north, south, east, and west. Let $S$ equal the east-west position and $T$ the north-south position after n steps. Define the joint pmf of $S$ and $T$. Give the probabilities of the joint pmf and the marginal pmfs.

I've drawn a grid and counted the number of ways in which you can you can land on a square after 3 moves starting from (0,0). If each move in any direction has a $\frac{1}{4}$ probability I assumed that any 3 moves would have a probability of $\frac{1}{64}$. Therefore if there are say 4 ways to get to a square then the probability of getting to that square should be $\frac{4}{64}$.

There are 16 total (checkmarked) squares you can end up on after 3 moves and 36 total ways you can get to the squares (some more than others, as indicated by the large number in each square). Using my method above the distribution totals only $\frac{36}{64}$. Where am I going wrong?

Answer 1

I'm going to focus attention on some specifics of your example, but the arguments carry over to larger examples.

As you saw, there are 25 cells inside a 3-step radius of the origin:

                .
             .  .  .
          .  .  .  .  .
       .  .  .  o  .  .  . 
          .  .  .  .  .
             .  .  .
                . 

The first thing to do is recognize that symmetry considerations reduce calculation to final cells whose center lie within an angle to the origin of $[0,\pi/4]$:

                .      ⁄ 
             .  .  . ⁄ 
          .  .  .  +  +
       .  .  .  +  +  +  + ------
          .  .  .  .  .
             .  .  .
                . 

That cuts 25 cells that lie within a 3-step radius down to 6. In large problems it will reduce it to a bit over 1/8th of the total.

The second thing to see is that parity considerations reduce calculation still further, eliminating 3 of the 6 cells (e.g. if you move three steps, you can't end up back where you start). So you only need to work out three cells:

             . 
           . . .  
         . . . . c
       . . . . a . b 
         . . . . .
           . . .
             . 

This step will reduce calculation by around half.

All other cells that have non-zero probability after 3 steps will equal one of the three marked cells.

Now recognize that if you take those three cells, and add another cell:

             . 
           . . c'  
         . . . . c
       . . . . a . b 
         . . . . .
           . . .
             . 

then by rotation, you cover all the positive-probability cells with the right probability. Hence if $n(.)$ is the number of ways of getting to cell $i$, $n(a)+n(b)+2n(c)=64/4=16$, and for probabilities, if $p_3(i)$ is the probability of getting to position $i$ at step $3$, $p_3(a)+p_3(b)+2p_3(c)=1/4$. This provides a useful check that we didn't miss any probability.

(More generally, you'd double any cell not on the x-axis or on an exact diagonal in this calculation. And on even numbered steps, the origin counts only once, of course.)

So if you have a systematic method for getting those individual cell counts/probabilities, you only have to do those ones.

---

However as for working out the probabilities, I tend to look at doing it recursively, one step at a time, essentially convolving the single-step probabilities as a kernel with the outcome of the previous step.

Step 0. We start with all the probability at the center:

           · · ·
         · · · · ·
         · · 1 · · 
         · · · · ·
           · · ·

Step 1. Consider the first, single step

         ·   ·   ·   ·   ·        ·   ·  1/4  ·   ·
                 ↑ 
         ·   · ← 1 → ·   ·  ===>  ·  1/4  0  1/4  · 
                 ↓                            
         ·   ·   ·   ·   ·        ·   ·  1/4  ·   ·

This single-step result now can be treated treated as a kernel - on any future step, we take the probabilities at any given location at the previous step, convolve it with this bivariate kernel and to get the next step. In practice this means you take a given amount of probability, divide it by 4 and add it to the cell probabilities one step in each of the 4 directions, iterated over all cells (in really large problems you'd look at more efficient approaches, but this will do for the present problem). If you do that across all relevant cells, you've computed all the probabilities at one step in terms of the previous one.

But, usefully, we can flip this around. To work out the probability of a given cell, you average the 4 probabilities from the previous step that were one step in each of the 4 directions around it:

$p_{i,j}(t)=\frac{1}{4}[p_{i-1,j}(t-1)+p_{i,j-1}(t-1)+p_{i+1,j}(t-1)+p_{i,j+1}(t-1)]$

We can employ the previously mentioned symmetries, so we only need to keep track of cells within the 1/8-arc (including its boundary).

So revised Step 1:

                   · · 
                 · · · 
               · · · · 
             o q · · · 

Where $p_1(o)=0$ and $p_1(q)=\frac{1}{4}$ (I used $q$ to stand for "quarter").

And revised Step 2:

                   · · 
                 · · · 
               w · · · 
             o . x · · 

The point marked $w$ gets 1/4 of the probability from each side of it. But only 2 of those cells are non-zero:

          0
          ↓
    q  →  w  ←  0
          ↑
          q

so $p_2(w) = 2(1/4)^2 = 1/8$

Meanwhile, $x$ is only getting probability from its left, so $p_2(x) = (1/4)^2 = 1/16$

However, there's also point $o$, which can inherit probability from any side, so $p_2(o)=4(1/4)^2=1/4$.

Check: $p_2(o)+4(p_2(w)+p_2(x))=1/4 + 4/8 + 4/16 = 1$

You can continue in that fashion to a revised Step 3:

      · ·                      · · 
    · · ·                    · · · 
  w · · ·    ===>          . c · · 
o . x · ·                . a . b · 

$p_3(a) = [p_2(o)+2p_2(w)+p_2(x)]/4 = [\frac{1}{4} + 2\frac{1}{8} + \frac{1}{16}]/4 =9/64$

$p_3(b) = p_2(x)/4 = (\frac{1}{16})/4 = 1/64$

$p_3(c) = [p_2(w)+p_2(x)]/4 = [\frac{1}{8} + \frac{1}{16}]/4 =3/64$

Check: $p_3(a)+p_3(b)+2p_3(c)=[9+1+2\times 3]/64=1/4$.

And so on for step 4, 5, etc.

Step 4 would go like:

      · ·                      · · 
    · · ·                    · · · 
  · c · ·    ===>          w · y · 
· a · b ·                o · x · z 

This is easy to write code to iterate through.

Answer 2

Are you allowing the particle to move backwards?

Either way, I would model it in terms of a matrix $A$ giving the transition probabilities between each pairs of cells. You can then find the probabilities of all paths from i to j after k steps by calculating $A^K$. This representation may lead you to a set of equations that would be more concise.

Answer 3

Your approach would lead to the correct answer, but you have missed some ways to get into the squares marked with $4$ and $2$. For example, 'right-up-right', 'right-right-up' and 'up-right-right' are 3 ways to end up at the same square, which you have marked with $2$.