# Probability of rolling one die by two persons 3 times each, and problem with pulling out cards

So suppose you have one die. Person A rolls one die 3 times. Person B does the same after A is finished. What is the probability that person A's smallest number (of his/hers 3 rolls) is greater than person B's biggest number?

Extra addition: Now problem is the same but instead of 1 die we have 32 cards with numbers 1-32 on each of the cards. I want to know the probability that person A's smallest number taken from 32 cards is greater than person B's biggest number. Each person takes 3 cards. When A is finished he puts back his cards. Than it's person B's turn and he also takes 3 cards out of 32.

• If this is homework please add the self-study tag. – TrynnaDoStat Feb 26 '15 at 15:21
• It is not homework. I heard this tricky question once and now I want to know the answer, before I forget it. – anicicn Feb 26 '15 at 16:48

Let's generalize the problems further.

### The card game: drawing without replacement

Notice that according to the description of the card game, each set of three draws is without replacement. Generalize "three" by $k\ge 1$ and suppose there are $N$ distinct card values.

$A$ draws $k$ values (without replacement) $a_1 \lt a_2 \lt \cdots \lt a_k$ from a population of numbers $x_1 \lt x_2 \lt \cdots \lt x_N$ where $x_i$ has probability $1/N$ of being drawn. After replacing those values, $B$ draws $k$ values $b_1 \lt b_2 \lt \cdots \lt b_k$. What is the chance that $a_1 \gt b_k$?

We can break this down by the value of $b_k$, which can range from $x_k$ up through $x_{N-k}$. The event $a_1 \gt b_k = x_m$ means all $k-1$ of $B$'s remaining values were drawn from the set $x_1, \ldots, x_{m-1}$ while all $k$ of $A$'s values were drawn from the set $x_{m+1}, x_{m+2}, \ldots, x_N$. The first can be done in $\binom{m-1}{k-1}$ ways while the latter can be done in $\binom{N-m}{k}$ ways. The total number of equiprobable outcomes is $\binom{N}{k}\binom{N}{k}$, regardless. Thus the answer is

$$\binom{N}{k}^{-2} \sum_{m=k}^{N-k} \binom{m-1}{k-1}\binom{N-m}{k} = \binom{N}{k}^{-2}\binom{N-k}{k}\frac{N!}{2^{k} (2 k-1)\text{!!} (N-k)!}.$$

For the cards, $N=32$ and $k=3$, giving $1827/49600\approx 0.0368347$.

### The die game: drawing with replacement

When, as in the dice problem, the draws are with replacement, the same idea applies but the probabilities differ a little. We can decompose the event "maximum of $B$ is less than the minimum of $A$" by the value attained by $\max(B)$, for instance. Let that value be $x_m$. When $G$ is the distribution law of $B$, the chance that all values in $B$ do not exceed $x_m$, but at least one equals it, is

$$G(x_m)^k - G(x_{m-1})^k.$$

Let $F$ be the distribution law of $A$. The chance that all values in $A$ exceed $x_m$ is

$$(1 - F(x_m))^k.$$

Consequently, since $1\le m\lt N$, the solution in general is

$$\sum_{m=1}^{N-1} (G(x_m)^k - G(x_{m-1})^k)(1 - F(x_m))^k.$$

In the present setting $G(x_m) = F(x_m) = m/N$ because all values have equal probabilities. For the dice, $N=6$ and $k=3$, giving $481/15552 \approx 0.0309285$ for the answer.

If we were to draw the cards with replacement, $N=32$, giving $\frac{3056755}{67108864} \approx 0.0455492$.

### The limiting game: both players draw without any replacement

This is the easiest of the three: of the $\binom{2k}{k}$ different and equiprobable configurations of the relative orders of $A$ and $B$, in only one do all elements of $B$ precede those of $A$. The chance of this therefore equals

$$\frac{1}{\binom{2k}{k}} = \frac{(k!)^2}{(2k!)}.$$

When $k=3$, this is $1/20 = 0.05$. Its closeness to the preceding answers--$0.037$ and $0.031$--gives us some assurance those answers are in the right ballpark. The simplicity of this formula also lets us approximate the answer when $n$ is large.

Mathematica computed the exact solutions quoted here. The following R code also computes them (in double precision rather than exactly) and runs simulations to evaluate the correctness of the analytical solutions. These simulations conduct repeated z-tests of the solutions. The mean of the z-values should be zero, but will differ slightly due to random variation. The distribution of the z-values should be approximately Standard Normal (with a little allowable deviation due to the small finite values of $n$ and $k$). Here they are (for 999 iterations each), demonstrating the accuracy of these answers:

#
# Simulate a solution and, optionally, test it against an expected value.
#
f <- function(n, k, n.iter=1e3, replace=TRUE, expectation) {
sim <- replicate(n.iter, {
max(sample(1:n, k, replace=replace)) < min(sample(1:n, k, replace=replace))
})
p <- mean(sim)
if (missing(expectation)) return(p)
se <- sqrt(p*(1-p)/n.iter)
return ((p - expectation) / se)
}
#
#
expectation <- function(n, k) {
z <- lgamma(n+1) + lchoose(n-k, k) + 0.5*log(pi)
z <- z - 2*k*log(2) - lgamma(n-k+1) - lgamma(k+1/2)
y <- 2 * lchoose(n, k)
exp(z - y)
}
expectation.replace <- function(n, k) {
g <- (0:n / n)^k
f <- rev(g)[-1]         # Chance the min of k values exceeds m
g <- g[-1] - g[-(n+1)]  # Chance the max of k values is m
sum(f * g)
}
#
# Show simulated and analytical answers.
#
c(expectation=expectation.replace(6, 3), simulated=f(6, 3, 1e5))
c(expectation=expectation(32, 3), simulated=f(32, 3, 1e5, FALSE))
#
# Run repeated tests of the two games.
# If the z-values approximate a standard Normal distribution,
# we can be confident the given expectation is correct.
#
par(mfrow=c(1,2))
z.values <- replicate(999, f(6, 3, replace=TRUE, expectation=expectation.replace(6, 3)))
hist(z.values, main="Dice (with replacement)")
abline(v=mean(z.values), col="Red", lwd=2)

z.values <- replicate(999, f(32, 3, replace=FALSE, expectation=expectation(32, 3)))
hist(z.values, main="Cards (without replacement)")
abline(v=mean(z.values), col="Red", lwd=2)

• Can you explain me a bit more this example with "The die game: drawing with replacement"? This formula Pr(min(aj)=m) is kinda confusing because I don't know where you derived it from. – anicicn Feb 27 '15 at 9:35
• @anicicn I added an explanation to this answer (and took the liberty of fixing some typographical errors). I also provided some working code to do the calculations and double-check the answers through simulation. – whuber Feb 27 '15 at 15:47
• Gee, thanks. You are an awesome guy. Really helped me a lot. God bless you! – anicicn Mar 1 '15 at 18:50

I didn't solve the problem analytically. However, I wrote a code in R to simulate it. For the cards the solution should be close to 4.5% and for the dice close to 3%. I hope this helps a bit in case to confirm an analytical solution.

n <- 10000 #number of trials
c <- rep(0,n)
d <- 32 #set to 32 for cards;  set to 6 for dice

for(i in 1:n){
A <- sample(1:d, 3, replace=T)
B <- sample(1:d, 3, replace=T)
c[i] <- ifelse(min(A)>max(B), 1, 0) #set element i in c to 1 if min(A)>max(B)
}

sum(c)/n #relative proportion of min(A)>max(B)