3
$\begingroup$

I am dealing with an interesting probability problem. I had $16$ subjects randomly divided into $4$ different rooms, each room having $4$ seats. The subjects were given a question to solve. We knew from our prior experience that only $50\%$ people could solve the problem. In our study, $7$ of the $16$ people solved and the others couldn't solve the problem. Both the solving times and the giving up times were recorded. So there were $7$ ordered solving times and $9$ ordered giving up times in our hands at the end of the study.

A subject is selected for the next task if he is the $1st$ solver of the $1st$ room or the $2nd$ solver of the $2nd$ room or the $1st$ solver of the $3rd$ room or the $2nd$ solver of the $last$ room. So, it constitutes something close to a ranked set sample for the next task.

I want to find out the probability that the subject having the 5th ordered solving time was the $1st$ solver of the $1st$ room or the $2nd$ solver of the $2nd$ room or the $1st$ solver of the $3rd$ room or the $2nd$ solver of the $last$ room. That is, I want to find out the probability of the $5th$ ordered solver to be selected for the next task.

Now, for being selected for the next task he should be able to solve the problem and the room he belongs to should have at least the necessary number of solvers. Say, a subject was randomly assigned to room $4$, solved the problem, but room $4$ had only $1$ solver, then he could not be selected for the next task. So, the probability for ordered subject $i$ seems like,

$P(\text{i gets selected for the next task}|\text{i solves the problem}, \text{the room it falls into has at least necessary number of solvers}).$

The probability seems to me like $P(A|B,C)$ where events $B$ and $C$ are independent. How do I accurately calculate the probability? It seems complicated.

Thanks in advance for any help!

$\endgroup$
4
$\begingroup$

Let's solve a related problem first, because it holds the key to this one.

Suppose $F$ is a continuous distribution. (It will model the solving times.) Let $X_i, i=1, \ldots, n$ and $Y_j, j=1, \ldots, m$ be iid random variables governed by $F$. Write $f(n,m,k,j)$ for the chance that the $j^\text{th}$ largest of the $Y$'s is the $k^\text{th}$ largest value among both the $Y$'s and $X$'s.

Since the variables are iid, they are exchangeable. This implies that $f(n,m,k,j)$ counts the proportion of permutations of the multiset $\{0^n, 1^m\}$ in which

  1. The first $k-1$ values contain exactly $j-1$ $1$'s. This can be done in $\binom{k-1}{j-1}$ ways.

  2. The $k^\text{th}$ value is a $1$.

  3. And therefore there are exactly $m-j$ $1$'s distributed among the remaining $n+m-k$ values. This can be done in $\binom{n+m-k}{m-j}$ ways.

The total number of such permutations is $\binom{m+n}{m}$. Therefore

$$f(n,m,k,j) = \frac{\binom{k-1}{j-1}\binom{n+m-k}{m-j}}{\binom{m+n}{m}}.$$


Solution

Set the solving times of any non-solvers to random times larger than any of the actual solving times. There is no difficulty with this because (1) the fifth best solver, on whom we will focus, really did solve the problem and has an actual solving time; and (2) we will only be comparing solving times in such a way that positions all non-solvers behind all solvers.

Let the $Y_j$ be the $m=4$ solving times in any given room. The $X_i$ are the remaining $n=12$ solving times in the other rooms.

  • The chance that the first solver (i.e., $j=1$) is the fifth best overall (i.e., $k=5$) is $f(12,4,5,1)=33/364$.

  • The chance that the second solver is the fifth best overall is $f(12,4,5,2)=11/91$.

It is not possible that the fifth best solver overall was in two rooms--but she had to be in some room. Therefore the events "the fifth best solver overall was in room $i$", for $i=1,2,3,4$, are an exhaustive partition of the possibilities. Consequently their chances add up. Since in rooms 1 and 3 we are looking at the best solver and in rooms 2 and 4 the second best solver, the answer is

$$2f(12,4,5,1) + 2f(12,4,5,2) = 11/26 \approx 0.423.$$


Checking the Answer

Probability calculations can be tricky. I checked the calculation of $f$ with exhaustive enumeration of the $\binom{16}{4}=1820$ cases. But since $f$ is only indirectly involved in the solution, it might help to simulate the experiment itself, omitting no detail. To do this (in R) we may

  • Generate seven solving times (with runif). I use a uniform distribution for this, because the choice of distribution does not matter: only the assumption of continuity is relevant.

  • Distribute those times randomly across four rooms of four people (with sample and matrix).

  • Check whether the fifth smallest time is the smallest in rooms 1 and 3 or the second smallest in rooms 2 and 4 (with sort and %in%).

After five seconds to perform 10,000 iterations the output (which includes an error estimate of twice the standard error) is

Estimate is 0.426 +/- 0.0099

This agrees beautifully with the previous result. The code itself may be of some value in understanding the theoretical solution, so here it is.

#
# Describe the situation.
#
n.rooms    <- 4
n.per.room <- 4
n.solved   <- 7
ranks      <- c(1,2,1,2)
k          <- 5
#
# Perform the simulation.
#
set.seed(17)
n.iter <- 1e4
n <- n.rooms * n.per.room
unsolved <- rep(NA, n-n.solved)
sim <- replicate(n.iter, {
  x <- apply(matrix(sample(c(runif(n.solved), unsolved), n), 
                    n.per.room, n.rooms), 2, sort, na.last=TRUE)
  sort(x)[k] %in% x[cbind(ranks, 1:n.rooms)]
})
#
# Report the results.
#
p.hat <- mean(sim)
cat(paste("Estimate is", round(p.hat, 3), "+/-", 
          round(2*sqrt(p.hat*(1-p.hat)/n.iter), 4)), "\n")
$\endgroup$
  • $\begingroup$ Dear whuber, thanks for your brilliant solution to this problem. In fact the verification of the answer was so nice of you! I was thinking the probability will be something like: $\frac{P(\text{k gets the next task)}}{\text{P(k solves the problem)}\text{P(there are at least j solvers)}}$. Could you please tell me why we didn't need something like that in the denominator? Are these two conditions automatically satisfied? $\endgroup$ – Blain Waan Jan 22 '15 at 5:53
  • $\begingroup$ The other think I am still struggling to understand is: how the assumption that "the solving times of any non-solvers are larger than any of the actual solving times" helped us get the right probability. Could you please explain it in plain language for me? I'm grateful for your kind help. Thanks a lot. $\endgroup$ – Blain Waan Jan 22 '15 at 5:56
  • $\begingroup$ The code makes this obvious. It sets the non-solver times to "NA" (at unsolved <- rep(NA, n-n.solved)). That is guaranteed to cause problems if ever those values are used in the calculation, but no problems ever show up. As to your first comment, I do not see how such a fraction would be justified on the basis of the rules of probability. So it's not for me to say why it's not applicable: it's up to you to say why it is. The key to this solution is it doesn't use conditional probability at all. It only adds the probabilities of a union of mutually exclusive events--that is axiomatic. $\endgroup$ – whuber Jan 22 '15 at 16:33

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.