From https://brilliant.org/wiki/linearity-of-expectation/
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)) $$