Probabilistic Treasure hunt game

I am designing a treasure hunt game where users start of at a fixed number of steps (x) away from the treasure. The user responses are either a or b. A correct answer places the user one step closer to the treasure, a wrong answer takes the user one step away from the treasure. (maximum steps away from the treasure is x.). The two options have a 50% chance of being right on each question. The Game ends when player is 0 steps from the treasure.

Is it correct that the user will always get to the treasure in 2x moves? Or is it 2^x (2 power x)?

Is there anything a player can do to increase their chances of winning? Is there a way I can make the game harder. (Apart from increasing x)?

-
Have you studied stochastic processes? This would be an exercise if you had. I could explain it to you if you did, but if you didn't study those, I can give you the answer plain. –  Patrick Da Silva Aug 8 '11 at 16:40
I have seen the phrase stochastic processes for the first time ever in your post. I am now on Google to learn more about it/them. –  artfullyContrived Aug 8 '11 at 16:46
It'll take a while before you can find the answer just by Googling... but it's a good thing you do =) I'll find the answer and post it for others to see... except if someone does before me =) –  Patrick Da Silva Aug 8 '11 at 16:53
You are dealing with the most studied example of a random walk. Lots of results. One can get a recurrence, and then an explicit formula, for being in ant "state" at a given time. –  André Nicolas Aug 8 '11 at 16:58
A player cannot do anything to increase his chances of winning (yelling at your console hoping to get lucky won't work =D) but if you want to make the game "harder" (i.e. make the player win less quickly) you could make your random walk assymetric, say, there is, for instance 3 choices, $a$, $b$ and $c$, and a correct answer (say $a$) would make the user move forward, and both $b$ and $c$ would make you move backwards. Another way you could do is let $a$ make you move forward, $b$ you stay in place, $c$ backwards. It will take more steps to get to $x$. –  Patrick Da Silva Aug 8 '11 at 17:42

The stochastic process you are describing is well known to be a random walk. I know OP said that he doesn't know about stochastic processes, but for the audience, consider the transition matrix in his problem, with state space $\{0,1,\cdots,x\}$ : $$P = \underset{x+1 \text{ columns }}{\underbrace{\begin{pmatrix} 1/2 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 & 0 & \vdots \\ 0 & 1/2 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & \cdots & 0 & 1 \\ \end{pmatrix} }}$$ From this matrix we get the matrix $Q$ of probabilities in transient states : $$Q = \underset{x \text{ columns }}{\underbrace{ \begin{pmatrix} 1/2 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 & 0 & \vdots \\ 0 & 1/2 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 1/2 \\ 0 & \cdots & \cdots & 1/2 & 0 \\ \end{pmatrix} }}$$ and thus the fundamental matrix becomes the inverse of $$I-Q = \begin{pmatrix} 1/2 & -1/2 & 0 & \cdots & 0 \\ -1/2 & 1 & -1/2 & 0 & \vdots \\ 0 & -1/2 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & -1/2 \\ 0 & \cdots & \cdots & -1/2 & 1 \\ \end{pmatrix}$$ One can guess by looking at the inverses of the matrix for small $x$ (using a computer to compute inverses for greater $x$ if his eyes are blind) that $$(I-Q)^{-1} = \begin{pmatrix} 2x & 2(x-1) & 2(x-2) & \cdots & 2 \\ 2(x-1) & 2(x-1) & 2(x-2) & \cdots & \vdots \\ 2(x-2) & 2(x-2) & 2(x-2) & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 2 \\ 2 & \cdots & \cdots & 2 & 2 \\ \end{pmatrix}$$ which means that the expected number of steps to go from $0$ to $x$ is $$\sum_{k=1}^x 2k = 2\frac{x(x+1)}2 = x^2 + x.$$ Furthermore, if it is of interest in your case, if your player has reached state $n$ and you want to know the expected number of steps before he reaches state $x$, that would be $$\sum_{k=1}^n 2k + (x-n)2n = 2n(x-n) + n^2 + n.$$ Hope that helps,

-
Maybe I am too pessimistic but I do not know what a novice can get from these matrix manipulations... :-) It seems you did not quite make up your mind about the audience (your word) you wanted to reach: beginners or experts? –  Did Aug 8 '11 at 17:52
@Didier Piau: at least, there is a formula for an average time. Btw, it will be nice if you join our discussion in the chatroom. –  Ilya Aug 8 '11 at 19:13
I think it was quite clear that when I said "for the audience", I meant "for those who know what a random walk is and want to know how it could be done", since I referred to the OP as someone who didn't know what a random walk is. Clearly a novice in stochastic processes gets nothing from this. =P I was reaching those who wanted to know how to solve this problem, if they had the tools to do so. Happy now? –  Patrick Da Silva Aug 8 '11 at 23:27
One more thing though ; it's still of interest in my opinion to post solutions even when the OP cannot understand (though it is polite to ask if he could, like I did) because letting other mathematicians approve your solution is a sign for the OP that your solution is correct, thus giving him confidence to use them if he wishes to. –  Patrick Da Silva Aug 8 '11 at 23:52

It may happen that the (2k) first answers are abababa... in which case you will not have reached 0 after (2k) steps, hence no uniform deterministic bound on the time needed to reach 0 can hold. But the expected time needed to reach 0 starting from x is x^2+x (this can be explained rather elementarily if you wish).

If the probabilities of a step in each direction are the same at each site but unequal, the expected time becomes linear in x if the chances to make a step towards 0 are more than 50% but it becomes exponential in x if the chances to make a step towards 0 are less than 50% (and I guess some physicists would call this a phase transition).

-

I hope I understand your problem correct. On each step the right answer is either $a$ or $b$ with probability $0.5$ - so the player can be at positions $0,1,2,...,x$.

First of all, player cannot do anything here since his choice does no influence at all - the random number generator in average will do the same. Second, there is always non-zero probability not to find the treasure in $n$ steps, no matter how great is $n$. Third, to make the game more harder you may want to make it more interesting - namely incorporate the nice dependence on the player's decisions.

-