Ошибка в книге или мой глюк

[thought]

Читаю книгу А.В.Черемушкина "Криптографические протоколы. Основные свойства и уязвимости". Там имеется такое неравенство: для любых натуральных чисел m и n и любого набора точек $x_1$,...,$x_n$ из отрезка [0,1] с условием, что $x_1+...+x_n=1$, выполнено

$$ \sum_{i=1}^nx_i(1-x_i)^m \leq \left(1 - \frac{1}{n}\right)^m $$

При этом при его доказательстве используется неравенство Йенсена для выпуклых функций и утверждение, что функция $(1-x)^m$ для любого натурального m на отрезке [0,1] является выпуклой вверх (стр.57 книги), но, очевидно, что данная функция на этом отрезке выпукла вниз. Поэтому доказательство неравенства падает.

Так вот вопрос: как правильно доказать данное неравенство. Докажу сам, только направление не вижу пока.

[svv]

Когда вторая производная отрицательна, функция выпукла вверх (например, Ваша функция, или же $y=-x^2$).
Когда вторая производная положительна, функция выпукла вниз (например, $y=x^2$).
Это если не рассматривать тонкости.
В Вашем случае выполняется неравенство
$f(tx+(1-t)y)\geqslant t f(x)+(1-t)f(y)$
Проверьте, такое ли (или эквивалентное) используется в книге, и если да, то все в порядке: для Вашей функции оно справедливо.

[Shtorm]

svv в сообщении #595256 писал(а):

Когда вторая производная отрицательна, функция выпукла вверх (это Ваш случай).

Разве? Берём вторую производную от $(1-x)^m$ и получаем всегда знак плюс на интервале от 0 до 1.

[svv]

WolframAlpha, plot (1-x)^0.5 from 0 to 1

[Shtorm]

svv, но там же в первом сообщении автора указано, что n и m - натуральные

[svv]

Да, прошу прощения, виноват. Я подумал, что это $m\in(0,1)$ (за компанию с иксом).

[thought]

svv в сообщении #595256 писал(а):

В Вашем случае выполняется неравенство
$f(tx+(1-t)y)\geqslant t f(x)+(1-t)f(y)$
Проверьте, такое ли (или эквивалентное) используется в книге, и если да, то все в порядке: для Вашей функции оно справедливо.

Это все очень просто и просто так я бы не обратился. В книге для функции $(1-x)^m$ на отрезке [0,1] использовано неравенство
$f(tx+(1-t)y)\geqslant t f(x)+(1-t)f(y)$, но функция то выпукла вниз, поэтому для нее верно такое неравенство:
$f(tx+(1-t)y)\leq t f(x)+(1-t)f(y)$, вернее, его обобщение, но суть та же. Так как все знают критерий:
функция f выпукла вниз на (a,b) тогда и только тогда, когда для любых $x_1,...,x_n \in (a,b)$, $t_1,...,t_n \in [0,1]$, $t_1+...+t_n=1,$ верно неравенство:

$$ f(t_1x_1+...+t_nx_n) \leq t_1f(x_1)+...+t_nf(x_n) $$

[svv]

Мда, книги об уязвимостях криптографических протоколов имеют свои уязвимости.

[thought]

svv в сообщении #595264 писал(а):

Мда, книги об уязвимостях криптографических протоколов имеют свои уязвимости.

В том то и дело, формулируются серьезные вещи на ошибочных постулатах.

-- 14.07.2012, 19:09 --

svv в сообщении #595256 писал(а):

В Вашем случае выполняется неравенство
$f(tx+(1-t)y)\geqslant t f(x)+(1-t)f(y)$

В Вашем случае как раз знак надо поменять, если речь о выпуклой вниз функции

[svv]

Я вначале подумал почему-то, что $m$ лежит в интервале $(0,1)$ и исходя из этого были все мои рассуждения. Невнимательно прочитал условие.

[thought]

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

[mserg]

А выполнится ли неравенство при $n=3, m=9, x_1=0.1,x_2=0.1,x_3=0.8$?

То ли у меня калькулятор сломался, то ли в неравенстве под суммой скобок не хватает …

[thought]

mserg, при Ваших значениях левая часть неравенства равна 0.08610, правая 0.03902. Если оставить такие же значения, но изменить m, то при m=6 получаем 0.10634 и 0.08779 соответственно, то есть начиная с этого номера при остальных фиксированных значениях неравенство неверно, а значит в книге часть теории рухнуло. Спасибо Вам за помощь. Замечу, что то неравенство при m=1 точно всегда верно, а в общем случае значит нет.

mserg в сообщении #595316 писал(а):

то ли в неравенстве под суммой скобок не хватает …

$x_i$ и $(1-x_i)^m$ стоят под знаком суммы.

-- 15.07.2012, 09:47 --

В книге Черемушкина это неравенство служило для доказательства следующего важного неравенства, которое может еще можно спасти.

Обозначим через$\mathcal{A}_n^k$ множество всех размещений без повторений из $n$ элементов по $k$ множества $\{1,...,n\}$.
Пусть $x_1,...,x_n$ - произвольный набор действительных чисел из отрезка $[0,1]$ с условием, что $x_1+...+x_n=1$. Тогда для любого фиксированного k, $2 \leq k \leq n,$ будет выполнено такое неравенство:

$$ \sum_{(i_1,...,i_k) \in \mathcal{A}_n^k} x_{i_1}...x_{i_k} \leq \prod_{i=1}^{k-1}\left(1 -\frac{i}{n} \right). $$

[thought]

Кстати, неравенство из первого поста можно рассматривать только для случая m < n, если оно верно, то все в порядке будет.

[thought]

А если задачу сформулирую на другом языке, может кому удастся решить или найти направление.

Пусть $A_1$,...,$A_n$ - полная группа событий с соответствующими вероятностями $p_1$,...,$p_n$. В каждом независимом испытании может произойти одно и только одно из представленных событий. Проводится $m$ независимых испытаний, $m \leq n$. Пусть $B(m)$ - событие, заключающееся в том, что в $m$ независимых испытаниях ни одно из событий $A_1$,...,$A_n$ не произойдет более одного раза. Доказать, что вероятность события $B(m)$ сверху ограничена числом

$$ \prod_{i=1}^{m-1} \left( 1 - \frac{i}{n} \right) $$