Probability question: n-sided dice

  • #1
Char. Limit
Gold Member
1,204
14

Homework Statement


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?


Homework Equations


I... don't really know.


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?
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
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:
 
  • #3
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
15,046
1,636
Hint: If you need k rolls, that means you had k-1 failures before a success.
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement


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?


Homework Equations


I... don't really know.


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?

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:
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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)
 
  • #6
Char. Limit
Gold Member
1,204
14
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?
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
But how do I find a closed form for the second, third, and fourth terms there?

Well, if [itex]v(N+1) = A_n v(N)[/itex], then v(N) = A_^N v(0)[/itex].
 
  • #8
Char. Limit
Gold Member
1,204
14
Well, if [itex]v(N+1) = A_n v(N)[/itex], then v(N) = A_^N v(0)[/itex].

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?
 
  • #9
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Now, I assume I just need the third term of this vector, right? And then I'd, what, run a sum over all N?
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.
 
  • #10
Char. Limit
Gold Member
1,204
14
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.

Thanks a ton! I got the answer I was looking for. You were a huge help!
 
  • #11
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement


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?


Homework Equations


I... don't really know.


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?

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
 

Related Threads on Probability question: n-sided dice

  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
13
Views
2K
Replies
4
Views
805
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
11
Views
7K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
1
Views
633
  • Last Post
Replies
6
Views
1K
Top