Элементы асимптотического геометрического анализа
Функция концентрации меры на кубах Хемминга

Морозов Владимир Владимирович,
учитель математики и информатики
НОУ частной школы "Ступени", Москва.

Изучая работу [2] и лично общаясь с автором, мы поставили себе цель наглядно представить себе поведение функции концентрации меры на пространствах большой размерности на примере куба Хемминга и написать компьютерную программу для построения графика функции концентрации меры.

Вопросы асимптотического геометрического анализа излагаются в [1‑5].

Сначала введём некоторые понятия.

Определение. Пусть . Кубом Хемминга размерности  назовём множество всех двоичных строк длинны . Обозначим его .

Таким образом, типичный элемент куба Хемминга – это строка длины , состоящая из нулей и единиц: , где .

На кубе Хемминга  введём метрику, расстояние между любыми двумя строками куба Хемминга: расстоянием между двумя словами длинны n куба Хемминга будем считать равным количеству несовпадающих символов этих слов.

Очевидно, что для расстояния Хемминга выполняются следующие свойства.

1. ;

2.   (симметричность);

3.  (неравенство треугольника).

Определение. Диаметром конечного метрического пространства  назовём число .

Легко видеть, что диаметр куба Хемминга равен n, диаметр куба Хемминга зависит от его размерности.

Для того чтобы диаметр куба Хемминга не зависел от размерности, определим нормализованную метрику на кубе Хемминга. Нормализованное расстояние между двумя словами куба Хемминга будем считать равным количеству несовпадающих символов этих двух слов, поделённому на размерность куба, n.

Очевидно, что диаметр куба Хемминга относительно нормализованной метрики равен 1, не зависит от размерности. Далее будем пользоваться нормализованным расстоянием Хемминга.

На множестве  введём также меру – аналог площади или объёма. Сколько элементов во множестве ? Сколько всевозможных строк длинны n из нулей и единиц можно построить? Решая эту простую комбинаторную задачу, получаем:

.

Определение. Пусть А – произвольное подмножество куба Хемминга: . Нормализованной мерой множества А будем считать число , где  – число элементов множества А.

Легко видеть, что

1) , нормализованная мера куба Хемминга также не зависит от размерности;

2) ;

3) если , то .

Определение. Пространство Х с мерой  и метрикой d называется mm-пространством.

Таким образом, куб Хемминга является mm-пространством.

Для mm-пространств вводится понятие функции концентрации меры.

Определение. Пусть , пусть . Будем называть e-утолщением множества B множество .

Определение. Функцией концентрации куба Хемминга  назовём функцию

В [2] доказано, что функция концентрации меры n-мерного куба Хеммнга удовлетворяет неравенству . Именно этот результат побудил нас построить график функции концентрации меры куба Хемминга с помощью компьютера.

Проблема заключается в том, что если пытаться писать компьютерную программу, вычисляющую функцию концентрации меры непосредственно по определению, то эта программа перебирала бы всевозможные наборы строк, наборы, в которых ровно половина строк, в каждом таком наборе 2^n-1 строк. Сколько способов выбора таких наборов? . Для каждого такого набора программа строила бы e-утолщение, считала количество слов в e-утолщении и его меру. Из всех таких мер находила бы минимальную меру и полученное число вычитала бы из 1. Естественно, с ростом размерности n вычисления возрастали бы катастрофически, и дать полезный и удовлетворительный результат программа не смогла бы.

Положение спасает…

Теорема Харпера. Пусть В – шар радиуса e в кубе Хемминга. Пусть .

Тогда В имеет наименьшую границу (то есть 1/n-утолщение) из всех множеств той же меры m.

Важное наблюдение. Дополнение любого шара в кубе Хемминга снова шар. Дополнение шара с центром в строке ‘000…0’ – это шар с центром в ‘111…1’. Для того, чтобы получить шары с другими центрами в кубе Хемминга, следует прибавить к каждому элементу данных шаров любое фиксированное слово, сложение предполагается по модулю 2. Перебирая всевозможные радиусы и прибавляя по модулю 2 всевозможные строки, мы получаем всевозможные шары в кубе Хемминга.

Пусть В – шар радиуса ½. Тогда мера этого шара – сумма первых n/2 биномиальных коэффициентов, поделённых на 2, если n – чётно; таким образом, мера шара радиуса ½ равна ½, если n – чётно и больше ½, если n – нечётно.  

Пусть теперь А – произвольное подмножество куба Хемминга меры ½.

В соответствии с результатом Харпера, минимум мер e-утолщения множества А – это мера шара радиуса e+0.5. Следовательно, функция концентрации меры  равна мере шара радиуса 0.5-e, если  , и , если e>0.5.

Осталось написать программу на языке Pascal для вычисления меры шара радиуса 0.5-e и построения графика функции концентрации меры куба Хемминга.

program Hamming;

{Построение графика функции концентрации меры }

  uses crt, graph, graphpl;

  const n=1023; {Размерность куба Хемминга }

  var ee:double; k:longint;

  function measure(eps:double):double; {Вычисление меры шара радиуса eps}

    var m,a,p:double;

        k,i:longint;

    begin

      a:=1;

      k:=trunc(eps*n);

      p:=1;

      for i:=1 to n do

        p:=2*p;

      if eps>0

        then

          m:=1/p

        else m:=0;

      for i:=1 to k do

        begin

          a:=a*(n-i+1)/i; {Очередной биномиальный коэффициент}

          m:=m+a/p;

        end;

      if eps=1/2

        then

          measure:=1/2

        else

          measure:=m

    end;

    procedure graphic; {Процедура построения графика функции концентрации}

      var i,j:integer;

          eps:double;

      begin

        opengraph;

        line(10,440,610,440);

        line(10,440,10,40);

        for i:=0 to 600 do

          begin

            eps:=i/1200;

            j:=440-trunc(measure(1/2-eps)*800);

            putpixel(i+10,j,14);

            if i = 0 then Circle(i+10,j,2)

          end

      end;

begin {Основной модуль}

  TextColor(14);

  TextBackGround(1);

  ClrScr;

  for k:=0 to (n div 2) do

    begin

      ee:=k/n;

      writeln('k=',k:4,' alfa=',measure(1/2-ee));

    end;

  readln;

  graphic;

  repeat until keypressed;

  closegraph

end.

Результат работы программы

График функции концентрации меры куба Хемминга размерности 10

График функции концентрации меры куба Хемминга размерности 100

График функции концентрации меры куба Хемминга размерности 500

График функции концентрации меры куба Хемминга размерности 1023

Максимальная размерность куба Хемминга, с которой программа на языке Pascal справилась – 1023. Это очень неплохой результат. Но если такая размерность не устраивает читателя, то приведённый выше алгоритм легко перенести в Delphi, используя тип int64.

Вывод. В результате проведённого исследования и работы программы мы ясно видим, что с ростом размерности куба Хемминга функция концентрации меры убывает всё стремительней. Это означает, что ничтожно малое утолщение множества меры ½ имеет меру, чрезвычайно близкую к 1. Именно это свойство пространств большой размерности далеко не очевидно и привлекает современных математиков к изучению асимптотического геометрического анализа.

Список литературы 

1.     Kecris A. S., Pestov V. G., Todorcevic S. Fraïssé Limits, Ramsey Theory, and Topological Dynamics of Automorphism Groups. Department of Mathematics and Statistics, University of Ottawa.

2.     Vladimir Pestov. Elements of Asymptotic Geometric Analysis. School of Mathematical and Computing Science, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand.

3.     Vladimir Pestov. Topological Groups: Where To From Here? School of Mathematical and Computing Science, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand.

4.     Vladimir Pestov. Some Universal Constructions in Abstract Topological Dynamics. School of Mathematical and Computing Science, Victoria University of Wellington, Wellington, New Zealand.

5.     Vladimir Pestov. MM-spaces and Group Actions. Department of Mathematics and Statistics, University of Ottawa.