erank: Expected rank under the Harville model.

Description Usage Arguments Details Value Note Author(s) Examples

View source: R/RcppExports.R

Description

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

Usage

1
erank(mu)

Arguments

mu

a vector giving the probabilities. Should sum to one.

Details

Given the vector μ, 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

π_{1,i} = \frac{μ_i}{∑_j μ_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 μ, 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} - ∑_j \frac{μ_i}{μ_i + μ_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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# 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))
}

ohenery documentation built on Oct. 30, 2019, 9:53 a.m.