7
$\begingroup$

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?

Grid

$\endgroup$
  • $\begingroup$ The calculations to compute $((s+1/s+t+1/t)/4)^n$ and expand it out as monomials in $s,t$ are identical to the ones you are making. You can therefore let algebra do your work for you. Setting $n=3$ in that expression shows that the coefficient of $s$ (which corresponds to a net $1$ move right and $0$ moves up or down) is $9/64$, which is considerably larger than anything shown in your diagram. Can you find the nine distinct paths to which that corresponds? $\endgroup$ – whuber Dec 12 '14 at 22:21
  • $\begingroup$ I don't follow your reasoning exactly, how did you derive this formula? $\endgroup$ – Chris Dec 12 '14 at 22:50
  • $\begingroup$ Think about the operations you do when you multiply such polynomials: you have to keep track of the powers of $s$ and $t$ and add up the various contributions. The $s$ term represents one step horizontally; the $1/s$ term cancels that with a step in the other direction because $s\times 1/s=1$. The $t$ terms work similarly. Polynomial algebra (from this point of view) is just a bunch of shortcuts for computing all the paths, giving you a rigorous and systematic answer to a question in one of your comments: "Do you know of a better way of calculating the number of ways?" $\endgroup$ – whuber Dec 12 '14 at 23:15
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand most of this, but have a few questions. Why does $p3(a)+p3(b)+2p3(c)=\frac{1}{4}$? In revised step 1, how has q already reached the third dot? At this point I assume we can only move one dot over? Thanks! $\endgroup$ – Chris Dec 15 '14 at 3:30
  • $\begingroup$ By the indicated rotational symmetry there are 4 'a' cells, 4 'b' cells and 8 'c' cells in total, which between them must contain all probability. $\endgroup$ – Glen_b -Reinstate Monica Dec 15 '14 at 5:12
  • $\begingroup$ I see, and for $\frac{1}{4}$ of the grid it must be $\frac{1}{4}$. I'm still a little confused about revised step 1. $\endgroup$ – Chris Dec 15 '14 at 15:13
  • $\begingroup$ It's the same drawing as step 1, but since everything outside the indicated 45-degree "slice of pie" (i.e. $[0,\pi/4]$) can be computed from that slice, we only need to draw/compute what's in that slice (and on its boundary). So from that point on we just draw that part. $\endgroup$ – Glen_b -Reinstate Monica Dec 15 '14 at 19:33
  • $\begingroup$ Aha I see you are moving outward and to the right! From the pie slice shape I thought you had moved outward and to the left 3 spaces already. Thanks for your solution! Learned a lot :) $\endgroup$ – Chris Dec 15 '14 at 20:48
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes the particle can move in any direction. $\endgroup$ – Chris Dec 12 '14 at 21:02
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you know of a better way of calculating the number of ways? It is easy to get lost writing it out as I have been. $\endgroup$ – Chris Dec 12 '14 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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