Хотите знать, почему можно рассчитать медиану таким образом?

Question

Мне было интересно, что может быть причиной использования этой медианной функции вместо простого вычисления min + (max - min) / 2:

// used by the random number generator
private static final double  M_E12 = 162754.79141900392083592475;

/**
 * Return an estimate of median of n values distributed in [min,max)
 * @param min the minimum value 
 * @param max the maximum value
 * @param n 
 * @return an estimate of median of n values distributed in [min,max)
 **/
private static double median(double min, double max, int n) 
{
    // get random value in [0.0, 1.0)
    double t = (new Random()).nextDouble();

    double retval;
    if (t > 0.5) {
        retval = java.lang.Math.log(1.0-(2.0*(M_E12-1)*(t-0.5)/M_E12))/12.0;
    } else {
        retval = -java.lang.Math.log(1.0-(2.0*(M_E12-1)*t/M_E12))/12.0;
    }
    // We now have something distributed on (-1.0,1.0)
    retval = (retval+1.0) * (max-min)/2.0;
    retval = retval + min;
    return retval;
}

Единственным недостатком моего подхода может быть его детерминированность, я бы сказал?

Весь код можно найти здесь, http://www.koders.com/java/fid42BB059926626852A0D146D54F7D66D7D2D5A28D.aspx?s=cdef%3atree#L8, кстати.

Спасибо

Answer 1

[пытаясь охватить диапазон здесь, потому что мне не ясно, что вы не понимаете]

сначала медиана - это значение middle . Медиана [0,0,1,99,99] составляет 1.

и, таким образом, мы видим, что данный код не вычисляет медиану (он не находит среднего значения). вместо этого он оценивает из некоторого теоретического распределения. как говорится в комментарии.

форум, который вы даете, предназначен для середины. если многие значения равномерно распределены между min и max, тогда да, это хорошая оценка медианы. в этом случае (предположительно) значения не распределяются таким образом, поэтому необходим какой-то другой метод.

Вы можете понять, почему это может быть необходимо, вычислив среднюю точку чисел, приведенных выше - ваша формула даст 49,5.

причина использования оценки , вероятно, в том, что она намного быстрее, чем поиск медианы. причина сделать эту оценку случайной , скорее всего, поможет избежать наихудшего случая при нескольких вызовах.

и, наконец, извините, но я не знаю, что такое дистрибутив в этом случае. вам, вероятно, нужно найти структуру данных и / или имя автора, чтобы узнать, сможете ли вы найти справочную статью или книгу (я подумал, что это может быть степенной закон, но см. правку ниже - кажется, добавляется очень небольшое исправление ) (Я не уверен, что это то, о чем вы спрашиваете, или вы более смущены).

[править] Еще немного, я думаю, что журнал (...) дает центральное смещение для равномерно случайного t. так что это в основном то, что вы предлагаете, но с некоторым разбросом около 0,5. Вот график одного случая , который показывает, что retval на самом деле довольно маленькая корректировка.

Answer 2

Я не могу сказать вам, чего пытается достичь этот код;для начала он даже не использует n!

Но, судя по всему, он просто генерирует некое экспоненциально распределенное случайное значение в диапазоне [min,max].См. http://en.wikipedia.org/wiki/Exponential_distribution#Generating_exponential_variates.

---

Интересно, что поиск в Google для этого магического числа вызывает множество соответствующих попаданий, ни один из которых не освещает: http://www.google.co.uk/search?q=162754.79141900392083592475.