Случайные процессы
Stochastic на собеседовании
Технические собеседования в quantitative finance, ML-исследованиях и SRE регулярно проверяют понимание стохастических процессов. Не формулы - а умение быстро думать через вероятностные модели, применять закон Литтла из головы, объяснить нелинейность очередей или почему e^{B(t)} не является мартингалом. Этот урок - финальная практика перед реальным интервью.
- **Quantitative Finance** - вопросы по GBM, мартингалам, формуле Ито - стандарт для quant developer и researcher
- **ML Research** - сходимость SGD, диффузионные модели, Langevin MCMC - типичные темы в исследовательских интервью
- **SRE и Backend** - закон Литтла, нелинейность очередей, системный дизайн с теорией массового обслуживания - это ожидается на Senior-уровне
Предварительные знания
Марковские цепи: вопросы на собеседовании
Вопросы по марковским цепям - одни из самых частых на собеседованиях в quantitative finance, ML и data engineering. Ключевые темы: стационарное распределение, время первого возвращения, вероятности поглощения. Умение быстро получить стационарное распределение π из уравнений баланса - обязательный навык.
**Топ вопросов по Маркову на собеседованиях:** 1. «Найдите стационарное распределение цепи с матрицей P» - решить πP = π, ∑πᵢ = 1 2. «Какова вероятность поглощения из состояния i?» - система линейных уравнений hᵢ = pᵢⱼ + ∑ pᵢₖ hₖ 3. «Ожидаемое время первого возвращения в состояние i?» - mᵢ = 1/πᵢ 4. «PageRank - это какое распределение?» - стационарное распределение случайного блуждания по веб-графу 5. «Цепь сходится к π. Как быстро?» - спектральный зазор |λ₂|, время перемешивания
**Типичная ловушка на собеседовании:** вопрос о периодических цепях. Если цепь периодическая (например, блуждание на двудольном графе), стационарное распределение существует, но сходимости π^{(t)} → π нет. Правильный ответ: «Для эргодической цепи (нерегулярной + неприводимой) сходимость гарантирована; период нужно проверить».
| Вопрос на собеседовании | Ключевой факт | Типичная ошибка |
|---|---|---|
| Найди стационарное π | πP = π, ∑πᵢ = 1 (лев. собств. вектор) | Решать Pᵀπ = π - тоже верно |
| Ожидаемое время возврата в i | E[τᵢ] = 1/πᵢ | Путать с временем первого прохода |
| Сходимость к π | Геометрическая: ‖πᵗ-π‖ ≤ C·|λ₂|ᵗ | Считать, что любая цепь сходится |
| Поглощение в случайном блуждании | P(достичь N из i) = i/N | Пытаться считать напрямую через DP |
PageRank - это сложный алгоритм Google, не связанный с теорией вероятностей
PageRank = стационарное распределение случайного блуждания по веб-графу (с телепортацией: с вероятностью α перейти на случайную страницу). Это классическая задача нахождения π для эргодической цепи Маркова
π = стационарное распределение матрицы P = (1-α)·(матрица переходов) + α·(1/n)·J. Power iteration (многократное умножение на P) - это не что иное как симуляция случайного блуждания до стационарного состояния
На собеседовании: «Случайное блуждание на {0,...,10} поглощается на концах. Старт из 4. Цель - дойти до 10. Какова P(успеха)?»
Броуновское движение: вопросы на собеседовании
Вопросы по броуновскому движению и стохастическому анализу - стандарт для quantitative analyst и research scientist позиций. Ключевые навыки: правильно считать ковариации, применять формулу Ито, понимать геометрическое BM. Многие вопросы имеют элегантные решения через мартингальные аргументы.
**Топ вопросов по BM на собеседованиях:** 1. «Что такое квадратичная вариация BM?» - [B,B]_t = t (не t², не 0) 2. «Чему равно E[B(s)·B(t)]?» - min(s,t) 3. «Вычислите E[e^{σB(t)}]» - e^{σ²t/2} (моментообразующая нормального) 4. «Является ли B(t)² мартингалом?» - Нет! B²(t) - t - мартингал (формула Ито) 5. «Решите dX = aX dt + bX dB (GBM)» - X(t) = X₀ exp((a-b²/2)t + bB(t)) 6. «Как изменится формула Ито для f(t, B)?» - добавляется ∂f/∂t · dt
**Частая ловушка на собеседовании:** вопрос «Является ли e^{B(t)} мартингалом?» Ответ: **нет**. E[e^{B(t)}] = e^{t/2} растёт со временем - это субмартингал. Мартингалом является e^{B(t) - t/2}. Другой вариант ловушки: «Найдите E[B(3) | B(1) = 2]». Ответ: 2 (мартингальное свойство), а не 2/3 или 6.
| Вопрос | Правильный ответ | Частая ошибка |
|---|---|---|
| E[B(s)·B(t)], s≤t | min(s,t) = s | Ответить s·t или 0 |
| E[B(3) | B(1)=2] | 2 (мартингал) | Ответить 6 (линейная интерполяция) |
| Является ли e^{B(t)} мартингалом? | Нет, E[e^{B(t)}] = e^{t/2} растёт | Спутать с e^{B(t)-t/2} |
| d(B(t)³) по формуле Ито | 3B² dB + 3B dt | Написать 3B² dB (забыть поправку) |
| Квадратичная вариация cos(B) | ∫sin²(B_s)ds | Ответить 0 или t |
B(t)² - это мартингал, потому что B(t) - мартингал и x² - выпуклая функция
B(t)² - это субмартингал (неравенство Йенсена). Мартингалом является B(t)² - t. Поправка -t возникает из формулы Ито: d(B²) = 2B dB + dt
Неравенство Йенсена: E[f(B_t)|F_s] ≥ f(B_s) для выпуклой f - это субмартингал, не мартингал. Формула Ито показывает точно: d(B²) = 2B dB + dt, интегрируя: B(t)² = 2∫B dB + t. Мартингальная часть - 2∫B dB, компенсатор - t
На собеседовании: «Вычислите E[B(5) | B(2) = 3]».
Очереди и применения: вопросы на собеседовании
Вопросы по теории очередей встречаются в системном дизайне, SRE и бэкенд-интервью. Ключевые задачи: применить закон Литтла, рассчитать M/M/1 характеристики, найти узкое место в сети Джексона. Многие кандидаты знают M/M/1, но не понимают нелинейность очередей - именно это проверяют.
**Топ задач по очередям на собеседованиях:** 1. «Дано: λ=80 req/s, μ=100 req/s. Среднее время ответа?» - W = 1/(μ-λ) = 50 мс 2. «Зачем ограничивать загрузку 70%, а не 95%?» - нелинейность: L = ρ/(1-ρ) 3. «L=20 concurrent запросов, throughput=200 req/s. Среднее время?» - W = L/λ = 100 мс (закон Литтла) 4. «Два сервера vs один быстрый?» - M/M/2 vs M/M/1 с 2μ - M/M/2 всегда лучше при той же суммарной мощности 5. «Время ответа при CV=2 vs CV=1?» - P-K формула: в 2.5 раза хуже
**Системный дизайн + очереди:** На вопрос «Как улучшить latency сервиса?» правильная последовательность ответа: 1. измерить ρ = λ/μ 2. найти узкое место через сети Джексона 3. применить закон Литтла L = λW для оценки W по наблюдаемым метрикам 4. снизить CV времени обслуживания через batching или load balancing.
| Сценарий интервью | Формула | Ответ |
|---|---|---|
| «Сколько реплик нужно?» | ρ_per_server = λ/(c·μ) < 0.7 | c = ceil(λ/(0.7·μ)) |
| «Почему latency выросла при 90% load?» | L = ρ/(1-ρ): при ρ 0.8→0.9, L: 4→9 | Нелинейный рост очереди |
| «P95 vs среднее: почему разница?» | M/G/1: CV влияет на хвост | Тяжёлый хвост обслуживания |
| «Hedging (дублирование запросов)?» | W ~ 1/(μ-λ): меньшая CV | Снижает P99 за счёт избыточных запросов |
Два сервера со скоростью μ/2 каждый хуже одного сервера со скоростью μ
При высокой нагрузке два сервера со скоростью μ/2 лучше одного со скоростью μ (M/M/2 лучше M/M/1). При низкой нагрузке - примерно одинаково
M/M/2: каждый сервер обслуживает половину потока при вдвое меньшей скорости → ρ не меняется, но очередь формируется по более мягкому Erlang-C критерию. Ключевой момент: два сервера дают два параллельных «выхода», что снижает время ожидания при временных пиках нагрузки
На системном интервью: «На дашборде L=50 active connections, throughput=100 req/s. Каково среднее время ответа?»
Практические применения: вопросы уровня Senior
Senior-собеседования в ML и Systems требуют не только знать формулы, но и уметь быстро моделировать реальную задачу через стохастические процессы. Типичные вопросы: объяснить поведение системы под нагрузкой, выбрать правильную модель, оценить порядок ответа без точных вычислений.
**Архетипы задач Senior-уровня:** **«Estimate» задачи:** - «За сколько шагов SGD сойдётся к ε-оптимуму?» → O(1/(η·ε)) для выпуклых, O(1/ε²) для невыпуклых - «Насколько увеличится задержка если нагрузка вырастет с 70% до 90%?» → L(0.9)/L(0.7) = (9)/(2.33) ≈ 4× (нелинейно!) **«Design» задачи:** - «Как спроектировать A/B тест с правильными гарантиями?» → Sequential probability ratio test (SPRT), мартингалы - «Как детектировать аномалии в потоковых данных?» → CUSUM (cumulative sum) - мартингальный монитор **«Explain» задачи:** - «Почему batch size влияет на качество модели?» → Большой batch = маленький шум градиента = быстрая сходимость к sharp minimum
**Ответ на «Design» вопросы** строится по схеме: 1. определить случайный процесс, описывающий систему 2. написать ключевые уравнения (стационарное распределение / SDE / уравнения баланса) 3. применить теорему (OST / Little's Law / Ito formula) 4. интерпретировать результат инженерно. Демонстрация этой цепочки мышления - то, что отличает сильного кандидата.
| Реальная задача | Модель | Ключевой результат |
|---|---|---|
| A/B тест: когда остановить? | SPRT - мартингал E-value | Остановить при E_t > 1/α |
| Аномалия в метриках? | CUSUM - суммирование LLR | Детектировать сдвиг μ оптимально |
| Rate limiting (token bucket) | M/M/1 с конечным буфером | P(отклонить запрос) = ρ^K/(1-ρ^{K+1}) |
| Exponential backoff | Геометрическое распределение ожидания | Оптимально для Poisson коллизий |
На собеседовании нужно знать все формулы наизусть
Важнее понимать структуру задачи и уметь выводить ответы. «Я помню принцип: L = ρ/(1-ρ) - нелинейная зависимость» ценнее, чем зазубренная формула Эрланга-C без понимания
Интервьюер проверяет способность мыслить через стохастические процессы: определить процесс, написать уравнения, применить теорему. Правильно поставленная задача и приближённый ответ «порядка величины» - сильнее, чем точная формула без понимания её происхождения
Собеседование по системному дизайну: «Загрузка сервиса выросла с 70% до 90%. Во сколько раз увеличилось среднее число запросов в очереди?»
Ключевые идеи
- **Марков на интервью** - P(поглощения из i) = i/N, E[возврат] = 1/πᵢ, PageRank = стационарное π; проверяй периодичность
- **BM на интервью** - Cov(B(s),B(t)) = min(s,t), E[B(t)|B(s)] = B(s), B²-t мартингал, d(B³) = 3B²dB + 3B dt
- **Очереди на интервью** - W = L/λ (закон Литтла), W = 1/(μ-λ) для M/M/1, нелинейность L = ρ/(1-ρ)
- **Senior задачи** - структура ответа: процесс → уравнения → теорема → инженерная интерпретация; порядок величины важнее точной формулы
Связанные темы
Этот урок объединяет ключевые результаты всего курса в формате интервью:
- Мартингалы — OST для задачи о разорении, мартингальные аргументы для B(t)² - t, последовательные тесты
- Теория массового обслуживания — Закон Литтла, M/M/1, нелинейность нагрузки - стандартные вопросы системного дизайна
- Stochastic в ML и Systems — SGD как марковская цепь, DDPM как СДУ, inference latency через очереди - практический контекст
Вопросы для размышления
- На собеседовании вас спрашивают: «Почему SGD с большим batch size часто обобщается хуже?» Как связать это с теорией стохастических процессов?
- «Придумайте эксперимент, который покажет что сервис подчиняется M/M/1, а не M/G/1» - как стоит ответить?
- Самая сложная часть стохастических процессов на практике - что стоило бы объяснить иначе, чем написано в учебниках?