Распределение разностей порядковых статистик

soldatiki

Бросаем N случайных точек x(i) в отрезок [0, 1] равномерным образом.
Сортируем. Пусть y(i) -сортированная последовательность.
Строим разности d(i) = y(i) - y(i-1 для первой точки берем d(1) = y(1) + 1 - y(N) = сумма расстояний от первой точки до нуля плюс "хвостик" от последней точки до единицы.
Внимание, вопрос (бдзыыыннннь):
1) как распределены d(i)?
2) хотим, чтобы d(i) были "примерно одинаковые" (= имели низкую дисперсию по какому распределению нужно бросать исходные точки x(i чтобы этого добиться, при условии, что количество точек N заранее дано?
P.S. Задача оригинально из проблемы Load Balancing для кластерных вычислений: там x(i) - это хэш-коды чанков с данными, а d(i) - диапазоны хэшей, приходящиеся на чанк. Нужно, чтобы чанки получали примерно равные дипазоны.
http://en.wikipedia.org/wiki/Consistent_hashing

griz_a

Точно нужно склеивать последний и первые диапазоны? Это распределение уродует.
Если не творить такой трешатины, то все n+1 диапазон будут одинаково распределенными тогда и только тогда, когда исходные точки равномерно распределены.
При этом распределение будет с плотностью [math]$n(1-x)^{n-1} $[/math]
Это довольно известный факт, даже оценка на основе этого есть в статистике - оценка методом спейсингов.
Тогда доказывается в копейку - вариационный ряд (d_1, d_1+d_2,....,d_1+...d_n) (это я при приличном определении d_1) распределен равномерно в тетраэдре, поэтому последовательность разностей распределена как I_{d_1+...+d_n<1}, откуда видно, что они одинаково распределены, а значит также как d_1, т.е. как минимум, у которого известно как ищется распределение.
 

soldatiki

Первый и последний диапазон склеивают "по техническим причинам": алгорим, который находит чанк по хэш-коду z от данных, ищет ближайшее сверху y(i при этом если z > y(N то берется y(1). Думаю, что он будет так же прекрасно работать, если единицу всегда включать в качестве y(N). Но тогда распределения будут ОК.
Спасибо, попробую.

soldatiki

Попробовал. Ситуация почти не поменялась. Насколько я понимаю, у этого распределения среднее = 1 / (n + 1 а второй момент = 2 / (n + 2 дисперсия примерно 2 / n, то есть, разброс весьма большой по сравнению со средним.
Сейчас на самом деле процедура такая. Для каждого "чанка" берется не один диапазон, а разыгрывается k штук "представителей" x(i). Тогда в качестве вероятности попадания в чанк будет уже сумма длин соответствующих диапазонов d(i).
Распределение суммарных длин, как я уже сказал, получается не достаточно хорошим (всего 20 чанков, берется 20 отрезков для каждого чанка, 400 отрезков всего):
0 : 75.6
1 : 97.5
2 : 78.3
3 : 61.1
4 : 43.7
5 : 85.8
6 : 76.1
7 : 106.8
8 : 71.5
9 : 64.0
10 : 86.9
11 : 111.8
12 : 108.3
13 : 64.5
14 : 69.5
15 : 87.7
16 : 73.7
17 : 94.0
18 : 75.7
19 : 72.5
Это суммарные длины в "условных единицах" для каждого из чанков. Средняя длина тут около 80, но попадаются чанки, на кого пришлось больше 100. Требуется сделать, чтобы было не более 90.
Как можно улучшить? У меня такие мысли:
- поделить отрезок [0,1] на m частей, к каждой части применить процедуру независимо, причем в каждой части брать одинаковое число k / m представителей для каждого чанка, тогда разброс суммарных длин, возможно, снизится по сравнению со случайным киданием k представителей во весь отрезок
- распределять представителей не сразу, а после сортировки длин отрезков d(i чтобы каждому чанку достались как маленькие, так и большие отрезки
- убрать часть самых больших и самых маленьких отрезков d(i переразыграв для них точки x(i повторить процедуру несколько раз, пока не будет удовлетворительный разброс длин d(i)
Как думаете, имеет это смысл? Понятно, что можно взять и проверить (так я сейчас и делаю но хочется знать, что тут происходит с точки зрения науки.

griz_a

Я не очень понимаю, что вообще нужно. Видимо, нужна какая-то случайность, нельзя просто взять равные промежутки? Насколько большая и с какой целью - не знаю

soldatiki

Равные промежутки нельзя взять из-за того, что должна быть возможность добавлять/удалять чанки без большого перераспределения данных. При равных промежутках исключение одного из них приведет к большому "переколбасу" оставшихся.
Думаю, что в качестве решения сгодится процедура, которая динамически корректирует отрезки, например, так: находит экстремально маленькие и большие и пытается их границу сдвинуть в сторону соседа или от него, предполагая, что соседний интервал "нормальный". Так за несколько проходов можно "подровнять" отрезки. При этом возникающее перераспределение данных относительно небольшое, так как аффектятся только соседи.

griz_a

Что такое "большой переколбас"? Если вы при среднем 80 не хотите иметь более 90, то вам придется перераспределить с десяток.
Наиболее простой механизм - это когда вы рассматриваете (X_1,...,X_n|X_1+....+X_n = 1 где X_i - н.о.р. (хотя на самом деле симметрично зависимых хватит). Можно брать различные распределения для X, получая разные итоги.
Ваш исходный вариант - это когда X_i экспоненциальны. Если экспоненциальность для вас слишком большую дисперсию дает - возьмите какие-нибудь величины, у которых меньшее соотношение среднего и стандартного отклонения.

soldatiki

Не хотелось изначально лезть в детали исходной задачи, так как она из программирования, больше инжинерная, но в ней вырисовалась математическая подзадача.
А исходная проблема такая.
Есть некий Load Balancer, задача которого - в ответ на имя файла выдавать номер хранилища (чанка где лежит этот файл. В качестве такого отображения используется следующая процедура. Все пространство 128-разрядных целых чисел разбивается на диапазоны. От имени файла вычисляется хэш-код. Смотрим, в какой диапазон мы попали. Каждому диапазону отнесен чанк. Одному чанку соответстует не один, а несколько (порядка 200) дипазонов.
Так сделано потому, что:
- отображение должно быть "арифметическим" (не хотим держать просто словарь имя_файла -> номер_чанка, так как файлов много, словарь будет большой)
- много диапазонов для одного чанка - потому что тогда при удалении чанка из хранилища (например, устрйство хранения нужно отключить или заменить) его отрезки удалятся и таким образом автоматом "раздадутся" НЕСКОЛЬКИМ (в идеале - всем) остальным чанкам - поэтому порядок отрезков случайный, чтобы после отрезков одного шли отрезки многих других
- аналогично при добавлении нового чанка мы добавляем точки разбиения случайным образом, какие-то отрзки при этом разбиваются на две части, одна из которых теперь будет обслуживаться новым чанком; так как порядок отрезков был случайным относительно номеров чанков, то новый чанк "отберет" часть данных у НЕСКОЛЬКИХ (в идеале - у всех) других, сохраняя таким образом баланс загрузки
- при обавлении-удалении чанка мы должны поменять разбиение диапазлна чисел и, как следствие, переместить соответстввующие данные с одного устройства хранения на другое, так вот нужно еще и минимизировать траффик, который получается при модификации разбиения.
Без последнего требования, разумеется, можно просто поравну делить весь дипазон каждый раз и переливать все данные в соответствии с новым разбиением. Но очевидно, что это большие накладные расходы. Поэтому тут и выбран подход через случайное разбиение, потому что его можно инкрементально доразбить или наооборот убрать некоторые точки.

soldatiki

Насчет того, чтобы сразу разыгрывать длины отрезков, а не точки разбиения - да, я тоже сразу подумал об этом. Но, во-вепрых, тогда неясно, как потом избежать большого копирования данных при переходе от одного разбиения такого рода к другому (добавления-удаления новых чанков а во-вторых, в задаче у меня изначально данные выложены по вот тому кривому разбиению, и от него уже нужно перейти к другому, также по возможности не перемещая большое количество данных.
То есть, по сути надо придумать политику разбиения отрезка, такую что:
- для каждого N имеем разбиение, при котором на каждый чанк приходится примерно один объем (распределение объема имеет низкую дисперсию)
- при добавлении/удалении чанка перемещается не более чем c*V данных, где V - объем данных в чанке, c - константа, "не сильно больше единицы", то есть overhead небольшой по сравнению с необходимым объемом перемещаемых данных
- необходимо стартовать с текущего разбиения (у которого с дисперсией, как выяснилось, проблемы) и также постараться минимизировать overhead при переходе к "правильному" разбиению

griz_a

Я бы стартовал с того, что разбил бы, скажем, на в 10 раз большее число отрезков, а потом объединил их по 10. Дисперсия уменьшится в 10 же раз

soldatiki

Покурил еще над задачей и понял, что из распределения длин больше не выжать в принципе. При увеличении количества отрезков на чанк в 100 раз дисперсия суммарных длин уже около 1-2 процентов, то есть, фактически все чанки полчуают равный объем. В реальной же задаче есть еще перекос из-за разного размера файлов (распределение размеров нормальное). То есть, по-любому тогда нужна динамическая процедура, которая будет менять распределение отрезков непосредственно под данные.
Все, спасибо, с вами было приколько общаться, господа.
Оставить комментарий
Имя или ник:
Комментарий: