1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability question: n-sided dice

  1. Sep 4, 2011 #1

    Char. Limit

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Two n-sided dice, with numbers ranging from 0 to n-1, are rolled. The first die represents the first digit of a base-n number, and the second represents the second digit of said base-n number. (In other words, the two dice rolls, if they are a and b, give the number a+b*n). Assuming that both dice are rolled concurrently, and each die is rolled until it rolls an n-1, at which point the other die continues to be rolled until it also rolls an n-1, what is the average number of rolls necessary until both dice reach their maximum value?


    2. Relevant equations
    I... don't really know.


    3. The attempt at a solution

    I've never taken a probability class, so I have no idea what to do here. The idea came to me while I was playing Dungeons and Dragons, and the original idea involved 10-sided dice, but I thought the general result might be more fun to see. Could someone help me with this problem, tell me what I need to do to solve it?
     
  2. jcsd
  3. Sep 4, 2011 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Char. Limit! :smile:

    (what does the scoring have to do with it? :confused:)

    Start with P(> k rolls needed) = P(k rolls insufficient) :wink:
     
  4. Sep 4, 2011 #3

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Hint: If you need k rolls, that means you had k-1 failures before a success.
     
  5. Sep 4, 2011 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You want the _Geometric Distribution_ with success probability p = 1/n per toss. See, eg.,
    http://mdm4u1.wetpaint.com/page/7.3+Geometric+Distribution [Broken] for a simple introduction with worked examples.

    RGV
     
    Last edited by a moderator: May 5, 2017
  6. Sep 4, 2011 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Brute force approach: you have four states:

    * Neither die have attained maximum
    * One die has attained maximum
    * Both dice have attained maximum
    * You were done prior to this step

    What state are you in after N dice rolls? You can write down a vector v(N) that encapsulates the probability of each case. e.g.
    [tex]v(0) = \left[ \begin{array}{} 1 \\ 0 \\ 0 \\ 0 \end{array} \right][/tex]

    There is a matrix A such that A v(N) = v(N+1). Its entries are the probabilities of transitioning from one state to another at each step. (the probability of transitioning from the third state to the third state is 1)

    So you can grind through linear algebra to get an explicit formula for v(N), and then you can sum the series that defines the average!

    (how to grind through linear algebra? Either compute a matrix exponential (diagonalize!) or solve a difference equation or solve a linear recurrence)
     
  7. Sep 4, 2011 #6

    Char. Limit

    User Avatar
    Gold Member

    All right, after a bit of work, I found A_n, where n is the number of sides on the dice. I got the following:

    [tex]A_n = \left[ \begin{array}{cccc}
    \frac{(n-1)^2}{n^2} & 0 & 0 & 0 \\
    \frac{2n-2}{n^2} & \frac{n-1}{n} & 0 & 0 \\
    \frac{1}{n^2} & \frac{1}{n} & 0 & 0 \\
    0 & 0 & 1 & 1 \end{array} \right][/tex]

    So we assumed at the start that A_n * v(x) = v(x+1), right? Umm... I've found the first term of v(x) in closed form, but I'm not sure how to handle the others. I mean, I get that if v(N) = [x1, x2, x3, x4]T, then

    [tex]v(N+1) = \left[ \begin{array}{c}
    \frac{(n-1)^2}{n^2} x_1 \\
    \frac{2n-2}{n^2} x_1 + \frac{n-1}{n} x_2 \\
    \frac{1}{n^2} x_1 + \frac{1}{n} x_2 \\
    x_3 + x_4 \end{array} \right][/tex]

    But how do I find a closed form for the second, third, and fourth terms there?
     
  8. Sep 4, 2011 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if [itex]v(N+1) = A_n v(N)[/itex], then v(N) = A_^N v(0)[/itex].
     
  9. Sep 4, 2011 #8

    Char. Limit

    User Avatar
    Gold Member

    Of course! Thanks a ton, I don't know how I missed that. All right, I have a closed form for v now. It's below:

    [tex]v_n(N) = \left[ \begin{array}{c}
    \left(\frac{n-1}{n}\right)^{2N} \\
    2 \left(\frac{n-1}{n}\right)^N - 2 \left(\frac{n-1}{n}\right)^{2N} \\
    2 \frac{(n-1)^{N-1}}{n^N} + (1 - 2n) \frac{(n-1)^{2N-2}}{n^{2N}} \\
    \frac{\left(n^N - n^{N+1} + n (n-1)^N \right)^2}{(n-1)^2 n^{2N}} \end{array} \right][/tex]

    Now, I assume I just need the third term of this vector, right? And then I'd, what, run a sum over all N?
     
  10. Sep 4, 2011 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Right, that's the plan. Well, you want to average, so you would sum the third term of N v(N).

    We expect summing the third term over all N to result in 1, I think.
     
  11. Sep 4, 2011 #10

    Char. Limit

    User Avatar
    Gold Member

    Thanks a ton! I got the answer I was looking for. You were a huge help!
     
  12. Sep 5, 2011 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    This is a simple 3-state Markov chain problem. The states are the number of (n-1)'s obtained to date, so they are 0, 1 or 2. The system starts in state 0, and you want to know the average number of transitions ("tosses") until you first reach state 2. The 1-step (i.e., 1-toss) transition probabilities are P{0->0} = (1-1/n)^2, P{0->1} = 2/n, P{0->2} = 1/n^2, P{1->0} = 0, P{1->1} = 1-1/n, P{1->2} = 1/n, and P{2->2} = 1 (i.e., '2' is an absorbing state). These are put into a one-step transition probability matrix P = [[(1-1/n)^2, 2/n,1/n^2],[0,1-1/n,1/n],[0,0,1]], whose ROWS sum to 1. (Note: 99.9% of Markov chain books and articles use the convention that rows sum to 1, but in some primarily-Asian journals the opposite convention of columns summing to 1 is sometimes used.) Of course, my P is the transpose of the 3x3 northwest 3x3 submatrix of your A.

    If all you want are expected numbers of tosses, you don't need matrix powers (although that would be one way to do it). In fact, if x = expected number of transitions to reach state 3, starting from state i = 0 or i = 1 we have: x[0] = 1 + P[0,0]*x[0] + P[0,1]*x[1] and x[1] = 1 + P[1,0]*x[0] + P[1,1]*x[1] = 1 + P[1,1]*x[1]. Solve these to get x[0].

    For more on this, see
    http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf , especially section 11.5.

    RGV
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Probability question: n-sided dice
Loading...