erank {ohenery}

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.

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 ith 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 ith 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 ith element takes value

e_i = k + \frac{1}{2} - \sum_j \frac{\mu_i}{\mu_i + \mu_j}.

Value

The expected ranks, a vector.

Note

we should have the sum of ranks equal to the sum of 1:length(mu).

Author(s)

Steven E. Pav [e-mail]

Examples

# 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


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))
}