1
$\begingroup$

I need to get from one Place A to another places B on a square-board fe. The distances from A to B is 20 places. I have a dice and if I get 4 I move 4 places.

One rule exist: You can move forward and backwards. Ie if I'm at place 22 and I through a 2, I can then move 2 places backwards and still get 20 (B) which is my goal. You can decide at any step whether or not to move forward or backwards. If this make the problem too complex, we could assume that a player always moves forward in the start.

How can I calculate the probability for getting to B with 10 troughs with a dice? This was just one example, but I'm also interested in the general solution.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Note that the probability of getting in exactly one step is $\frac{1}{6}$ iff you're within $6$ blocks. You can try recursion up from that. $\endgroup$ – Cehhΐro Jan 30 '17 at 13:33
1
$\begingroup$

You start at point 0 of your lane. With equal propability you can roll $1$ to $6$ and than you can choose between walking forwards and backwards. By choosing a laurent polynomial $p=\frac{1}{6}(x^{-6} + x^{-5} + x^{-4} + x^{-3} + x^{-2} + x^{-1} + x^{1} + x^{2}+ x^{3} + x^{4} +x^{5} + x^{6})$ one can multiply this with $1$ as often, as one would like to roll.

Usually the coefficient of the monomial of choice is the porpability you want, but you have to be careful here! Since you can go two ways on each roll, the sum of coefficients is $2$ instead of $1$ as is should be. Therefore you can interprete the result as "number of ways to get to this point after $n$ rolls".

There is not a closed form for this, I fear.


In comments, the question arises, what will happen, if we allow only the last (tenth) throw to go back. In that case, you take the normal polynomial $q=\frac16(x+x^2+x^3+x^4+x^5+x^6)$ and calculate $q^9$. This will give you some propabilites to reach square 14 to 19 and 21 to 26 as coefficients for $x^{19}$ for example. You have to multiply each of those by $\frac16$ and add them up.

By this you consider to reach to a square, from where you can finish in the last roll of the dice. And you take into consideration to throw the fitting number (hence the last $\frac16$).


Edit for clarity: Often, when we are dealing with discrete propbilities, it is often necessary to convolute them as a means of "Add the results of two random experiments to get the result of one experiments" This is done when calculating the sum of two dices.

One easy way to convolute discrete vectors is by polynomial multiplication of $p$ and $q$. Every coefficient of $p$ is multiplied with every one from $q$ and the result is grouped by the power of $x$. And, in fact, it does not matter, if you got the 7 by throwing $(1,6)$ or $(3,4)$. YYou jsut care about the seven.

So you associate the propability of a throw giving result $y$ (like in dice-rolls $1$ to $6$) with the coefficient of $x^y$ in a polynomial. Thats where my polynomial $q$ from above comes from. Every result (as given in the exponent of a power of $x$) hast the propability of it's coefficient. If you multiply those polynomials, you can interprete the result again as a propability distribution. The propability of result $y$ is the coefficient in front of $x^y$. There is no need to replace $x$ with any value since we are not interested in evaulating that polynomial but more in the polynomial itself.

$\endgroup$
  • $\begingroup$ Thanks for the answer. To be clear; I'm my case where I have 10 troughs to get exactly block 20, what is the probability then? $\endgroup$ – Ole Petersen Jan 30 '17 at 13:50
  • $\begingroup$ If I'm not mistaken in MATLAB calculations, there are 9.185 ways to get from 0 to 20. This does not directly correspond to a propability! $\endgroup$ – Laray Jan 30 '17 at 14:14
  • $\begingroup$ But I'm not clear about the use of values. Can I see your code or how you use the choice of parameters? $\endgroup$ – Ole Petersen Jan 30 '17 at 14:17
  • $\begingroup$ I just set up a laurant-polynomial with Q=laurpoly[1 1 1 1 1 1 0 1 1 1 1 1 1]/6, 6) and then do q*...*q and read the result $\endgroup$ – Laray Jan 30 '17 at 14:19
  • 1
    $\begingroup$ That is way easier. I will update my answer for that. $\endgroup$ – Laray Jan 30 '17 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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