5
$\begingroup$

A fair four-sided die has its sides labeled U, D, L, and R, respectively. A token is placed at (0, 0) on the Cartesian plane and the die is then rolled repeatedly. After each roll, the token is moved as follows:

Token Moves
U (a, b) → (a, b + 1)
D (a, b) → (a, b − 1)
L (a, b) → (a + 1, b)
R (a, b) → (a − 1, b)

Let the random variable Yn be the taxicab distance. Taxicab distance is calculated by |a|+|b|.

What is the expected value of Yn and why?
What is the expected variance of Yn and why?

What I know so far:

After using a program that I made and tracking the sample space of n=1, n=2, n=3 and n=4 I managed to determine an equation that seems to generate the correct expected value 100% of the time.

E(Yn)=E(Y(n-1))*(2n-1)/(2n-2)

I don't know how I'd go about proving this equation and I lack a conceptual understanding of why it works. I need help with finding why this relation works.

$\endgroup$
1
  • $\begingroup$ Welcome to Cross Validated! Please take a moment to view our tour. This sounds as if it is a self-study question. If that is the case, please add the tag to your question and read the wiki for the tag. $\endgroup$
    – Tavrock
    Mar 13, 2017 at 16:51

1 Answer 1

5
$\begingroup$

Description:

Let $X_n = (X_{1,n},X_{2,n})^T \in \mathbb{Z}^2 = \mathbb{Z} \times \mathbb{Z}$ be the vector of positions for the process at time $t=0,1,2,3,\ldots$. This state space is just all the pairs or couples of integers. The square and times symbols denote the Cartesian product. You can google that, but the idea is that it's just all the possible pairs.

The first one will be the "$x$" coordinate. The second one will be the "$y$" coordinate. So we know $X_0 = (0,0)^T$, and there's a quarter chance of $X_1 = (1,0)^T$, and so on.

Your model can be written as $$ X_n = X_{n-1} + W_n, $$ where $W_n = (W_{1,n},W_{2,n})^T \in \{(0,1)^T, (0,-1)^T, (1,0)^T, (-1,0)^T\}$ is the jump or innovation or decision that moves the token around on the board.

Next define $Y_n = |X_{1,n}| + |X_{2,n}|$, the sum of the absolute values of each component. This is the "Manhattan distance" or "Taxicab distance."

Marginal Chains:

Notice that we could write the above as two equations $$ X_{1,n} = X_{1,n-1} + W_{1,n} $$ and $$ X_{2,n} = X_{2,n-1} + W_{2,n} $$ where the noise terms can take on values $(-1,0,1)$ with probabilities $.25, .5$, and $.25$, respectively. But they are correlated--if you know one of them is $1$, then the other has to be $0$, for example.

Recursive Formula for Expected Distance:

  1. The expected value of $Y_n$ is \begin{align*} E[Y_n| &= E[|X_{1,n}| + |X_{2,n}|] \\ &= E[|X_{1,n-1} + W_{1,n}|+ |X_{2,n-1}+ W_{2,n}|] \\ &= E\left\{ E[|X_{1,n-1} + W_{1,n}|+ |X_{2,n-1}+ W_{2,n}| {\large |} W_n = w_n ] \right\} && \text{ law of total expectation} \\ &= \frac{1}{4}E[|X_{1,n-1} + 1|+ |X_{2,n-1}|] + \frac{1}{4}E[|X_{1,n-1} - 1|+ |X_{2,n-1}|] + \frac{1}{4}E[|X_{1,n-1} |+ |X_{2,n-1}+1|] + \frac{1}{4}E[|X_{1,n-1} |+ |X_{2,n-1}-1|] \\ &= \frac{1}{4}E[|X_{1,n-1} + 1|]+ \frac{1}{4}E[ |X_{2,n-1}|] + \frac{1}{4}E[|X_{1,n-1} - 1|]+ \frac{1}{4}E[|X_{2,n-1}|] + \frac{1}{4}E[|X_{1,n-1} |]+ \frac{1}{4}E[|X_{2,n-1}+1|] + \frac{1}{4}E[|X_{1,n-1} |]+ \frac{1}{4}E[|X_{2,n-1}-1|] \\ &= \frac{1}{4}E[|X_{1,n-1} + 1|]+ \frac{1}{4}E[|X_{1,n-1} - 1|] + \frac{1}{4}E[|X_{2,n-1}+1|] + \frac{1}{4}E[|X_{2,n-1}-1|] + \frac{1}{2}E[Y_{n-1}] \\ &= \frac{1}{2}E[|X_{1,n-1} + 1|]+ \frac{1}{2}E[|X_{1,n-1} - 1|] + \frac{1}{2}E[Y_{n-1}] \\ &= E[|X_{1,n-1} + 1|] + \frac{1}{2}E[Y_{n-1}] \end{align*}

Adding $1$ to a coordinate might increase or reduce the absolute value, depending on whether or not it's positive, negative or equal to $0$. So we want to use law of total expectation and condition on the sign of $X_{1,n-1}$.

At the moment, I'm having a hard time finding an expression for $E[|X_{1,n-1} + 1|]$. The random variable has support and probabilities that depends on $n$. In the meantime, here's some R code that uses the Monte Carlo method to find the answer:

getRandomDistance <- function(n){
  start <- c(0,0)

  posit <- start
  for(time in 1:n){
    jump <- sample(list(c(-1,0), c(1,0), c(0,1), c(0,-1)), size = 1, prob = c(.25, .25, .25, .25))[[1]]
    posit <- posit + jump
  }

  return(abs(posit[1]) + abs(posit[2]))
}


numTimes <- 10000
chainLength <- 101
mean(replicate(n = numTimes, expr = getRandomDistance(chainLength)))
$\endgroup$
6
  • 1
    $\begingroup$ Honestly, I'm not really at a level with statistics that I can really understand the solution you're presenting here. $\endgroup$
    – Magd Aref
    Mar 13, 2017 at 22:32
  • $\begingroup$ Well, I tried my best to research the components in your answer. I haven't been taught IIDs, lattice distributions or much else really. At this point in my uni course, we're supposed to be able to answer this question with an understanding of expected value, variance, and sums of random variables. Tomorrow is my lecture on Laws of Large Numbers, and Chebyshev’s Inequality. $\endgroup$
    – Magd Aref
    Mar 13, 2017 at 23:43
  • $\begingroup$ Thanks a lot :)! Turns out my lecture on Laws of Large Numbers, and Chebyshev’s Inequality was cancelled as well. $\endgroup$
    – Magd Aref
    Mar 14, 2017 at 12:34
  • $\begingroup$ Okay so in this comment I'm going to ask for some small clarifications on various things. First of all, in the beginning, you say the function element of integers squared. I'm unfamiliar with what the square or the superscript 2 means with respect to the integer symbol. The next thing I was wondering about was the definition of Yn, the sub of absolute values of each component. By sub do you mean sum? $\endgroup$
    – Magd Aref
    Mar 14, 2017 at 15:02
  • 2
    $\begingroup$ Obtaining the expectations is simpler than it might look, because $X_n$ has a distribution that is easily related to the Binomial. Thus, $$E|X_{n}|=n\binom{2n}{n}/4^n = \sqrt{\frac{n}{\pi}}\left(1 - \frac{1}{8n} + \frac{1}{128n^2} + O(n^{-3})\right).$$ The variances are harder to compute exactly--using a Normal approximation would be appropriate. $\endgroup$
    – whuber
    Mar 14, 2017 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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