Поиск сжатой простой формы для громоздкого выражения

[seryrzu]

Доброго времени суток.

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

Фиксируем $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$ (в такой форме, как написано в этом посте) даже в одной точке невозможно за разумное время.

[Vince Diesel]

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

[seryrzu]

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

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

-- 21.02.2015, 18:56 --

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

[Vince Diesel]

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). $$

Вот для перестановок хуже. Но для начала можно попробовать хотя бы для равномерного распределения прикинуть асимптотику.

[mserg]

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

[seryrzu]

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). $$

Вот для перестановок хуже. Но для начала можно попробовать хотя бы для равномерного распределения прикинуть асимптотику.

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