Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

Please keep the answer simple.

share|improve this question
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
add comment

3 Answers

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,

share|improve this answer
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
add comment

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).

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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