Probability question: n-sided dice

[Char. Limit]

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?

 

[tiny-tim]

Hi Char. Limit!

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

Start with P(> k rolls needed) = P(k rolls insufficient)

 

[vela]

Hint: If you need k rolls, that means you had k-1 failures before a success.

 

[Ray Vickson]

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 for a simple introduction with worked examples.

RGV

 

[Hurkyl]

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.
$$v(0) = \left[ \begin{array}{} 1 \\ 0 \\ 0 \\ 0 \end{array} \right]$$

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)

 

[Char. Limit]

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:

$$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]$$

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) = [x₁, x₂, x₃, x₄]^T, then

$$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]$$

But how do I find a closed form for the second, third, and fourth terms there?

 

[Hurkyl]

But how do I find a closed form for the second, third, and fourth terms there?

Well, if $v(N+1) = A_n v(N)$, then $v(N) = A_^N v(0)$.

 

[Char. Limit]

Well, if $v(N+1) = A_n v(N)$, 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:

$$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]$$

Now, I assume I just need the third term of this vector, right? And then I'd, what, run a sum over all N?

 

[Hurkyl]

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.

 

[Char. Limit]

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!

 

[Ray Vickson]

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