5
$\begingroup$

An invisible target on the integer line starts at $0$. On each round it either stays put, moves to the left or moves to the right by $1$ with probability $\frac{1}{3}$ each. You are then asked to guess the location of the target and told whether your guess was correct or wrong.

What is the optimal strategy to maximise the expected number of correct guesses, say in $N \geq 2$ rounds?

Improve this question
$\endgroup$
8
  • $\begingroup$ An observation: when you correctly guess the game effectively restarts. So you want to minimize the number of incorrect guesses until a correct guess. $\endgroup$
    – user479223
    Commented Feb 19 at 22:47
  • 1
    $\begingroup$ @user479223 That was my initial thought too, but there is actually quite a subtle but large difference between minimising the time taken to guess the correct location, and maximising the expected number of correct guesses. This is because when the game resets, you now have $N-k$ turns to go, which affects the expected value, and even the optimal strategy of the new game. In other words the expected value is a weighted sum of the time taken to guess correctly, so it’s not immediate that minimising the expected time (an unweighted sum) maximises the expected number of guesses. $\endgroup$
    – Nate River
    Commented Feb 19 at 22:53
  • 1
    $\begingroup$ @user479223 It may be that the two end up equivalent but it is at least not a priori immediate. $\endgroup$
    – Nate River
    Commented Feb 19 at 22:54
  • 1
    $\begingroup$ Updated observation: if you know the optimal strategy for $N-k$ and you guess correctly at $k$ then you are fine. Maybe some kind of Bellman… $\endgroup$
    – user479223
    Commented Feb 19 at 23:13
  • $\begingroup$ Yuval Peres told me a proof for a $c\, N$ lower bound. Do you care about the optimal constant? Do you care about the exactly optimal strategy? $\endgroup$
    – mathworker21
    Commented Apr 23 at 16:12

0

Reset to default

You must log in to answer this question.