Вероятность покраски чисел

[Вячеслав]

Форумчане подскажите способ решения пож.

Зафиксируем целое число k>1 и будем красить натуральные числа в два цвета. Изначально все числа не покрашены. Возьмем k наименьших не покрашенных, выберем одно из них равновероятно. Это число покрасим в синий цвет, а все непокрашенные числа, меньшие его — красный. Будем повторять это бесконечно много раз. У какого числа вероятность быть покрашенным в синий цвет наибольшая?

[Kreativshik]

Форумчане подскажите способ решения пож.

Интересная задача.
Здесь процесс окраски генерирует возрастающую последовательность синих чисел [tex]B_{1}, B_{ 2}, B_{3},…[/tex]
Генерация происходит следующим образом:
[tex]B_{1}=V_{1} \sim U \{1, …, k\}[/tex]
[tex]B_{i+1}=B_{i}+V_{I+1}[/tex] , все [tex]V_{ i}[/tex] независимые.
Обозначим через [tex]p(n)[/tex] , вероятность того, что n является синим. Число [tex]n[/tex] будет синим, если оно является одним из членов последовательности [tex]B_{1}, B_{ 2}, B_{3},…[/tex]
Так как эти события несовместны, вероятность есть сумма вероятностей того, что [tex]n[/tex] является первым, вторым, третьим, ... синим числом
[tex]p(n)=P(B_{1}=n)+P(B_{2}=n)+P(B_{3}=n)+…[/tex]
Очевидно , что [tex]P(B_{i}=n)=0[/tex], при[tex]i>n[/tex] т.к. [tex]B_{i}≥i[/tex]. Значит сумма конечна:
[tex]p(n)= \sum_{i=1}^{n }P(B_{i}=n)[/tex]
Т. к. [tex]B_{i}=V_{1}+V_{2}+V_{3}+…+V_{i}[/tex] то вероятность [tex]P(B_{i}=n)[/tex] - это вероятность того, что сумма
[tex]i[/tex] независимых таких ([tex]V[/tex])величин равна [tex]n[/tex]. Эта вероятность равна количеству способов представить число [tex]n[/tex] в виде суммы [tex]i[/tex]натуральных слагаемых, каждое из которых не больше [tex]k[/tex], деленному на общее число исходов [tex]k^{i}[/tex] .
Обозначим число таких способов (композиций), как [tex]N(i, n)[/tex]. Тогда:
[tex]P (B_{i}=n)= \frac{N(i,n)}{k^{i}}[/tex]
Следовательно, итоговая формула:
[tex]p(n)= \sum_{i=1}^{n } \frac{N(i,n)}{k^{i}}[/tex]
Далее анализируем итоговую формулу и показываем, что максимум находится в точке [tex]n=k[/tex]
Следовательно, вероятность быть окрашенным в синий цвет максимальна для числа [tex]n=k[/tex]
Пример для k=5:

n | p(n)
---------------
1 | 0.2
2 | 0.24
3 | 0.288
4 | 0.3456
5 | 0.41472
6 | 0.297664
7 | 0.317197
8 | 0.332636
9 | 0.341563
10 | 0.340756

Максимальная вероятность: p(5) = 0.41472

[ivashenko]

Будем повторять это бесконечно много раз.

А шо делать, если сразу выпадет $k$?

[ivashenko]

Т. к. [tex]B_{i}=V_{1}+V_{2}+V_{3}+…+V_{i}[/tex]

не пропустили здесь справа слагаемое $B_1$?

то вероятность [tex]P(B_{i}=n)[/tex] - это вероятность того, что сумма
[tex]i[/tex] независимых таких ([tex]V[/tex])величин равна [tex]n[/tex]. Эта вероятность равна количеству способов представить число [tex]n[/tex] в виде суммы [tex]i[/tex]натуральных слагаемых, каждое из которых не больше [tex]k[/tex], деленному на общее число исходов [tex]k^{i}[/tex] .
Обозначим число таких способов (композиций), как [tex]N(i, n)[/tex]. Тогда:
[tex]P (B_{i}=n)= \frac{N(i,n)}{k^{i}}[/tex]
Следовательно, итоговая формула:
[tex]p(n)= \sum_{i=1}^{n } \frac{N(i,n)}{k^{i}}[/tex]
Далее анализируем итоговую формулу и показываем, что максимум находится в точке [tex]n=k[/tex]
Следовательно, вероятность быть окрашенным в синий цвет максимальна для числа [tex]n=k[/tex]
Пример для k=5:

n | p(n)
---------------
1 | 0.2
2 | 0.24
3 | 0.288
4 | 0.3456
5 | 0.41472
6 | 0.297664
7 | 0.317197
8 | 0.332636
9 | 0.341563
10 | 0.340756

Максимальная вероятность: p(5) = 0.41472

А мне почему-то казалось, что эта вероятность равна 1. Поскольку количество испытаний по условию может быть бесконечным. И рано или поздно выпадет k. Это же понятно и без столь мудреных расчетов. Вероятность не выпасть $k$ за сколь угодно большое число испытаний равна 0, значит вероятность выпасть $k$ равна 1. Если выпадает не $k$, то испытание продолжается пока не выпадет $k$. Или я неправильно понимаю условие задачи?

[Kreativshik]

А мне почему-то казалось, что эта вероятность равна 1. Поскольку количество испытаний по условию может быть бесконечным. И рано или поздно выпадет k. Это же понятно и без столь мудреных расчетов.

Разберитесь в условии для начала, чтобы вам ничего не казалось.

[ivashenko]

А мне почему-то казалось, что эта вероятность равна 1. Поскольку количество испытаний по условию может быть бесконечным. И рано или поздно выпадет k. Это же понятно и без столь мудреных расчетов.

Разберитесь в условии для начала, чтобы вам ничего не казалось.

Так я разобрался. Просто в отличии от Вас допускаю, что могу ошибиться, а не утверждаю не разобираясь, что у меня "Изначально все правильно".

Здесь возможны 2 интерпретации:
1. Берем натуральное число $k$. Среди натуральных чисел меньших или равных $k$ выбираем равновероятным способом число, красим его в синий цвет, а числа меньшие его в красный. Далее, среди оставшихся неокрашенных чисел меньших или равных $k$ выбираем равновероятным образом числои все числа меньшие его красим в красный цвет, а само выбранное число в синий. В этой интерпретации не всегда возможно бесконечное количество итераций, которое должно быть по условию. Но в итоге число k будет синим с вероятностью 1.
2. Берем натуральное число $k$. Среди натуральных чисел меньших или равных $k$ выбираем равновероятным способом число, красим его в синий цвет, а числа меньшие него в красный. Далее берем от синего числа k неокрашенных чисел и выбираем среди них любое неокрашенное число равновероятным способом, затем красим его в синий цвет, а все числа меньшие него в красный и т.д.

Какая Ваша интерпретация этой задачи? Я так понимаю второй.

[ivashenko]

Форумчане подскажите способ решения пож.

Интересная задача.
Здесь процесс окраски генерирует возрастающую последовательность синих чисел [tex]B_{1}, B_{ 2}, B_{3},…[/tex]
Генерация происходит следующим образом:
[tex]B_{1}=V_{1} \sim U \{1, …, k\}[/tex]
[tex]B_{i+1}=B_{i}+V_{I+1}[/tex] , все [tex]V_{ i}[/tex] независимые.
Обозначим через [tex]p(n)[/tex] , вероятность того, что n является синим. Число [tex]n[/tex] будет синим, если оно является одним из членов последовательности [tex]B_{1}, B_{ 2}, B_{3},…[/tex]
Так как эти события несовместны, вероятность есть сумма вероятностей того, что [tex]n[/tex] является первым, вторым, третьим, ... синим числом
[tex]p(n)=P(B_{1}=n)+P(B_{2}=n)+P(B_{3}=n)+…[/tex]
Очевидно , что [tex]P(B_{i}=n)=0[/tex], при[tex]i>n[/tex] т.к. [tex]B_{i}≥i[/tex]. Значит сумма конечна:
[tex]p(n)= \sum_{i=1}^{n }P(B_{i}=n)[/tex]
Т. к. [tex]B_{i}=V_{1}+V_{2}+V_{3}+…+V_{i}[/tex] то вероятность [tex]P(B_{i}=n)[/tex] - это вероятность того, что сумма
[tex]i[/tex] независимых таких ([tex]V[/tex])величин равна [tex]n[/tex]. Эта вероятность равна количеству способов представить число [tex]n[/tex] в виде суммы [tex]i[/tex]натуральных слагаемых, каждое из которых не больше [tex]k[/tex], деленному на общее число исходов [tex]k^{i}[/tex] .
Обозначим число таких способов (композиций), как [tex]N(i, n)[/tex]. Тогда:
[tex]P (B_{i}=n)= \frac{N(i,n)}{k^{i}}[/tex]
Следовательно, итоговая формула:
[tex]p(n)= \sum_{i=1}^{n } \frac{N(i,n)}{k^{i}}[/tex]
Далее анализируем итоговую формулу и показываем, что максимум находится в точке [tex]n=k[/tex]
Следовательно, вероятность быть окрашенным в синий цвет максимальна для числа [tex]n=k[/tex]
Пример для k=5:

n | p(n)
---------------
1 | 0.2
2 | 0.24
3 | 0.288
4 | 0.3456
5 | 0.41472
6 | 0.297664
7 | 0.317197
8 | 0.332636
9 | 0.341563
10 | 0.340756

Максимальная вероятность: p(5) = 0.41472

Вот есть число 4. Пусть k=2. 4 можно представить в виде:
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=3+1
4=1+3.
В последних 2-х способах слагаемое превышает k, значит подходят только первые 4 способа. i= 4/k=2. Тогда $4/2^i=1$
Возьмем число 5 и k=2
5 можно представить подходящими способами как:
5=1+1÷1÷1÷1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+2+2
5=2+1+2
5=2+2+1
Т.е. 8 подходящих способов, способы включающие слагаемые 3,4,5 не подходят.
i=5/2=2.5.
$8/2^i=8/2^{2.5)\aprox1.42$

Правомерно ли использовать объем гиперкуба $k^i$ в качестве количества всех возможных исходов?
И что Вы понимаете под "всеми возможными исходами"? Можно на примере композиций числа 5.

[Kreativshik]

Здесь возможны 2 интерпретации:

Абсолютно нет, т.к. автор русским по белому написал:

Возьмем k наименьших не покрашенных, выберем одно из них равновероятно. Это число покрасим в синий цвет, а все непокрашенные числа, меньшие его — красный. Будем повторять это

Двояко здесь понимать нечего.

[Kreativshik]

что Вы понимаете под "всеми возможными исходами"?

Все возможные исходы при рассмотрении [tex]B_i=n[/tex] - это все возможные последовательности
[tex](V_1, V_2, …, V_i)[/tex], где каждое [tex]V_i[/tex]— независимая случайная величина, равномерно распределенная на [tex]\{1,2,…, k \}[/tex]

[Kreativshik]

Правомерно ли использовать объем гиперкуба
в качестве количества всех возможных исходов?

Да, это абсолютно правомерно!

Каждая последовательность [tex](V_1, …, V_i)[/tex] равновероятна с вероятностью [tex]\frac{1}{k^i}[/tex]

Композиция [tex]N(i,n)[/tex]— это количество "благоприятных" последовательностей, дающих в сумме [tex]n[/tex]

По классическому определению вероятности:

[tex]P(B_i=n)=[/tex][tex]\frac{Число \ благоприятных \ исходов}{Общее \ число \ исходов}[/tex][tex]= \frac{N(i,n)}{k^i}[/tex]

Можно на примере композиций числа 5.

Для автора можно, для вас нет, т.к. не в коня корм.

[ivashenko]

Правомерно ли использовать объем гиперкуба
в качестве количества всех возможных исходов?

Да, это абсолютно правомерно!

Каждая последовательность [tex](V_1, …, V_i)[/tex] равновероятна с вероятностью [tex]\frac{1}{k^i}[/tex]

Композиция [tex]N(i,n)[/tex]— это количество "благоприятных" последовательностей, дающих в сумме [tex]n[/tex]

На примере числа 5 и k=2 нетрудно увидеть, что моуг быть подходящие композиции:
5=1+1÷1÷1÷1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+2+2
5=2+1+2
5=2+2+1, которые не имеют одной размерности i в Вашем гиперкубе. Вы делите объемы параллелипипедов разной размерности, лежащих в гиперкубе, в том числе и пересекающихся, на объем самого гиперкуба и получается абракадабра. Чтобы получилась вероятность необходимо делить непересекающиеся объемы параллелепипедов, принадлежажих гиперкубу и имеющих с ним одну размерность на объем гиперкуба. А этого у Вас к сожалению нет.

[ivashenko]

Т. к. [tex]B_{i}=V_{1}+V_{2}+V_{3}+…+V_{i}[/tex] то вероятность [tex]P(B_{i}=n)[/tex] - это вероятность того, что сумма
[tex]i[/tex] независимых таких ([tex]V[/tex])величин равна [tex]n[/tex]. Эта вероятность равна количеству способов представить число [tex]n[/tex] в виде суммы [tex]i[/tex]натуральных слагаемых, каждое из которых не больше [tex]k[/tex], деленному на общее число исходов [tex]k^{i}[/tex] .
Обозначим число таких способов (композиций), как [tex]N(i, n)[/tex]. Тогда:
[tex]P (B_{i}=n)= \frac{N(i,n)}{k^{i}}[/tex]
Следовательно, итоговая формула:
[tex]p(n)= \sum_{i=1}^{n } \frac{N(i,n)}{k^{i}}[/tex]
Далее анализируем итоговую формулу и показываем, что максимум находится в точке [tex]n=k[/tex]
Следовательно, вероятность быть окрашенным в синий цвет максимальна для числа [tex]n=k[/tex]

еще раз, композиции числа в которых слагаемые не превышают k=2:
5=1+1+1+1+1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+2+2
5=2+1+2
5=2+2+1
По Вашим формулам: i=5 и существует 1 способ представить число 5 пятью слагаемыми не превышающими k=2. Значит $P(B_{5}=5)=\frac{1}{2^5}=\frac{1}{32}$. Здесь $2^5$- пятимерный куб со стороной k=2.
Далее, для композиций числа 5 из i=4 слагаемых существует 4 композиции. Значит $P(B_{4}=5)=\frac{4}{2^4}=\frac{1}{4}$, здесь $2^4$ объем четырехмерного куба со стороной k=2, а сами эти 4 композиции - пресекающиеся в 4-мерном пространстве параллелепипеды.
И наконец, для i=3 существует 3 композиции числа 5 со слагаемыми не превышающими k=2. $P(B_{3}=5)=\frac{3}{2^3}=\frac{3}{8}$
Для i<3 и i>5 нет подходящих композиций.
И что Вы по сути делаете? Складываете эти объемы параллелепипедов разной размерности, соотнесенные к объемам гиперкубов разной размерности и называете эту сумму вероятностью. Т.е. 1/32+1/4+3/8=0,65625. Бред сивой кобылы.

Теперь рассмотрим все композиции числа 5 и возьмем k=5, т.е. слагаемые в композициях могут принимать значения вплоть до 5:
5=1+1+1+1+1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+2+2
5=2+1+2
5=2+2+1
5=3+1+1
5=1+3+1
5=1+1+3
5=4+1
5=1+4
5=5
Количество композиций в которых i=5 слагаемых -1 шт. Значит $P(B_{5}=5)=\frac{1}{2^5}=\frac{1}{32}$
Количество композиций в которых i=4 слагаемых -4 шт. Значит $P(B_{4}=5)=\frac{4}{2^4}=\frac{1}{4}$
Количество композиций в которых i=3 слагаемых -6 шт. Значит $P(B_{3}=5)=\frac{6}{2^3}=\frac{3}{4}$
Количество композиций в которых i=2 слагаемых -2 шт. Значит $P(B_{2}=5)=\frac{2}{2^2}=\frac{1}{2}$
Количество композиций в которых i=1 слагаемых -1 шт. Значит $P(B_{1}=5)=\frac{1}{2^1}=\frac{1}{2}$

Сумма этих "Вероятностей" по Вашей итоговой формуле равна 2,03125.