1
$\begingroup$

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.

  • 0
    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$.2011-08-08

3 Answers 3

3

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,

  • 0
    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.2011-08-08
1

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

0

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.