Simple (or not?) Probability

1. Dec 18, 2012

Mandelbroth

1. The problem statement, all variables and given/known data
A friend proposed this question to me. It looks like a homework problem, though, so I'll put it here to avoid any conflict with forum rules.

Suppose you roll a fair 9 sided die (with sides 1 through 9) 4 times. Let A be the value of the first roll, B be the value of the second roll, C be the value of the third roll, and D be the value of the fourth roll.

Find the probability that $A\leq B\leq C\leq D$

3. The attempt at a solution
I figure that the probability that $A\leq B$ is $\frac{9+36}{81}=\frac{45}{81}$ because there are 9 ways that they can be equal and half of the remaining 72 outcomes have A less than B. However, I'm having difficulty extending this to greater numbers of rolls.

Can someone please help guide me toward my next step? Thank you, in advance.

2. Dec 18, 2012

Ray Vickson

Letting $E = \{A \leq B \leq C \leq D\}$ we have
$$P(E) = \sum_{a=1}^9 P(A=a) P(E | A=a),$$
and for a = 1,2,3, ..., 9 we have
$$P(E|A=a) = P(a \leq B \leq C \leq D ).$$

Let $F_a = \{ a \leq B \leq C \leq D\}$. We have
$$P(F_a) = \sum_{b=a}^9 P(B=b) P(F_a | B = b) ,$$
and for b = a, ..., 9 we have
$$P(F_a | B = b) = P(b \leq C \leq D).$$
Keep going like that, or else try to find a nice formula for $Q(b) \equiv P(b \leq C \leq D).$ Then $P(E) = \sum_{a=1}^9 \sum_{b=a}^9 P(A=a)P(B=b) Q(b).$

3. Dec 18, 2012

haruspex

Another approach is to break it down according to numbers of rolls the same. There are 9*8*7*6 (ordered) rolls in which they're all different, and 1/24th of these will be in the desired order. 4C2*9*8*7 with one pair the same, of which 2/24 are in the right order. Then there's the two pairs case, the 3 of a kind, and four of a kind.