# Calculating probabilities related to order statistics

Crux of the question

Let $q \sim F$ with support $[0,1]$. Let $q_j$ be the $j$th order statistic of $N$ draws from $F$. Let $z_j \sim \text{Bernoulli}(q_j)$. See that these draws are independent, given the $q$ probabilities. We need to know $$\begin{equation*}\Pr(z_{1} = 0, \dots, z_{j-1} = 0 | q_{j} = x);\end{equation*}$$ in words, what's the chance of $j-1$ failures given the probability of success on the $j$th trial is $x$?

For a known $F$, sequence $z_1, \dots z_{j-1}$, and a particular $x$, how can we find this probability? Some kind of simulation might do it, but I'd be integrating this probability over continuous $x$, seemingly ruling out a simulation strategy (this probability is a component in an application of Bayes' rule---see below).

Background

Scenario: I look through a page of search results, clicking on the first, then the second, and so on down the list until I find the information that I seek. I want to estimate the probability that the next site that I visit is the right one, given that the others that I have visited were not.

Each site has a certain probability of being the right one for me of $q_j$; we can think of this as saying that fraction $q_j$ of the population finds what they are looking for on a given site. There may be many sites that fulfill a viewer's needs, so these probabilities do not sum to 1. Let $z_j$ be an indicator for site $j$ fulfilling my needs. After visiting site $j$, I only learn $z_j$, not $q_j$.

Imagine each site reaching into a distribution $F$ to find its $q_j$. Then, the sites are placed in decreasing order of $q$. Hence, $q_j$ is the $j$th order statistic after $N$ draws from $F$.

I want to calculate \begin{align*} \bar{q}_{j} &= \text{E}[q_{j} | z_{1} = 0, \dots, z_{j-1} = 0] \\ &= \int_0^1{x\Pr(q_{j} = x | z_{1} = 0, \dots, z_{j-1} = 0) \,\text{d}x} \\ &= \int_0^1{x\frac{\Pr(z_{1} = 0, \dots, z_{j-1} = 0 | q_{j} = x)\Pr(q_{j} = x)}{\Pr(z_{1} = 0, \dots, z_{j-1} = 0)} \,\text{d}x} \\ &= \frac{\int_0^1{x\Pr(z_{1} = 0, \dots, z_{j-1} = 0 | q_{j} = x)\Pr(q_{j} = x)\,\text{d}x}}{\Pr(z_{i1} = 0, \dots, z_{j-1} = 0)} \\ &= \frac{\int_0^1{x\Pr(z_{1} = 0, \dots, z_{j-1} = 0 | q_{j} = x)\Pr(q_{j} = x)\,\text{d}x}}{\int_0^1{\Pr(z_{1} = 0, \dots, z_{j-1} = 0 | q_{j} = x)\Pr(q_{j} = x)\,\text{d}x}}. \end{align*}

This is a standard application of Bayesian updating techniques. The problem, however, is that there isn't a single parameter to be updated---$q$ varies across the sites.

Two ways to get around the problem are to use heuristics: for the sake of calculation, (a) $q$ is assumed to be the same across sites or (b) $q$ is assumed to change in a predictable way, e.g., $q_j = q_1 - a(j-1)$ with known $a$, giving updating over a single parameter $q_1$. Case (a) would give an estimate that is always too big. In either case, the prior distribution $\Pr(q_j=x)$ can use the order statistic properties of $F$.

Another approach would be to assume that I know $F$ and to use the fact that we have order statistics. But, for a given $x$ in this integral, there isn't a unique set of probabilities for sites 1 to $j-1$. For example, in the case of $j=2$ and in calculating the integral for the case $q_2=x$, $\Pr(z_1=0)$ could fall anywhere between 0 and $1-x$. The question becomes which of these values to plug in? One obvious answer would be the expected value of each order statistic. This doesn't seem like it works to me. We might be able to simulate the quantity inside the integral for each value of $x$, but integrating across continuous $x$ seems to make this approach too intensive a strategy.

-
add comment