Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/0students/2008-kr4-shnurnikov.pdf Дата изменения: Thu May 28 14:47:04 2009 Дата индексирования: Sat Apr 9 22:56:30 2016 Кодировка: Windows-1251

Московский Государственный Университет имени М.В. Ломоносова Механико-математический факультет Курсовая работа

Частные случаи гипотезы для независимых бернуллиевских случайных величин ai и вектора x = 1.
P (|
n i=1

a i xi |

1)

1 2

Выполнил студент 405 группы Шнурников И.Н. под рук. академика РАН Фоменко А.Т. 14 апреля 2008

1


Обзор работы:
В статье 2001 года А.Бен-Таал, А.Немировский и К.Рос доказали, что для всякого вектора (x1 , x2 , . . . , xn ) единичной длины x2 + x2 + ћ ћ ћ + x2 = 1 и всяких независимых в совокупности слуn 1 2 чайных бернуллиевских величин a1 , a2 , . . . , an (т.е. P (ai = 1) = P (ai = -1) = 1 ) верно неравенство 2
n

P (|
i=1

ai x i |

1)

1 3

n

и выдвинули гипотезу

P (|
i=1

ai x i |

1)

1 . 2

В настоящей работе доказаны: Теорема 1 гипотеза для n = 4, 5, 6. 1 Теорема 2 гипотеза для x1 = x2 = ћ ћ ћ = xn = n для любого n 3. Приведена геометрическая интерпретация гипотезы и теорем. К сожалению, метод линейных и квадратичных оценок в Т.1 и аналог центральной предельной теоремы в Т.2 дальнейших продвижений в гипотезе не дают.

1 величины с распределением P (ai = 1) = P (ai = -1) = 2 , где i = 1, 2, . . . n. Тогда для всяких 2 2 2 чисел x1 , x2 , . . . , xn со свойством x1 + x2 + ћ ћ ћ + xn = 1 верно неравенство n

Теорема 1. Пусть n = 4, 5 или 6. Пусть a1 , a2 , . . . , an независимые в совокупности случайные

Формулировки и доказательства:

P (|
i=1

ai xi |

1)

1 . 2

При n = 4, 5 добавим фиктивные числа x5 = x6 = 0, x6 = 0 и сведем Т.1 к случаю n = 6. Заменим случайные величины на всевозможные наборы из 6 чисел +1 или -1 каждое. Сформулируем, к чему свелась Т.1: Утверждение 1. Для всяких 6 чисел x1 , x2 , x3 , x4 , x5 , x6 со свойством x2 +x2 +x2 +x2 +x2 +x2 = 1 6 5 4 3 2 1 количество N (x) наборов 6 чисел a1 , . . . , a6 , каждое из которых +1 или -1, не превосходит 16. Доказательство утверждения 1 состоит в фиксировании и упорядочивании чисел x1 x2 x3 x4 x5 x6 , и в последовательном рассмотрении трех случаев: Случай а). Верно -x1 + x2 + x3 + x4 + x5 + x6 1, тогда для всякого набора a1 , . . . , a6 , что

ai xi > 1 верно a1 = 1 и x1 + i=2 (-ai )xi < 1, т.к. 2 2x1 = i=1 ai xi + x1 + i=2 (-ai )xi . Поэтому число N (x) не превосходит половины от количества всевозможных наборов из 5 чисел +1 или -1 каждое, т.е. N (x) 16. Теперь, исходя из -x1 + x2 + x3 + x4 + x5 + x6 > 1, получим следующие неравенства.
1 1 2 3 4 По неравенству Коши-Буняковского для чисел x1 , x2 , x3 , x4 : x1 +x2 +x3 +x4 4 4 2, поэтому x1 + x2 + x3 + x4 2 и x2 + x4 1. Предположив x1 + x2 - x3 + x4 - x5 - x6 1 и сложив с -x1 + x2 + x3 + x4 + x5 + x6 > 1, получим противоречие с x2 + x4 1, откуда получаем, что x1 + x2 - x3 + x4 - x5 - x6 < 1 и что существует не более одного набора a1 , . . . , a6 , состоящего из не 6 менее чем трех -1, такого что i=1 ai xi > 1. Отметим, что таких наборов ai с не более, чем одной -1, ровно 7, и для оценки N (x) осталось рассмотреть наборы с двумя -1. Случай б). Верно -x1 + x2 + x3 + x4 + x5 + x6 > 1 и -x1 + x2 + x3 + x4 + x5 - x6 1. Предположив дополнительно x1 - x2 + x3 - x4 + x5 + x6 > 1 и огрубив предположенное до x1 + x6 > 1, перемножим два неравенства, x6 > 1 - x1 и x2 + x3 + x4 + x5 + x6 > 1 + x1 : x2 +x2 +x2 +x2

6 i=1

6

6

6

1 - x2 = x2 + ћ ћ ћ + x2 1 2 6

x6 (x2 + ћ ћ ћ + x6 ) > 1 - x2 . 1 x3 +x4 +x5 -x6 1 и x1 -x2 +x3 -x4 +x5 +x6 1, тогда N (x) 7 + 8 + 1 = 16. и -x1 + x2 + x3 + x4 + x5 - x6 > 1. Предположив + x3 + x4 + x5 + x6 > 1, получим противоречие -1 не более 6, и тогда N (x) 7 + 6 + 1 = 14

Противоречие привело к совокупности -x1 +x2 + откуда искомых наборов ai с двумя -1 не более 8, и Случай в). Верно -x1 + x2 + x3 + x4 + x5 + x6 > 1 x1 + x2 - x3 + x4 - x5 + x6 1 и сложив с -x1 + x2 с x2 + x4 1. Поэтому искомых наборов ai с двумя

1 3 натуральное число и x1 = x2 = ћ ћ ћ = xn = n . Пусть a1 , a2 , . . . , an независимые в совокупности случайные величины с распределением P (ai = 1) = P (ai = -1) = 1 , 2 где i = 1, 2, . . . n. Тогда верно неравенство

Теорема 2. Пусть n

2


n

P (|
i=1

ai xi |

1)

1 . 2

Заменим случайные величины на всевозможные наборы ai из n чисел или -1 каждое. Если +1 n в наборе ai ровно k чисел -1 и i=1 ai > n, то (n - k ) - k > n, т.е. k < n-2 n . Количество наборов k ai с ровно k числами -1 равно Cn , поэтому
n

2n ћ P (
i=1

ai >



n) =
0 i<
n- n 2

i Cn .

Сформулируем, к чему свелась Т.2: Утверждение 2. Для всех натуральных n
n- n 2

3 верно неравенство:
i Cn < 2 n-2

0 i<

План доказательства утверждения 2: Для 3 n 15 вычислим обе части неравенства явно. k Для n 16 перепишем неравенство через сумму "центральных" Cn , оценим последние по формуле Стирлинга, а их сумму через e- 2 dt. Шаг 1. Составим таблицу из обеих i вании Cn для 3 n 15 : n 3456 7 n- n 1122 3 2 i Cn 1 1 6 7 29 2n-2 2 4 8 16 32
Для n
i 16 пользуясь Cn = C n-i n t
2

частей неравенства и количества участвующих в суммиро-

8 9 10 11 12 13 14 15 3 3 4 4 5 5 6 6 37 46 176 232 794 1093 3473 4944 64 128 256 512 1024 2048 4096 8192
n- n 2 n+ n 2 n- n i= 2 i Cn > 2 n-1

и n-

=

n+ n 2

, перепишем требуемое неравенство:

функцию энтропии H (x) = -x log2 x - (1 - x) log2 (1 - x) :
i Cn =

i Шаг 2. Оценим Cn , используя формулу Стирлинга n! = ( n )n ћ ( 2 ne e



n 12n

), где 0

n

1, и

n! = i!(n - i)! 2

nn i ћ (n - i)(n i
i nH n

-i)

ћ

2 n ћe 2 i2 (n - i) n ћe 4i(n - i)
1 -3

n-i i n 12n - 12i - 12(n-i)

ћ

2 ћ

n 4i(n-i)

.

Введем величину t =

i n

- 1 , выразим через нее 2
n 2

4 4i(n - i) = n

n 2

+ nt n

- nt

= n(1 - 4t2 )

и оценку

C

i n

2

1 nH t+ 2

2 e 3n(1-4t2 ) ћ . n(1 - 4t2 )

-

1

Определим функцию отрезок получился из |i - n | 2

f (t) := 2
n 2

1 nH t+ 2 -n

ћ

e

1 2nt2 - 3n(1-4t2 )



1 - 4t

2

на отрезке |t|

1 , 2n

. Преобразуем =e
3
n 1+2t - 2 ln(1-4t2 )-ntln 1-2t

2

1 nH t+ 2 -n

=2

1 1 n - 2 +t log2 (1+2t)- 2 -t log2 (1-2t)

,

для определения функции


h(t) := ln(f (t)) = 2nt2 -

1 - ntln 3n(1 - 4t2 )

1 + 2t 1 - 2t

-

n+1 ln(1 - 4t2 ), 2 t
1 2n

при

|t|

1 . 2n

Функция h(t) четная и h(0) = - 31 , покажем h (t) n и разложив вторую группу в ряд по степеням 2t :

0 при 0

, сгруппировав слагаемые

h (t) =

2t 8t - 1 - 4t2 3n(1 - 4t2 )2


+


2t 1 + 2t + 4nt - nln( ) 1 - 4t2 1 - 2t 2t 41 + 1 - 4t2 45
1 2n

=


2t 4 (1 - )+ 1 - 4t2 3n(1 - 4t2 )
так как n получим h(t)

(2t)
k=0 2

2k+1

- 2n
l=1

(2t)2l+1 2l + 1

(2t)2
k=0

k+1

1- t

2n(2t)2 2k + 3
1 2n

0,

16, 0

t
1 3n i n

1 8

и n(2t) и f (t)

1. Из четности h(t) и неотрицательности h (t), f (0) = e
-
1 3n

0

h(0) = -

для |t|

, откуда следует n . 2
x2 -2

C

2

n

2 e n

1 -2nt2 - 3n

,

n при n|t| = |i - | 2
x2 -2

Шаг 3. Из (e

x2 -2

) = (x2 - 1)e

x2 -2

получим выпуклость вверх функции e
b

любого отрезка [a, b], где -1 трапеция

a x2 -2

1, верно e
x -2
2

e
a

dx

(b-a)e

-

(a+b)2 8

при |x| < 1. Для

, поскольку криволинейная

(x, y )|a

x

b, 0

в силу выпуклости содержится в трапеции, отсекаемой
a+b 2

касательной к графику y = e

в точке

,e

-

(a+b)2 8

от полуполосы (a
1 x
2

x

b, 0

y ) . Ана-

логично получим для -1 a < a+b < 1 < b неравенство a e- 2 dx (b - a)e- 8 . Обозначим 2 множество целых чисел отрезка [ n-2 n , n+2 n ] за In и для каждого i In обозначим число i 2 n( n - 1 ) за xi , тогда по шагу 2 получим: 2

(a+b)2

C
i I
n

i n

2

n

2 e n

1 - 3n i I
n

e

x2 i -2

.

Оценивая e

x2 i -2


снизу через

n 2

1 min(xi + ,1) n

e-
1 max(xi - ,-1) n

x2 2

dx,

замечая maxi

I

n

2 xi > 1- , min n

i I

n

2 xi < 1+ : n

1-

C
i I
n

i n

2

n

1- e 2 x

1 n

1 3n -1+
1 n

e

x2 -2

dx.
1 - 3n

Шаг 4. Используя e

-x

1 - x при 0
1-
1 n

1, <
3 4

22 7

иn

16 получим: e

1-

1 3n

44 45

и

e
-1+
1 n

x -2

2

dx
3 -4

1-

87 x2 dx = 2 64

и

1 2

>

1 2

7 11

, поэтому

iI

n

i Cn > 2

n-1

77 87 81 80

>2

n-1

Замечание 1. При n верно
2
-n 0 i<
n- n 2

1 C 2
i n

-1

e
-

t2 -2

dt 0.158 < 0.25

4


Замечание 2. В книге А.Н. Ширяева "Вероятность" том 1, пар. 11 задача 2: Пусть ak независимые одинаково распределенные случайные величины с E ak = 0, Dak = 2 , E |ak |3 < . Тогда
P( a1 + ћ ћ ћ + an 1 )- n 2
x

e- 2 dt
-

t2

cE |a1 |3 n(1 + |x|)3
3

Что доказывает теорему 2 при условии малой константы c.

него единичная сфера x2 + x2 + ћ ћ ћ + x2 = 1. Будем писать, что касательная к сфере гиперплоскость n 1 2 отсекает вершину A куба, если точка A и центр сферы находятся строго по разные стороны от гиперплоскости . Пример. Гиперплоскость x1 + x2 = 2, касающаяся сферы в точке ( 22 , 22 , 0, . . . , 0), отсекает 2n-2 вершины, в точности те, у которых первые две координаты равны 1.

Определение. Дан n-мерный куб с координатами вершин (+1, +1, . . . , +1) Rn и вписанная в

Переформулировка гипотезы:

Утверждение 1(Фольклор). Дана точка x = (x1 , . . . , xn ) на единичной сфере x = 1. Пусть ai независимые случайные величины с распределением P (ai = 1) = P (ai = -1) = 1 , где 2 n 1 i = 1, 2, . . . , n. Тогда P (| i=1 ai xi | 1) 2 эквивалентно утверждению, что касательная гиперплоскость в точке x вписанной сферы отсекает не более чем 2n-2 вершин n-мерного куба.
Условие отсечения имеет вид i=1 ai xi > 1, где ai координаты отсекаемой вершины. Из симметрии множества вершин куба относительно замены знака всех координат вершины, получим
n n n

P (|
i=1

ai xi |

1) = 1 - 2P (
i=1

ai xi > 1).
n i=1

Отсечение не более чем 2

n-2

вершин n-мерного куба равносильно 2P (

ai xi > 1)

1 2

Следствие 1(утверждения 1). Пусть ai , где i = 1, . . . , n независимые случайные величины с n распределением P (ai = 1) = P (ai = -1) = 1 , где i = 1, 2, . . . , n. Тогда условие P (| i=1 ai xi | 1) 2 1 2 для любого вектора x такого, что x = 1, эквивалентно утверждению, что любая касательная гиперплоскость к вписанной сфере отсекает не более чем 2n-2 вершин n-мерного куба.
а) Любая касательная гиперплоскость к вписанной в 6-мерный куб сфере отсекает не более 16 его вершин. 1 1 1 б) Гиперплоскость x1 + x2 + ћ ћ ћ + xn = n, касающаяся сферы в точке ( n , n , . . . , n ), отсекает не более, чем 2n-2 вершин куба. санной в куб единичной сферы в точке (

Следствие 2(теорем 1,2).

Утверждение 2(Дильман Глеб). Гиперплоскость x1 + x2 + ћ ћ ћ + xn = n, касающаяся впи1 1 , n n



,...,

1 n

), отсекает ровно

i<

n- n 2

i Cn вершин куба.

Пусть координаты отсекаемой вершины куба состоят из k единиц и n - k минус единиц, тогда n k - (n - k ) > n, то есть n - k < n-2 n . Осталось заметить, что существует Cn -k вершин куба с ровно n - k отрицательными координатами. Таким образом, гипотеза и теоремы 1 и 2 имеют геометрическую интерпретацию. 1) А.Н. Ширяев ?Вероятность? 2) Журавлев Ю.И. ?Об отделимости подмножеств вершин n-мерного куба.? Труды МИАН СССР (51) М.1958 с 143-157 3) A. Ben-Tal, A. Nemirovski, C. Ros, 11.06.2001. ??

Литература.

5