2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Поиск сжатой простой формы для громоздкого выражения
Сообщение21.02.2015, 18:04 


09/08/12
15
Доброго времени суток.

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

Фиксируем $S \in \mathbb N$. Рассмотрим симметрическую группу (группу перестановок) порядка $S$: $\mathfrak S_S$.
Фиксируем набор $\{p_i\}_{i=1}^S$,обладающий свойствами: $p_i \geqslant 0$ для любого $i \in 1:S$ и$\sum_{i=1}^S p_i = 1$.
Для любой перестановки $\mathbf i = (i_1,\ldots,i_S) \in \mathfrak S_S$ определим
$$
	\pi_{\mathbf i} = \pi_{i_1,i_2,\ldots, i_S} =
	\frac{p_{i_1} \ldots p_{i_{S-1}}}{(1 - p_{i_1})( 1 - p_{i_1} - p_{i_2} ) 
	\ldots ( 1 - p_{i_1} - p_{i_2} - \ldots - p_{i_{S-2}})}
	=\frac{\prod\limits_{k=1}^{S-1}p_{i_k}}{\prod\limits_{k=1}^{S-2}
	\left(1-\sum\limits_{j=1}^k p_{i_j}\right)}\ .
$$
Теперь же рассмотрим функцию $f : \{1,2,\ldots,S\} \mapsto [0;1]$, определяемую для любого $j \in 1:S$ следующим образом
$$
	f(j) = \sum\limits_{k=1}^S p_k 
	\sum\limits_{\substack{\mathbf i \in \mathfrak S_S \\ \mathbf i_j = k}} \pi_{\mathbf i}.
$$
Хочется получить удобную для вычислений форму $f(j)$, так как непосредственно по определению при больших $S$ считать затруднительно, так как происходит суммирование по $S!$ слагаемым.

На самом деле это связано с генераторами псевдослучайных чисел, и, в частности, $S$ --- количество разных чисел, которые может генерировать генератор. То есть на практике $S \geqslant 2^{30}$, а при таких значениях $S$ вычислить $f$ (в такой форме, как написано в этом посте) даже в одной точке невозможно за разумное время.

 Профиль  
                  
 
 Re: Поиск сжатой простой формы для громоздкого выражения
Сообщение21.02.2015, 18:41 
Заслуженный участник


25/02/11
1529
При таких значениях не стоит ли уже искать какое-нибудь предельное распределение или типа того? Да и когда этих вероятностей порядка $10^{10}$, больно много вариантов. Мб что-то можно получить сделав дополнительные предположения, задав так-сказать макро-распределение. Например, $p_i=h(i/S)$, где $h\ge0$ — гладкая функция на $[0,1]$, $\int_0^1h(x)\,dx=1$. А в ответе предположительно должна получиться функция $f:[0,1]\to[0,1]$. Или такая постановка не имеет смысла?

 Профиль  
                  
 
 Re: Поиск сжатой простой формы для громоздкого выражения
Сообщение21.02.2015, 18:53 


09/08/12
15
Искать предельное распределение (по $S$) наверняка разумно, но вопрос в том, как от набора $\{p_i\}_{i=1}^S$ перейти к $\{p_i\}_{i=1}^{S+1}$ разумным способом?

В теории это просто набор вероятностей, так что они могут быть любыми. На практике -- они довольно близки к $1/S$, если мы рассматриваем хороший генератор.

-- 21.02.2015, 18:56 --

Чисто интуитивно при взгляде на выражение $\pi_\mathbf i$ видно, что в нем есть какие-то симметрии. Так что, может быть, вопрос поиска удобной формы -- это алгебраический вопрос.

 Профиль  
                  
 
 Re: Поиск сжатой простой формы для громоздкого выражения
Сообщение21.02.2015, 19:53 
Заслуженный участник


25/02/11
1529
seryrzu в сообщении #980919 писал(а):
Искать предельное распределение (по $S$) наверняка разумно, но вопрос в том, как от набора $\{p_i\}_{i=1}^S$ перейти к $\{p_i\}_{i=1}^{S+1}$ разумным способом?

Не надо переходить. На входе функция $h$, на выходе $f$. Скажем
$$
\prod\limits_{k=1}^{S-1}p_{i_k}=\exp{\sum_{k=1}^{S-1}\ln p_{i_k}}
\approx p_{i_S}^{-1}\exp\left({S\int_0^1\ln h(x)\,dx}\right).
$$
Вот для перестановок хуже. Но для начала можно попробовать хотя бы для равномерного распределения прикинуть асимптотику.

 Профиль  
                  
 
 Re: Поиск сжатой простой формы для громоздкого выражения
Сообщение21.02.2015, 20:54 


17/10/08
1026
А есть посчитанные данные, которые можно было бы изучить?

 Профиль  
                  
 
 Re: Поиск сжатой простой формы для громоздкого выражения
Сообщение22.02.2015, 00:57 


09/08/12
15
mserg в сообщении #980970 писал(а):
А есть посчитанные данные, которые можно было бы изучить?


Здесь таблица из моей работы.
В первом столбце разные $S$.
Заданы конкретные $p_i$, как написано во втором столбце.
В третьем столбце $f(k)$, посчитанные по формуле из первого поста.

\begin{table}[h]
\begin{center}
\small{
  \begin{tabular}{| c | c | c |c|}
    \hline
S& $p_1,\ldots,p_S$&Вероятности $f(k)$\\
\hline
4&$p_1=1/2$ $p_i=1/6$&$(.3333,.2667,.2167,.1833)$ \\
\hline
5&$p_1={2}/{5}$, $p_i={3}/{20}$&$(.25,.2209,.1954,.1748,.1593)$\\
\hline
6&$p_1={1}/{3}$, $p_i={2}/{15}$&$(.2,.1846,.1706,.1582,.1475,.1390)$\\
\hline
   \end{tabular}
    \caption{Сравнение теоретических вероятностей с экспериментальными. При $i>1$ все $p_i$ взяты одинаковыми.}
    \label{tab:results}
    }
\end{center}
\end{table}

Понятно, что тут $S$ маленькие совсем.

На самом деле доказано, что, если исходные $\{p_i\}_{i=1}^S$ не равны все по $1/S$, то новые $\{f(k)\}_{k=1}^S$ будут в нескольких смыслах ближе к равномерному распределению (то есть к $1/S$). Так что описано некоторое <<сглаживающее>> преобразование.

-- 22.02.2015, 01:40 --

Vince Diesel в сообщении #980941 писал(а):
seryrzu в сообщении #980919 писал(а):
Искать предельное распределение (по $S$) наверняка разумно, но вопрос в том, как от набора $\{p_i\}_{i=1}^S$ перейти к $\{p_i\}_{i=1}^{S+1}$ разумным способом?

Не надо переходить. На входе функция $h$, на выходе $f$. Скажем
$$
\prod\limits_{k=1}^{S-1}p_{i_k}=\exp{\sum_{k=1}^{S-1}\ln p_{i_k}}
\approx p_{i_S}^{-1}\exp\left({S\int_0^1\ln h(x)\,dx}\right).
$$
Вот для перестановок хуже. Но для начала можно попробовать хотя бы для равномерного распределения прикинуть асимптотику.



Возможно это, действительно, путь. Я только не понимаю, что будет выступать в качестве непрерывного <<аналога>> симметрической группы. И еще оценка суммарной погрешности будет наверное крайне затруднительная для вычисления... Хотя идея интересная, я подумаю над этим.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

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


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

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