Вася и Петя – аналитики в команде Х в Авито. За неделю в канал их команды пришло 2·n ad-hoc запросов. Вася и Петя смотрят их по очереди: первый смотрит Вася, второй — Петя, третий — снова Вася, и т. д. Каждый запрос независимо можно закрыть быстрым ответом с вероятностью p. Как только кто-то впервые дает быстрый ответ, все оставшиеся запросы недели забирает другой аналитик. Если за неделю никто не дал быстрый ответ, оставшиеся запросы никому не достаются. Пусть E_вася – среднее число оставшихся запросов, которые достанутся Васе, а E_петя – среднее число оставшихся запросов, которые достанутся Пете. Найдите E_петя - E_вася. Ответ округлять необязательно. Допустимая погрешность ±1. Пусть n = 159.0, p = 0.05.

Решение:

Пусть \(N\) — общее число запросов, \(p\) — вероятность быстрого ответа, \(q = 1-p\) — вероятность того, что запрос не будет закрыт быстро.

Вася и Петя смотрят запросы по очереди. Всего запросов \(N = 2n\).

Ожидаемое количество запросов, которые достанутся Васе (E_вася):

Вася смотрит запросы под номерами 1, 3, 5, ...

Если первый запрос (который смотрит Вася) не будет закрыт быстро (с вероятностью \(q\)), то Петя смотрит следующий запрос (№2). Если и он не будет закрыт быстро (с вероятностью \(q\)), то Вася смотрит запрос №3.

Можно предположить, что Вася и Петя получают запросы примерно поровну, если бы не было условия о быстром ответе. Однако, наличие быстрого ответа изменяет распределение.

Рассмотрим ожидаемое число оставшихся запросов.

Вероятность того, что запрос будет закрыт быстро (P(Success)) = p

Вероятность того, что запрос не будет закрыт быстро (P(Failure)) = q = 1 - p

Ожидаемое количество запросов, которое закроет Вася:

Вася смотрит запросы 1, 3, 5, ...

Петя смотрит запросы 2, 4, 6, ...

Если запрос №1 (Вася) закрыт быстро, то Вася получает 1 запрос. Если не закрыт (с вероятностью \(q\)), то Петя смотрит №2.

Если запрос №2 (Петя) закрыт быстро, то Петя получает 1 запрос. Если не закрыт (с вероятностью \(q\)), то Вася смотрит №3.

Пусть \(E_V\) — ожидаемое количество запросов, которое получит Вася, и \(E_P\) — ожидаемое количество запросов, которое получит Петя.

Общее ожидаемое количество запросов, которые будут закрыты, равно \(N \cdot p\) (если бы каждый запрос имел шанс быть закрытым). Однако, здесь другая механика.

Рассмотрим ожидаемое число запросов, которое достанется каждому аналитику, если бы они смотрели по очереди без остановки. Тогда в среднем каждый получит \(N/2\) запросов.

Система останавливается, как только кто-то дает быстрый ответ. Это значит, что вероятность быстрого ответа \(p\) очень важна.

Моделирование ситуации:

Пусть \(E_V\) — ожидаемое число запросов, доставшихся Васе.

E_вася — среднее число оставшихся запросов, которые достанутся Васе.

E_петя — среднее число оставшихся запросов, которые достанутся Пете.

Логика задачи:

Если Вася смотрит запрос №1 и закрывает его быстро (с вероятностью \(p\)), он получает 1 запрос. Если он не закрывает (с вероятностью \(q\)), то Петя смотрит №2.

Если Петя смотрит запрос №2 и закрывает его быстро (с вероятностью \(p\)), он получает 1 запрос. Если он не закрывает (с вероятностью \(q\)), то Вася смотрит №3.

Ожидаемое число запросов, которое будет закрыто:

Вероятность, что первый запрос будет закрыт (Васей): \(p\)

Вероятность, что второй запрос будет закрыт (Петя): \(q \times p\)

Вероятность, что третий запрос будет закрыт (Васей): \(q^2 \times p\)

Вероятность, что k-ый запрос будет закрыт: \(q^{k-1} \times p\)

Общее ожидаемое число запросов, которые будут закрыты = \( Σ_{k=1}^{2n} k \times q^{k-1} \times p \)

Это сложная сумма. Попробуем упростить.

Симметрия:

Вася и Петя смотрят запросы по очереди. Если бы не было условия о быстром закрытии, то они бы получили по \(n\) запросов.

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

Пусть \(K\) — номер запроса, который был закрыт первым.

Если \(K=1\) (Вася закрыл), Вася получает 1 запрос. Остальные \(2n-1\) запросов достаются другому аналитику (Петя).

Если \(K=2\) (Петя закрыл), Петя получает 1 запрос. Остальные \(2n-1\) запросов достаются другому аналитику (Вася).

Если \(K=3\) (Вася закрыл), Вася получает 1 запрос. Остальные \(2n-1\) запросов достаются другому аналитику (Петя).

Вероятность, что первый быстрый ответ будет на запросе \(k\):

\(P(K=k) = q^{k-1}p\) для \(k=1, 2, ..., 2n\)

Ожидаемое количество запросов для Васи:

\(E_V = Σ_{k=1}^{2n} (\text{если } k \text{ нечетное}) \times P(K=k) \times (1 \text{ запрос достается Васе}) + (\text{если } k \text{ четное}) \times P(K=k) \times (2n-1 \text{ запрос достается Васе}) \)

\(E_V = Σ_{j=1}^{n} P(K=2j-1) \times 1 + Σ_{j=1}^{n-1} P(K=2j) \times (2n-1) \)

\(E_V = Σ_{j=1}^{n} q^{2j-2}p \times 1 + Σ_{j=1}^{n-1} q^{2j-1}p \times (2n-1) \)

Ожидаемое количество запросов для Пети:

\(E_P = Σ_{k=1}^{2n} (\text{если } k \text{ нечетное}) \times P(K=k) \times (2n-1 \text{ запрос достается Пете}) + (\text{если } k \text{ четное}) \times P(K=k) \times (1 \text{ запрос достается Пете}) \)

\(E_P = Σ_{j=1}^{n} q^{2j-2}p \times (2n-1) + Σ_{j=1}^{n-1} q^{2j-1}p \times 1 \)

Разница:

\(E_P - E_V = Σ_{j=1}^{n} q^{2j-2}p \times (2n-1) + Σ_{j=1}^{n-1} q^{2j-1}p - (Σ_{j=1}^{n} q^{2j-2}p + Σ_{j=1}^{n-1} q^{2j-1}p \times (2n-1)) \)

\(E_P - E_V = Σ_{j=1}^{n} q^{2j-2}p \times (2n-1 - 1) + Σ_{j=1}^{n-1} q^{2j-1}p \times (1 - (2n-1)) \)

\(E_P - E_V = Σ_{j=1}^{n} q^{2j-2}p \times (2n-2) + Σ_{j=1}^{n-1} q^{2j-1}p \times (2 - 2n) \)

\(E_P - E_V = (2n-2) Σ_{j=1}^{n} q^{2j-2}p - (2n-2) Σ_{j=1}^{n-1} q^{2j-1}p \)

\(E_P - E_V = (2n-2) \times [ Σ_{j=1}^{n} (q^2)^{j-1}p - Σ_{j=1}^{n-1} q \times (q^2)^{j-1}p ] \)

\(E_P - E_V = (2n-2) \times p \times [ Σ_{j=1}^{n} (q^2)^{j-1} - q Σ_{j=1}^{n-1} (q^2)^{j-1} ] \)

\(E_P - E_V = (2n-2) \times p \times [ \frac{1-(q^2)^n}{1-q^2} - q \frac{1-(q^2)^{n-1}}{1-q^2} ] \)

Альтернативный подход:

Пусть \(E\) — ожидаемое количество запросов, которое достанется аналитику, который смотрит первым (Вася).

\(E = 1 \times p + (q \times (2n - 1 - E)) \)

\(E = p + 2nq - q - qE \)

\(E(1+q) = p + 2nq - q \)

\(E(1+q) = p + q(2n-1) \)

\(E = \frac{p + q(2n-1)}{1+q} \)

Это ожидаемое количество запросов, которое достанется первому аналитику, если бы он был единственным.

Рассмотрим разницу E_петя - E_вася.

Пусть \(E_1\) - ожидаемое число запросов, которое получит первый аналитик (Вася).

Пусть \(E_2\) - ожидаемое число запросов, которое получит второй аналитик (Петя).

Вероятность, что Вася закроет первый запрос: \(p\). Тогда Вася получает 1 запрос, Петя получает \(2n-1\) запросов. Это происходит с вероятностью \(p\).

Вероятность, что Вася не закроет первый запрос, а Петя закроет второй: \(q \times p\). Тогда Петя получает 1 запрос, Вася получает \(2n-1\) запросов.

Вероятность, что никто не закроет первые \(k\) запросов: \(q^k\).

Рассмотрим конкретный запрос, скажем, запрос №\(i\). Какова вероятность, что он достанется Васе?

Запрос №\(i\) достанется Васе, если он смотрит этот запрос (\(i\) нечетное) и ни один из предыдущих \(i-1\) запросов не был закрыт быстро.

\(P(\text{запрос } i \text{ достанется Васе}) = q^{i-1} \times p \text{ (если } i \text{ нечетное)}\)

\(P(\text{запрос } i \text{ достанется Пете}) = q^{i-1} \times p \text{ (если } i \text{ четное)}\)

E_вася = \( Σ_{i \text{ нечетное}}^{2n} i \times P(\text{запрос } i \text{ достанется Васе}) + Σ_{i \text{ четное}}^{2n} (2n - i + 1) \times P(\text{запрос } i \text{ достанется Васе}) \)

E_петя = \( Σ_{i \text{ нечетное}}^{2n} (2n - i + 1) \times P(\text{запрос } i \text{ достанется Пете}) + Σ_{i \text{ четное}}^{2n} i \times P(\text{запрос } i \text{ достанется Пете}) \)

Это также сложная формула.

Простая модель:

Представим, что запросы идут непрерывно. Вероятность, что любой конкретный запрос будет закрыт быстро — \(p\).

Ожидаемое число запросов, которые Вася сможет закрыть сам, если бы он смотрел все: \(np\).

Ожидаемое число запросов, которые Петя сможет закрыть сам, если бы он смотрел все: \(np\).

Ключевой момент: Кто первый дал быстрый ответ?

Пусть \(K\) — номер первого запроса, закрытого быстро.

Если \(K=1\) (Вася), Вася получил 1 запрос. Остальные \(2n-1\) запросов (№2, №3, ..., №2n) достаются Пете. Вероятность этого \(p\).

Если \(K=2\) (Петя), Петя получил 1 запрос. Остальные \(2n-1\) запросов (№1, №3, ..., №2n) достаются Васе. Вероятность этого \(qp\).

Если \(K=3\) (Вася), Вася получил 1 запрос. Остальные \(2n-1\) запросов достаются Пете. Вероятность этого \(q^2p\).

E_вася = \( p \times 1 + qp \times (2n-1) + q^2p \times 1 + q^3p \times (2n-1) + ... \)

\(E_вася = p(1 + q^2 + q^4 + ...) + qp(2n-1)(1 + q^2 + q^4 + ...) \)

\(E_вася = p Σ_{j=0}^{n-1} (q^2)^j + qp(2n-1) Σ_{j=0}^{n-1} (q^2)^j \)

\(E_вася = (p + qp(2n-1)) Σ_{j=0}^{n-1} (q^2)^j \)

\(E_вася = (p + 2nqp - qp) \times \frac{1-(q^2)^n}{1-q^2} \)

\(E_вася = (p(1-q) + 2nqp) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_вася = (p^2 + 2nqp) \times \frac{1-q^{2n}}{1-q^2} \)

E_петя = \( qp \times 1 + p \times (2n-1) + q^2p \times (2n-1) + q^3p \times 1 + ... \)

\(E_петя = qp(1 + q^2 + q^4 + ...) + p(2n-1)(1 + q^2 + q^4 + ...) \)

\(E_петя = (qp + p(2n-1)) Σ_{j=0}^{n-1} (q^2)^j \)

\(E_петя = (qp + 2np - p) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя = (p(2n-1-q)) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя = (p(2n-1-(1-p))) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя = (p(2n-2+p)) \times \frac{1-q^{2n}}{1-q^2} \)

E_петя - E_вася = \( (p(2n-2+p) - (p^2 + 2nqp)) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя - E_вася = (2np - 2p + p^2 - p^2 - 2nqp) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя - E_вася = (2np - 2nqp - 2p) \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя - E_вася = 2np(1-q) - 2p \times \frac{1-q^{2n}}{1-q^2} \)

\(E_петя - E_вася = 2np^2 - 2p \times \frac{1-q^{2n}}{1-q^2} \)

Это всё ещё не кажется верным.

Простой случай: n=1 (всего 2 запроса).

Вася смотрит 1, Петя смотрит 2.

Варианты:

1. Вася закрывает №1 (вероятность \(p\)). Вася: 1 запрос. Петя: 1 запрос (№2).
2. Вася не закрывает №1 (вероятность \(q\)), Петя закрывает №2 (вероятность \(p\)). Петя: 1 запрос. Вася: 1 запрос (№1).
3. Вася не закрывает №1 (вероятность \(q\)), Петя не закрывает №2 (вероятность \(q\)). Никто не получил запросов.

E_вася = \( p \times 1 + qp \times 1 = p + qp \)

E_петя = \( p \times 1 + qp \times 1 = p + qp \)

E_петя - E_вася = 0.

В формуле \(n=1\):

E_вася = \( (p + 2qp - qp) \times \frac{1-q^2}{1-q^2} = p+qp \)

E_петя = \( (qp + p(2-1)) \times \frac{1-q^2}{1-q^2} = qp+p \)

Разница 0. Работает для n=1.

Вернёмся к задаче:

n = 159.0, p = 0.05

q = 1 - p = 1 - 0.05 = 0.95

\(E_{петя} - E_{вася} = (2np^2 - 2p \times \frac{1-q^{2n}}{1-q^2}) \)

\(n = 159\)

\(p = 0.05\)

\(q = 0.95\)

\(q^2 = 0.95^2 = 0.9025\)

\(1-q^2 = 1 - 0.9025 = 0.0975\)

\(2n = 318\)

\(2np^2 = 2 \times 159 \times (0.05)^2 = 318 \times 0.0025 = 0.795\)

\(q^{2n} = (0.95)^{318}\)

Это очень маленькое число, близкое к 0.

\((0.95)^{318} ≈ 0\)

\(2p \times \frac{1-q^{2n}}{1-q^2} ≈ 2 \times 0.05 \times \frac{1 - 0}{0.0975} = 0.1 \times \frac{1}{0.0975} = 0.1 \times 10.2564 ≈ 1.02564 \)

\(E_{петя} - E_{вася} ≈ 0.795 - 1.02564 = -0.23064 \)

Этот результат отрицательный, что противоречит интуиции. Должно быть, в формуле есть ошибка.

Рассмотрим ещё раз:

Пусть \(E_V\) и \(E_P\) — ожидаемое число запросов, которые достанутся Васе и Пете соответственно.

Пусть \(E\) — ожидаемое количество запросов, которые достанутся тому, кто смотрит первым, если бы он один обрабатывал все запросы.

\(E = p \times 1 + q \times (N-1 - E) \)

\(E = p + q(N-1) - qE \)

\(E(1+q) = p + q(N-1) \)

\(E = \frac{p + q(N-1)}{1+q} = \frac{p + (1-p)(2n-1)}{1 + (1-p)} = \frac{p + (1-p)(2n-1)}{2-p} \)

Это ожидаемое количество запросов для первого аналитика, если бы он смотрел все \(2n\) запросов, и система останавливалась бы, когда он закрывал бы запрос (а если не закрывал, то передавал бы другому, который продолжает до последнего запроса).

Симметричный подход:

Пусть \(X_i\) — случайная величина, равная 1, если \(i\)-й запрос закрыт первым, и 0 иначе.

\(P(X_i = 1) = q^{i-1}p \)

E_вася = \( Σ_{i \text{ нечетное}, i ≤ 2n} P(X_i=1) \times 1 + Σ_{i \text{ четное}, i ≤ 2n} P(X_i=1) \times (2n - i) \)

\(E_{петя} = Σ_{i \text{ нечетное}, i ≤ 2n} P(X_i=1) \times (2n - i) + Σ_{i \text{ четное}, i ≤ 2n} P(X_i=1) \times 1 \)

\(E_{петя} - E_{вася} = Σ_{i \text{ нечетное}} P(X_i=1) \times (2n - i - 1) + Σ_{i \text{ четное}} P(X_i=1) \times (1 - (2n - i)) \)

\(E_{петя} - E_{вася} = Σ_{j=0}^{n-1} q^{2j}p \times (2n - (2j+1) - 1) + Σ_{j=1}^{n-1} q^{2j-1}p \times (1 - (2n - 2j)) \)

\(E_{петя} - E_{вася} = Σ_{j=0}^{n-1} q^{2j}p \times (2n - 2j - 2) + Σ_{j=1}^{n-1} q^{2j-1}p \times (1 - 2n + 2j) \)

\(E_{петя} - E_{вася} = 2p Σ_{j=0}^{n-1} q^{2j} \times (n - j - 1) + p Σ_{j=1}^{n-1} q^{2j-1} \times (2j - 2n + 1) \)

Введём понятие