erank {ohenery}R Documentation

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 iith element is assigned value 1 is

π1,i=μijμj.\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 kk elements in μ\mu, then the iith element can be assigned any place between 11 and kk. This function computes the expected value of that random variable.

While a naive implementation of this function would take time factorial in kk, this implementation takes time quadratic in kk, since it can be shown that the expected rank of the iith element takes value

ei=k+12jμiμi+μj.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 shabbychef@gmail.com

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


[Package ohenery version 0.1.1 Index]