ohenery (version 0.1.1)

erank: Expected rank under the Harville model.

Description

Compute the expected rank of a bunch of entries based on their probability of winning under the Harville model.

Usage

erank(mu)

Arguments

mu

a vector giving the probabilities. Should sum to one.

Value

The expected ranks, a vector.

Details

Given the vector \(\mu\), we compute the expected rank of each entry, under the Harville model, where tail probabilities of winning remain proportional.

Under the Harville model, the probability that the \(i\)th element is assigned value 1 is $$\pi_{1,i} = \frac{\mu_i}{\sum_j \mu_j}.$$ Once an element has been assigned a 1, the Harville procedure removes it from the set and iterates. If there are \(k\) elements in \(\mu\), then the \(i\)th element can be assigned any place between \(1\) and \(k\). This function computes the expected value of that random variable.

While a naive implementation of this function would take time factorial in \(k\), this implementation takes time quadratic in \(k\), since it can be shown that the expected rank of the \(i\)th element takes value $$e_i = k + \frac{1}{2} - \sum_j \frac{\mu_i}{\mu_i + \mu_j}.$$

Examples

# NOT RUN {
# a garbage example
set.seed(12345)
mus <- runif(12)
mus <- mus / sum(mus)
erank(mus)

# confirm the expected rank via simulation
set.seed(123)
mus <- runif(6,min=0,max=2)
mus <- mus / sum(mus)
set.seed(101)
emp <- rowMeans(replicate(200,rhenery(mu=mus,gamma=rep(1,length(mus)-1)))) 
(emp - erank(mus)) / emp

# }
# NOT RUN {
if (require(microbenchmark)) {
  p10 <- 1:10 / sum(1:10)
  p16 <- 1:16 / sum(1:16)
  p24 <- 1:24 / sum(1:24)
  microbenchmark(erank(p10), erank(p16), erank(p24))
}
# }