4
$\begingroup$

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.

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

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:

Figure

#
# 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)
}
#
# Compute the analytical answers.
#
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)
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – anicicn Feb 27 '15 at 9:35
  • $\begingroup$ @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. $\endgroup$ – whuber Feb 27 '15 at 15:47
  • $\begingroup$ Gee, thanks. You are an awesome guy. Really helped me a lot. God bless you! $\endgroup$ – anicicn Mar 1 '15 at 18:50
2
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.