Помогите оценить хотя бы порядок значения 1-(1-0,5^x)^y

[DobriyDruid]

Здравствуйте.
Пытаюсь оценить сверху порядок значения

$$1 - \Biggl(1-\left(\frac{1}{2}\right)^{2^\rho}\Biggr)^{2^\mu}$$

(порядок log_2, т.к. значение в лоб в Mapple/Wolfram не считается) - получилось оценить ну оочень грубо ($<2^{ - {2^{\rho}} + \mu$ ), подскажите пожалуйста, наверно можно лучше?

т.е.
$$1 - {(1 - {2^h})^M}$
где $h = - ({2^\rho }),\,M = {2^\mu }$
$\rho \in [9..16];\,\mu \in [150..500]$

Зачем нужно:
Подобрать такие значения $\rho$, чтобы для заданного $\mu$ вероятность $\Pr \left( \exists \right)$ была "пренебрежимо мала"
Т.е. например для $\mu = 256$ при $\rho = 10?$ имеем, что $log_2(\Pr \left( \exists \right)) < -100$

Что получилось:
Как получилась сама формула (и оценка для нее):
Учитывая, что вероятность отсутствия ..

$$Pr(-) = {\left( {\frac{1}{2}} \right)^{{2^\rho }}} $$

получаем

$$\Pr \left( \exists \right) = \sum\limits_{i = 1}^{\rm M} {C_{\rm M}^i{{\left( {\Pr ( - )} \right)}^i}{{\left( {1 - \Pr ( - )} \right)}^{{\rm M} - i}}}$$

где $M=2^\mu$. Зададим выбор $\mu$ и $\rho$ таким, чтобы выполнялось условие $MPr ( - ) < 2^{-\mu}$ при некотором значении $u \geq 32$. Поскольку $\forall i$ имеет место ${\left( {1 - \Pr ( - )} \right)^{{\rm M} - i}} < 1$ и $C_{\rm M}^i < {{\rm M}^i}$, с учётом формулы для суммы членной бесконечной убывающей геометрической прогрессии можно записать

$$\Pr \left( \exists \right) < \sum\limits_{i = 1}^{\rm M} {{{\left( {{\rm M}\Pr ( - )} \right)}^i}} \approx \frac{{{\rm M}\Pr ( - )}}{{1 - {\rm M}\Pr ( - )}} \approx {\rm M}\Pr ( - ) \leqslant {2^{ - {2^{\rho}} + \mu }}$$

C дргой стороны

$$\Pr \left( \exists \right) = \sum\limits_{i = 1}^{\rm M} {C_{\rm M}^i{{\left( {\Pr ( - )} \right)}^i}{{\left( {1 - \Pr ( - )} \right)}^{{\rm M} - i}}} = 1 - \sum\limits_{i = 0}^{\rm 0} {C_{\rm M}^i{{\left( {\Pr ( - )} \right)}^i}{{\left( {1 - \Pr ( - )} \right)}^{{\rm M} - i}}} = 1 - (1-Pr(-))^M$$

но непонятно как это посчитать (хотя бы Log2)
$\rho \in [9..16];\,\mu \in [150..500]$

Предположение:
По сути - обычная задача на вероятность - что при M бросках орел выпадет хотя бы 1 раз (1 - "все решки")
Беда в том что числа очень большие, в лоб не считаются. Может есть формулы какой апроксимации/оценки с точностью до порядка?

Т.е. - вероятность что выпадет "орел" -

$$Pr(-) = {\left( {\frac{1}{2}} \right)^{{2^\rho }}} $$

Всего кидают монетку $M = {2^\mu }$
где
$\rho \in [9..16];\,\mu \in [150..500]$

Подобрать достаточное значение $\rho$ для заданного $\mu$ чтобы вероятность, что орел выпадет хотя бы 1 раз (1 - "все M раз будут решки") была меньше заданной ( например $\log2 <-100$)

[alcoholist]

Исходное выражение растущая функция $\mu$ и убывающая функция $\rho$, поэтому его можно оценить сверху и снизу числами
А что именно нужно?

-- Вс янв 31, 2016 21:19:12 --

вообще-то выражение явно близко к 1

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

Дубль темы «Вероятнось - все время выпадет решка. Но числа очень большие»

Делаем одну.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[DobriyDruid]

alcoholist в сообщении #1095629 писал(а):

...
вообще-то выражение явно близко к 1

Я тоже думал что уйдет в 1, но при достаточном $\rho$ получаю нужную мне "малость", т.е. например в статье давал таблицу (там "-1" еще в формулах, но не суть)

Только в таблице грубая оценка "с верху", наверно ее можно улучшить, но моих мат. познаний на это не хватает

[alcoholist]

DobriyDruid
Сформулируйте задачу четко, пожалуйста... А то я путаюсь в обозначениях

[Otta]

Я тоже. Что такое $2^p$ и $2^\mu$ и кто на ком стоял что происходит?

По порядку: симметричная монета подбрасывается.... раз. Дальше?

[gris]

Монета не симметричная. Вероятность выпадения орла крайне мала $ (0.5^{2^\rho})$, но монета подбрасывается чудовищное количество раз $(2^\mu)$.

[DobriyDruid]

gris в сообщении #1095675 писал(а):

Монета не симметричная. Вероятность выпадения орла крайне мала $ (0.5^{2^\rho})$, но монета подбрасывается чудовищное количество раз $(2^\mu)$.

Совершенно верно!

На вероятность "выпадения орла" я могу влиять (меняя $ \rho$).
Нужно подобрать оптимальное $ \rho$, так, чтобы при чудовищном кол-ве раз ($(2^\mu)$, \mu = 128...512) этот орел у меня если и выпал (хотя бы раз), то с пренебрежимо малой вероятностью = т.е. оценить сверху значение (1-"вероятность, что все решки").

Эта штука была ооочень грубо оценена сверху через убыв. геом. прогрессию ("Что получилось:" в описании), ее значения в последним столбце таблицы из комментария
post1095658.html#p1095658
(в таблице еще вместо $ \rho$ еще $ \rho-1$, но ет другая песня, не обращайте внимания)

[gris]

Ситуация до крайности искусственная, но понятно, что при больших значениях параметров искомая вероятность может меняться от почти нуля до почти единицы при определённых изменениях этих параметров. Ваши параметры $(\rho,\mu)$ весьма неравноправны. Я бы предпочёл такую формулировку задачи:
Вероятность события в одном испытании равна $1/M$. Производится $N$ испытаний. Вероятность того, что событие не произойдёт ни разу равна $(1-1/M)^N$. Поанализировать эту вероятность как функцию $M,N$.

Ясно, что при $N=M;N\to\infty$ вероятность устремится к $1/e$.

В Вашем варианте $M$ уж очень больше $N$. То есть вероятность будет очень близка к единице. А Ваша, соответственно, к нулю.

То есть, как бы если $M=kN$, то вероятноcть $\approx e^{-1/k}\approx 1-1/k$. При $k=1000000$ это будет $0.999999$. А у Вас $k$ получается примерно десять в тысячной степени?

А, пардон, Вы и пытаетесь её ограничить сверху числами настолько малыми, что их даже написать нельзя
Я вот в этом увидел искусственность. Но в определённых задачах, вероятно, такие числа бывают. Просто обывателю (мне) трудно представить себе вероятность с тысячами нулями после запятой).
Мне кажется, что второй замечательный предел и приближение экспоненты около нуля тут может пригодиться (а у Вас, случайно, не то же самое?), и что $\rho$ уж слишком велико.

[DobriyDruid]

gris в сообщении #1095681 писал(а):

Ситуация до крайности искусственная...

Не совсем, просто не описывал применение, дабы не путать.

Оценка необходима для оптимизации пропускной способности(уменьшения избыточности) через выбор правильного параметра в алгоритме вероятностного кодирования элемента поля,над которым задана ЭК - точкой этой ЭК. Соотв. $\mu$ - размер (бит) элемента поля, над которым задается ЭК, $\rho$ - сколько бит мы тратим на то, чтоб не было случая, когда не сможем закодировать какой-либо элемент этого поля точкой ЭК.
*Если совсем интересно, то http://i-vimi.ru/editions/for_readers/a ... T_ID=10958

[AlexValk]

В вашей задаче справедливы неравенства:

$$P_< = 1-\exp\left(-2^{\mu-2^\rho}\right)<Pr(\exists)<1-\exp\left(-2^{\mu}\frac{2^{-2^\rho}}{1-2^{-2^\rho}}\right)= P_>.$$

Ширина интервала характеризуется неравенством $P_>-P_< < \exp\left(-2^{\mu-2^\rho}\right) 2^{-2^\rho}< 2^{-2^\rho}$. В вашем случае, $\rho\geqslant 9$, это дает $2^{-2^\rho}< 10^{-150}$.

Поэтому результат для $Pr(\exists)$ в области $\rho\geqslant 9$ с относительной точностью лучше $10^{-150}$ ( ) дается формулой $Pr(\exists)\approx1-\exp\left(-2^{\mu-2^\rho}\right)$.

Выводы:
а) Если $\mu> 2^\rho$ хотя бы на несколько единиц (чего в вашей Таблице 1 я не увидел), то $Pr(\exists)$ с огромной точностью равно 1 (например, для $\rho=9$ и $\mu=517$ имеем $Pr(\exists)\approx 1-1,2\times10^{-14}).
б) Если $\mu< 2^\rho$ хотя бы на пару десятков (это в ваше Таблице 1 выполнено, и всегда с большим запасом), то $Pr(\exists)$ с большой точностью (а в вашей Таблице 1 - с колоссальной точностью) равно 0 (например при $\rho=9$ и $\mu=490$ имеем $Pr(\exists)\approx 2,4\times 10^{-7}$, а для $\mu=400$ получим уже $Pr(\exists)\approx 1,9\times 10^{-34}$). Здесь вероятность приближенно может быть найдена по формуле $Pr(\exists)\approx 2^{\mu-2^\rho}$.
в) Исключение - случай когда $\mu\approx 2^\rho$ (например, при $\mu=510$, $\rho=9$ будет $Pr(\exists)\approx 0,22$, а при $\mu=513$ получим $Pr(\exists)\approx 0,86$.

Так, что задача выглядит странноватой, по крайней мере при ваших данных $\mu$ и $\rho$. Осмысленной представляется ситуация в).

Для получения приведенных выше оценок можно использовать формулы $1-\varepsilon=e^{\ln(1-\varepsilon)}$ и $\ln(1-\varepsilon)=-(\varepsilon+\frac12\varepsilon^2+\frac13\varepsilon^3+\dots)$ вместе с неравенствами $\varepsilon < \varepsilon+\frac12\varepsilon^2+\frac13\varepsilon^3+\dots < \varepsilon+\varepsilon^2+\varepsilon^3+\dots=\varepsilon/(1-\varepsilon)$.
И наконец, последнее - численно тестировать приведенные формулы можно на том же Maple, который Вы упоминали вначале, но используя более скромные числа $\mu$ и $\rho$ (а также требуя от Maple при численных расчетах использовать больше значащих цифр, например командой типа evalf$(f, 100)$).

[gris]

С утра немного прояснилось в голове Ну да, экспонента работает, что даёт уже считаемую формулу. Приближение экспоненты линейной функцией в Ваших диапазонах также прекрасно работает и даёт, как мне кажется, те же результаты, что у Вас в немного запутанной таблице. Я лишь имел в виду, что на бытовой взгляд анализировать вероятности порядка $10^{-1000}$ совершенно не имеет смысла. То есть нижнее значение $\rho$ уже даёт решение проблемы. Хотя при дискретности этого параметра меньшие значения уже дадут почти противоположный результат. Ну тут не буду уж касаться вопросов, в которых не разбираюсь. Вдруг в Вашей области действуют именно такие вероятности. Именно это я и считал "искусственностью", а не саму задачу, надеюсь Вы не обиделись.
Впрочем, оставляю за собой возможность тотального ошибания и надеюсь, что в теме выскажутся специалисты.
Хотя, надо сказать, "бросание монетки" могло создать иллюзию несерьёзности.

+ А вот и высказались, но я своё сообщение оставляю.

[AlexValk]

Некоторые замечания к моему предыдущему посту:
За счет неравенства $\varepsilon+\frac12\varepsilon^2+\frac13\varepsilon^3+\dots < \varepsilon+\frac12(\varepsilon^2+\varepsilon^3+\dots)=\varepsilon+\frac12\frac{\varepsilon^2}{1-\varepsilon}$ можно усилить оценку сверху:

$$P_> =1-\exp\left(-2^{\mu-2^\rho}-\frac{2^{\mu-1-2^{\rho+1}}}{1-2^{-2^\rho}}\right).$$

Аналогично за счет неравенства $\varepsilon+\frac12\varepsilon^2<\varepsilon+\frac12\varepsilon^2+\frac13\varepsilon^3+\dots $ получаем улучшенную оценка снизу:

$$P_< =1-\exp\left(-2^{\mu-2^\rho}-2^{\mu-1-2^{\rho+1}}\right).$$

Естественно, все это имеет практическое значение только в случае в): $\mu\approx 2^\rho$.


Была ошибка в формуле для ширины интервала. Правильная оценка должна была быть $P_>- P_< < \exp\left(-2^{\mu-2^\rho}\right) \frac{2^{\mu-2^{\rho+1}}}{1-2^{-2^\rho}}< \frac{2^{\mu-2^{\rho+1}}}{1-2^{-2^\rho}}$. Здесь использовалось неравенство $1-\exp(-\varepsilon)<\varepsilon$, $\varepsilon>0$. Теперь (с улучшенными формулами для $P_>$, $P_<$) получаем $P_>- P_< < \exp\left(-2^{\mu-2^\rho}-2^{\mu-1-2^{\rho+1}}\right) \frac{2^{\mu-3\cdot2^{\rho}}}{3(1-2^{-2^\rho})}< \frac{2^{\mu-3\cdot2^{\rho}}}{3(1-2^{-2^\rho})}$. В случае $\rho\geqslant 9$, $\mu\leqslant 500$ это дает $P_>- P_< < 10^{-310}$.

[DeBill]

А чё, по Пуассону вероятности не считаюся разве? И ошибку Пуассон тоже дает (не превышает $np^2$. У Вас $n=2^{\mu}, p=2^{-2^{\rho}}$).