2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Ошибка в книге или мой глюк
Сообщение14.07.2012, 11:54 


14/07/12
23
Читаю книгу А.В.Черемушкина "Криптографические протоколы. Основные свойства и уязвимости". Там имеется такое неравенство: для любых натуральных чисел 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 книги), но, очевидно, что данная функция на этом отрезке выпукла вниз. Поэтому доказательство неравенства падает.

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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 18:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 18:51 
Аватара пользователя


14/02/10
4956
svv в сообщении #595256 писал(а):
Когда вторая производная отрицательна, функция выпукла вверх (это Ваш случай).


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 18:54 
Заслуженный участник


23/07/08
10626
Crna Gora
WolframAlpha, plot (1-x)^0.5 from 0 to 1

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 18:57 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:01 


14/07/12
23
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)
$$

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:06 
Заслуженный участник


23/07/08
10626
Crna Gora
Мда, книги об уязвимостях криптографических протоколов имеют свои уязвимости. :D

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:08 


14/07/12
23
svv в сообщении #595264 писал(а):
Мда, книги об уязвимостях криптографических протоколов имеют свои уязвимости. :D


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

-- 14.07.2012, 19:09 --

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

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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:22 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 19:39 


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение14.07.2012, 22:14 


17/10/08

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

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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение15.07.2012, 08:59 


14/07/12
23
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).
$$

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение15.07.2012, 10:49 


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

 Профиль  
                  
 
 Re: Ошибка в книге или мой глюк
Сообщение15.07.2012, 14:42 


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

Пусть $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)
$$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group