Опять теорвер: задача о филателисте

The Sleeping Beauty Problem?

собрано n марок

P(коллекция увеличится) = (N - n) / N

количество_поездок_для_одного_увеличения = N / (N - n)

терь всё это суммируем: N / (N - 0) + ... + N / (N - (N -1))

N^N ?

В целом правильно. Если N вынести за скобку, то в скобках будет гармонический ряд.

Ни слова не понял, кроме «кода на питоне». не буду писать код...

У нас N+n elements, N^(N+n) options. (N)C(N+n) choices, N! rearrangements.

И ответ: \sum_{n=0}^{\infty} \frac{{N+n \choose N}}{N^{N+n}} N! n

Хм.

Что значит «в среднем», и с какой вероятностью он должен собрать всю коллекцию?

https://ru.wikipedia.org/wiki/Математическое_ожидание

С вероятностью 1. В среднем - значит найти мат ожидание количества поездок.

Кстати, вопрос в корне неверен. Т.к. для того, чтобы с вероятностью p=1 собрать полную коллекцию, нужно сделать бесконечное количество поездок.

Т.е. ваше решение подразумевает сбор коллекции не полностью?

Господа, как призвать в тред модератора, чтобы предыдущего оратора забанили за оскорбление?

Ссылки на некорректные сообщения (32)

Спасибо!

сколько нужно сделать «в среднем» поездок, чтобы собрать всю коллекцию?

Гарантировано? Тогда бесконечность.

Я думаю надо остановить дискуссию о гарантированности сборки, вопрос не корректный и не особо имеет отношение к задаче.

Имеет. Прямое. Автор задачки про сундуки с теорвером дружил и дал строго формальную задачку. Кто не смог её строго формализовать, это их проблемы. А твоя задача в текущей формулировке не имеет смысла.

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

Ты даже не забавный.

Прочитал тред на >30 страницах, подумал, офигеть, а почему не запилить самому такой тред. Совершенно без знания вопроса, написал от лампочки задачу. Она не имеет красивого решения. Тем более, ты сам не знаешь, чего хочешь, «С вероятностью 1», блин.

Красивое решение у нее есть. Ответ n*ln(n). Выше оно приводилось. Про вероятность 1 как я уже написал вопрос не корректный.

Оно подразумевает сборку хотя бы m марок. Где m — от трех до N. Причем, скорей всего, m будет равно где-то так N/2.

n*ln(n)

Что

Ответ n*ln(n)

Неверно. Для вероятности 1 ответ — бесконечность. А этот ответ годится разве что для эдак процентов 30 (навскидку).

А ну в принципе да, оно неправильное.

Ну уж давай смоделируем поцесс что-ли? Если точнее n*(ln(n)+0.577)

Какая бесконечность? Мат ожидание бесконечность? А как же его тогда считают для известных распределений? Есть случайная величина - количество поездок. Она может принимать любое значение. Но мат ожидание у нее конечное.

Какая бесконечность?

За бесконечное количество поездок филателист соберет коллекцию.

А как же его тогда считают для известных распределений?

При чем здесь матожидание? Задача некорректна.

Есть случайная величина - количество поездок

Угу, стремящаяся к бесконечности при вероятности, стремящейся к 1.

Но мат ожидание у нее конечное.

Нет.

Процетирую условие:

Вопрос: сколько нужно сделать «в среднем» поездок, чтобы собрать всю коллекцию?

Ключевое слово здесь «в среднем», а не точно собрать.

ОК, среднее между 0 и \infty == \infty

А вот если моду какую-нибудь брать, или медиану, то ХЗ. Может, N^{N^N} и сработает. А может, будет {N!}^{N!} — ХЗ, лень такую фигню думать.

Итак, смоделированный процесс (на с#):

class Program
    {
        static void Main(string[] args)
        {
            int N = 100; // кол-во марок в коллекции
            int K = 10000; // количетво экспериментов

            var rnd = new Random();
            var slist = new List<int>(); // сюда сохраняем результаты экспериментов

            for (int i = 0; i < K; i++)
            {
                var attempts = new Dictionary<int, int>();
                for (int j = 0;; j++)
                {
                    int s = rnd.Next(N);
                    if (!attempts.ContainsKey(s)) attempts.Add(s,1);
                    if (attempts.Count == N)
                    {
                        slist.Add(j);
                        break;
                    }
                }
            }

            Console.WriteLine("avg = {0}, n*ln(n)={1}",slist.Average(),N*(Math.Log(N)+0.577));
        }
    }

Программа ставит 10000 экспериментов по сборке коллекции из 100 марок, после чего находит среднее количества поездок.

avg = 517.8028, n*ln(n)=518.217018598809

Замени количество марок на 666, а количество экспериментов на миллиард. Интересно, получится ли...

Слушай, ну вот давай возьмем для простоты дискретное распределение, к примеру Пуассона. Случайная величина может принимать любое значение > 0. Абсолютно любое. Но мат ожидание то у нее конечно. Бесконечное множество возможных значений никого не смущает.

Не, миллиард — мало. Давай, триллион. При грамотном распараллеливании за недельку посчитаешь.

Спасибо за совет, именно так и поступлю.

У тебя дискретная функция.

И что? Реально не понял ты к чему это?

Неправильно. Для N>1:

\sum_{n=0}^{\infty} \frac{\{{N+n \atop N}\}}{N^{N+n}} N! (N+n)

Где \{{N+n \atop N}\} - число Стирлинга второго рода.

Решение alfix - лучше, это - ребячество, но тоже должно работать.

«в среднем

Дак что такое в среднем? Мат ожидание?

Ты путаешь два разных понятия: «сколько нужно совершить поездок филателисту, чтобы гарантированно собрать всю коллекцию» и «известно, что филателист совершил K поездок и собрал всю коллекцию. Найти матожидание К». В первом случае ответ - бесконечность, так как сколько бы поездок он не совершил, всегда остаётся очень малая вероятность, что какая-то марка ему так и не попалась. Во втором случае будет какой-то ряд с конечной суммой, где эта вероятность и количество поездок перемножаются, так что ответ будет конечным.

Господа, как призвать в тред модератора, чтобы предыдущего оратора забанили за оскорбление?

Какой чувствительный попался... ну-ка, кто там предыдущий оратор?

<предыдущий пост — его же>

О_о, давай сразу пароль.

А по теме есть что сказать?

Я как раз ничего не путаю. В задаче просилось мат ожидание найти. Другие решили что нужно найти количество поездок до гарантированного сбора.

Я как раз ничего не путаю. В задаче просилось мат ожидание найти.

Нет, путаешь. Матожидание бесконечности - бесконечность. Если угодно, «матожидание количества поездок, необходимых для гарантированного сбора коллекции».

Другими словами, у тебя матожидание в условии не от той случайной величины берётся.

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

Дак что такое в среднем?

среднее арифметическое жеж

Мат ожидание?

да

Есть: валил бы ты с этого форума с такими темами, есть профильные. Правильное решение уже было, теперь надо тебя вытравить.

Понимаешь какая ситуация, здесь публичный форум и раздел science. Поэтому если тема тебе не интересна и сказать нечего, то «свалить» есть прекрасная возможность у тебя.

есть же люди которые все поняли и тем более правильно решили.

Ага, другую задачу.

Для вероятности 1 ответ — бесконечность

он наоборот имеет ввиду: для неограниченного (не бесконечного) числа попыток - вероятность собрать всю коллекцию - один.

а для вероятности 1 ответ - emptyset, а не эта ваша «бесконченость» (кроме случая n=1, в котором ответ 1)

сколько нужно сделать «в среднем» поездок

матожидание числа поездок

Другими словами, у тебя матожидание в условии не от той случайной величины берётся

где «не та» величина? я чего-то не понимаю?