Speed up median(Binomial)

[andreasnoack]

While it's good that the result is now correct, it is at a significant price. The evaluation of the cdf is quite costly and I think the quantile approach might end up calling it multiple times. Of course q=0.5 might be special cased in RMath but compare

# Old version
julia> @btime median(X)
  15.030 ns (0 allocations: 0 bytes)
8

julia> @btime quantile(X, 0.5)
  242.180 ns (0 allocations: 0 bytes)
7

It might be possible, at least in most cases, see https://onlinelibrary.wiley.com/doi/10.1111/j.1467-9574.1980.tb00681.x, to compute the median without evaluating the cdf or even the pdf.

The old version just used round but, as pointed out in #1923, that wasn't always correct. The paper helps us

In #1923, the example had X = Binomial(25, 0.3) so the condition is clearly not satisfied since

julia> mean(X)
7.5

so we could just do a single (c)cdf evaluation and adjust the value if needed in the cases where the condition of Theorem 1 isn't satisfied. It is likely to be much faster than quantile(..., 0.5)

[marcusps]

Good point. It should take no more than one cdf evaluation, right? And by the theorem you quote, sometimes no evaluations.

function median(rv::Binomial)
    bound = min(rv.p, 1-rv.p)
    rv_mean = mean(rv)
    floor_mean = floor(Int, rv_mean)
    ceil_mean = ceil(Int, rv_mean)
    if abs(floor_mean - rv_mean) <= bound
        floor_mean
    elseif abs(ceil_mean - rv_mean) <= bound
        ceil_mean
    elseif cdf(rv, floor_mean) > 0.5
        floor_mean
    else
        ceil_mean
    end
end

[devmotion]

I thought it would be most important to fix the bug, and that we should improve performance separately 🙂 I had actually seen this result on Wikipedia, together with a few other properties of the median: https://en.m.wikipedia.org/wiki/Binomial_distribution#Median But I wasn't sure if that list is conclusive or whether there are additional properties that we could exploit, so I assumed it might take a bit more time to discuss and release such performance improvements.