tgoop.com/machinelearning_interview/1728
Last Update:
🎲 Задача со стажировки ШАД по вероятности: сколько участников добежит до вершины?
Представим забег 100 человек по узкому скользкому эскалатору. У каждого есть шанс поскользнуться и упасть — тогда он и все, кто бежал за ним, соскальзывают вниз. Добираются до вершины только те, кто был впереди последнего упавшего.
Мы можем настраивать вероятность падения p. Вопрос: какое значение `p` нужно выбрать, чтобы в среднем до вершины добегало ровно 20 человек из 100?
Обозначения:
N = 100: общее количество участников.
K = 20: желаемое среднее количество участников, достигших вершины.
p: вероятность того, что один участник поскользнется и упадет (эту величину нужно найти).
q = 1 - p: вероятность того, что один участник не упадет.
X: случайная величина, равная количеству участников, достигших вершины. Мы хотим, чтобы E[X] = 20.
Логика процесса:
Участник i (где i от 1 до 100) доберется до вершины тогда и только тогда, когда ни один из участников перед ним (включая его самого) не упадет.
То есть, участники 1, 2, ..., i должны успешно пройти свой путь.
Вероятность того, что участник 1 достигнет вершины = P(участник 1 не упал) = q.
Вероятность того, что участник 2 достигнет вершины = P(участник 1 не упал И участник 2 не упал) = q * q = q^2.
Вероятность того, что участник i достигнет вершины = P(участники 1, ..., i не упали) = q^i.
Математическое ожидание E[X]:
Математическое ожидание количества добравшихся до вершины можно вычислить как сумму вероятностей того, что каждый конкретный участник доберется до вершины. Это связано со свойством линейности математического ожидания и использованием индикаторных переменных (I_i = 1, если i-й участник добрался, 0 иначе; E[X] = E[sum(I_i)] = sum(E[I_i]) = sum(P(I_i=1))).
E[X] = P(участник 1 добрался) + P(участник 2 добрался) + ... + P(участник N добрался)
E[X] = q^1 + q^2 + q^3 + ... + q^N
Это сумма первых N членов геометрической прогрессии с первым членом a = q и знаменателем r = q. Формула суммы:
S_N = a * (1 - r^N) / (1 - r)
Подставляем наши значения:
E[X] = q * (1 - q^N) / (1 - q)
Решение уравнения:
Мы хотим, чтобы E[X] = K = 20, при N = 100.
20 = q * (1 - q^100) / (1 - q)
Вспомним, что q = 1 - p. Значит, 1 - q = p.
20 = (1 - p) * (1 - (1 - p)^100) / p
20p = (1 - p) * (1 - (1 - p)^100)
Это уравнение довольно сложно решить аналитически из-за члена (1 - p)^100. Однако мы можем сделать разумное предположение.
Приближение:
Поскольку мы ожидаем, что только 20 из 100 человек доберутся до вершины, это означает, что падения должны происходить относительно часто, и вероятность того, что все 100 человек не упадут (q^100), должна быть очень мала. То есть, q^100 ≈ 0.
Если q^100 пренебрежимо мало по сравнению с 1, то формула для E[X] упрощается:
E[X] ≈ q * (1 - 0) / (1 - q)
E[X] ≈ q / (1 - q)
Теперь подставим желаемое значение E[X] = 20:
20 ≈ q / (1 - q)
20 * (1 - q) ≈ q
20 - 20q ≈ q
20 ≈ 21q
q ≈ 20 / 21
Теперь найдем p:
p = 1 - q
p ≈ 1 - (20 / 21)
p ≈ 1 / 21
Проверка приближения:
Давайте проверим, насколько мало значение q^100 при q = 20/21:
q^100 = (20/21)^100 ≈ (0.95238)^100
Используя калькулятор, (20/21)^100 ≈ 0.0076. Это действительно мало по сравнению с 1.
Посчитаем E[X] с этим приближением:
E[X] = (20/21) * (1 - (20/21)^100) / (1 - 20/21)
E[X] = (20/21) * (1 - 0.0076) / (1/21)
E[X] = 20 * (1 - 0.0076)
E[X] = 20 * 0.9924
E[X] ≈ 19.848
Это очень близко к целевому значению 20.
Ответ:
Чтобы в среднем вершины достигали 20 ребят из 100, вероятность падения p для каждого участника нужно подобрать примерно равной 1/21 (или около 0.0476).
👇 Пишите свое решение в комментариях
@machinelearning_interview
BY Machine learning Interview
Share with your friend now:
tgoop.com/machinelearning_interview/1728