1

From https://brilliant.org/wiki/linearity-of-expectation/ enter image description here I have two questions:

First question

The "obvious" solution is by using linearity of expectations. My idea was to write the states as $E(n - 1|n)$, where $n$ is the number of steps she needs to get her acorn. So the expectations for each state are $$ E(3|4) = 1 $$ (as $n = 4$ only happens at the starting point, and no matter where you move, you'll move to a spot where three are three more steps to move) $$ E(2|3) = \frac{2}{3} + \frac{1}{3}\left(2 + E(2|3)\right) $$ $$ E(2|3) = 2 $$

(suppose you're at (0, 1) in the x-y coordinate plane. Then there are two ways (moving up and right) that you will move into a spot where there are two steps required to get the acorn. There is one way to go back to the origin, which requires us to add 1, E(3|4) and E(2|3) as a result. Solving this, we get E(2|3) = 2)

$$ E(1|2) = \frac{1}{2} + \frac{1}{2}\left(1 + E(2|3) + E(1|2)\right) $$ $$ E(1|2) = 4 $$ $$ E(0|1) = \frac{1}{3} + \frac{2}{3} \left(1 + E(1|2) + E(0|1)\right) $$ $$ E(0|1) = 11 $$

(using the same logic as before)

And as a result,

$$ E(X) = E(3|4) + E(2|3) + E(1|2) + E(0|1) $$ $$ E(X) = 1 + 2 + 4 + 11 $$ $$ E(X) = 18 $$

  • Is this correct?
  • Is there a more elegant use of "states" I could use to solve this problem faster?

Second question

Can this be solved without the use of linearity of expectations? For example, by bivariate recursion on the points themselves? Such as saying something like

$$ f(0, 0) = 1 + \frac{1}{2} (f(1, 0) + f(0, 1)) $$

Leaderboard
  • 335
  • 1
    1/ Note that the states at distance 2 are not necessarily the same, and you need to come up with an argument for why they are. That hole can be fixed. (For the other distances, you can argue that they are equivalent via symmetry) $\quad$ 2/ Can you elaborate on what $E(n-1|n)$ is? Why not write it as $E_n$? -> I think you want $E(a | b)$ to be the expected steps to get to a $a$ away position, conditional on being $b$ away. – Calvin Lin Mar 12 '24 at 15:48
  • 1
    3/ Typically the approach would be to set up $E(State)$ and solve for each directly. This idea of $E(a|b)$ isn't commonly used, in part because the states at distance $a$ away could be very different from each other. As such, I encourage you to figure out the $E(State)$ approach, which is what you alluded to in the second question. – Calvin Lin Mar 12 '24 at 15:52
  • @CalvinLin you are correct on point 2, i.e, the expected number of steps to come one step closer (i.e, expected steps to get to $n - 1$ away, conditioned on being $n$ steps away) – Leaderboard Mar 12 '24 at 17:59

0 Answers0