RUВход: сто бросков
Игральную кость бросают 100 раз; $S$ — сумма выпавших очков. Найти $\E S$.
Прямой путь — перечислить значения $S$ от 100 до 600 и для каждого найти вероятность: это число способов разложить его в сумму ста слагаемых от 1 до 6, делённое на $6^{100}$. Такой путь не длинный, а невозможный. Обходной путь — весь сегодняшний день:
$$S = X_1 + X_2 + \cdots + X_{100}, \qquad \E S = 100 \cdot \E X_1 = 100 \cdot 3.5 = 350$$Одна строка. Вопрос дня не в том, как считать среднее по определению, а в том, как увидеть сумму там, где её сразу не видно.
Величина, распределение, среднее
Случайная величина — число, которое зависит от того, какой исход реализовался. Распределение — список её значений с вероятностями; их сумма равна 1, и это бесплатная проверка.
Математическое ожидание$$\E X = \sum_i x_i\,\P(X = x_i)$$Среднее значение, взвешенное вероятностями. Для кубика $\E X = \frac{1+2+3+4+5+6}{6} = 3.5$.
Два замечания, которые дальше работают как инструменты. Первое: матожидание не обязано быть возможным значением — 3.5 на кубике не выпадет никогда, это центр тяжести распределения, а не прогноз. Второе, важнее: если $X$ принимает только значения 0 и 1, то
$$\E X = 0 \cdot \P(X = 0) + 1 \cdot \P(X = 1) = \P(X = 1)$$Среднее такой величины и есть вероятность единицы. Отсюда растёт весь метод индикаторов — и в обратную сторону, способ вытащить неизвестную вероятность из известного среднего.
Линейность и почему ей не нужна независимость
Определение выше группирует исходы по значениям величины. Ту же сумму можно записать по элементарным исходам — число то же, просто слагаемые ещё не собраны вместе:
$$\E X = \sum_{\omega} X(\omega)\,\P(\omega)$$В такой записи всё видно сразу:
$$\E(X + Y) = \sum_{\omega} \big(X(\omega) + Y(\omega)\big)\P(\omega) = \sum_{\omega} X(\omega)\P(\omega) + \sum_{\omega} Y(\omega)\P(\omega) = \E X + \E Y$$В выводе нет ни одной строки, где понадобилось бы знать, как $X$ и $Y$ связаны между собой: они складываются в каждом исходе по отдельности, а исходы одни и те же.
Линейность матожидания$$\E(aX + bY) = a\,\E X + b\,\E Y$$Верно всегда. Независимость $X$ и $Y$ не требуется и в выводе даже не упоминается.
Метод индикаторов
Индикатор события $A$ — величина $I_A$, равная 1, если $A$ произошло, и 0 иначе. По второму замечанию $\E I_A = \P(A)$ — и это всё, что о нём нужно знать.
Три шага- Реши, что ты считаешь, и введи индикатор $I_j$ на каждый такой объект.
- Проверь равенство $X = I_1 + I_2 + \cdots + I_n$: оно должно быть верно в каждом исходе.
- Сложи вероятности: $\E X = \P(I_1 = 1) + \cdots + \P(I_n = 1)$.
Разобранный пример. Сто писем случайным образом раскладывают по ста подписанным конвертам, по одному письму в конверт. Сколько в среднем писем попадёт в свой конверт? Прямой путь потребовал бы распределения числа совпадений — это формула беспорядков, полстраницы работы. Через индикаторы: $I_j = 1$, если $j$-е письмо попало в свой конверт; письмо равновероятно оказывается в любом из ста конвертов, значит $\P(I_j = 1) = \frac{1}{100}$, и
$$\E X = 100 \cdot \frac{1}{100} = 1$$Ответ не зависит от числа писем. И заметь: индикаторы здесь откровенно зависимы (если 99 писем легли верно, сотое обязано лечь верно тоже) — линейность на это не смотрит.
Куда вешать индикаторЭто главное решение в каждой такой задаче, и принимается оно до всех вычислений. Возьми вопрос и найди слово сразу после «число» или «сколько»: считаешь письма — индикатор на письмо, считаешь грани — на грань, пары соседей — на пару. Индикатор «на действие» (на бросок, на человека) почти всегда бессмыслен: непонятно, что даст его сумма.
Как считать вероятность одного слагаемого
Разложение построено, осталось найти $\P(I_j = 1)$. Три хода закрывают почти всё.
Симметрия. Если объекты равноправны, все $\P(I_j = 1)$ равны одному и тому же $p$, и ответ сразу $\E X = np$. Так было с письмами, так же работает извлечение без возвращения.
Дополнение. Свойство «объект встретился хотя бы раз» прямым счётом разваливается на случаи «ровно один раз», «ровно два» и так далее, а противоположное — «не встретился ни разу» — всегда одно и считается одним произведением. Поэтому
$$\P(I_j = 1) = 1 - \P(\text{объект } j \text{ не встретился ни разу})$$Обратный ход. Иногда неизвестна как раз вероятность слагаемого, зато известно среднее всей суммы. Тогда равенство $\E X = \sum_j \P(I_j = 1)$ читается справа налево — как уравнение.
Пример. Прибор за час даёт не более одного сбоя, вероятность сбоя за час равна $0.12$, четыре четверти часа равноправны; найти вероятность $q$ сбоя в конкретную четверть. Число сбоев за час $X$ принимает только значения 0 и 1, поэтому $\E X = 0.12$; с другой стороны, $X = I_1 + I_2 + I_3 + I_4$ и $\E X = 4q$. Отсюда $q = 0.03$.
Как читать «не более одного события за период»Эта фраза — не украшение условия, а указание, каким действием собирать вероятности: события «сбой в первой четверти», …, «сбой в четвёртой» попарно несовместны, два сразу произойти не могут. Дальше работает объявленное в блоке «Мост» правило для несовместных событий: $\P(\text{сбой за час}) = 4q$, а не $1 - (1-q)^4$. Обратная сторона той же фразы — величина $X$ принимает только значения 0 и 1, и её среднее равно $\P(X = 1)$.
Дисперсия: когда можно складывать
Дисперсия показывает, насколько далеко значения разлетаются от центра:
$$\D X = \E\big[(X - \E X)^2\big] = \E X^2 - (\E X)^2$$Правая запись удобнее для счёта: для кубика $\E X^2 = \frac{91}{6}$, поэтому $\D X = \frac{91}{6} - 3.5^2 = \frac{35}{12} \approx 2.92$.
Проверьте ковариациюДля конечных дисперсий $\D(X+Y)=\D X+\D Y+2\Cov(X,Y)$. Независимость достаточна для нулевой ковариации, но не необходима. Нулевая ковариация тоже даёт сложение дисперсий. При $Y=X$ имеем $\D(X+X)=4\D X$, а не $2\D X$: смешанное слагаемое нельзя забывать. Вывод и практика взвешенных оценок — день 15.
Ни в одной сегодняшней задаче дисперсия не понадобится: она стоит здесь потому, что оговорка про независимость видна лишь рядом с линейностью, которой такая оговорка не нужна.
Шесть распределений, которые надо знать наизусть
| Распределение | Когда возникает | $\E$ | $\D$ |
|---|
| Бернулли $(p)$ | один опыт: успех или нет | $p$ | $p(1-p)$ |
| Биномиальное $(n, p)$ | число успехов в $n$ независимых опытах | $np$ | $np(1-p)$ |
| Геометрическое $(p)$ | число попыток до первого успеха включительно | $\dfrac1p$ | $\dfrac{1-p}{p^2}$ |
| Пуассона $(\lambda)$ | число редких событий за период | $\lambda$ | $\lambda$ |
| Равномерное $[a,b]$ | точка наудачу на отрезке | $\dfrac{a+b}{2}$ | $\dfrac{(b-a)^2}{12}$ |
| Показательное $(\lambda)$ | время до события | $\dfrac1\lambda$ | $\dfrac{1}{\lambda^2}$ |
Биномиальное — сумма $n$ бернуллиевских, обе его формулы получаются на месте: $\E$ — по линейности, $\D$ — по независимости опытов. Остальные четыре строки — геометрическое, пуассоновское, равномерное и показательное — сегодняшними средствами не выводятся, их придётся выучить. В геометрическом слово «включительно» существенно: если удачную попытку не считать, среднее станет $\frac{1-p}{p}$.
Процессы: сколько шагов до успеха
Величина «число шагов, пока не случится то-то» в сумму не раскладывается: слагаемых заранее не видно, их количество само случайно. Здесь нужен другой приём.
Условие на первый шагПервый шаг делаем в любом случае. Дальше два варианта: с вероятностью $p$ успех и конец; с вероятностью $1-p$ неудача — и мы оказываемся ровно в исходной ситуации. Это формула полной вероятности, применённая к среднему:
$$\E = 1 + (1-p)\,\E \;\Longrightarrow\; p\,\E = 1 \;\Longrightarrow\; \E = \frac1p$$ Слово «ровно» здесь несущее: приём законен только потому, что после неудачи впереди процесс, устроенный точно так же, как в начале. Если после неудачи условия меняются, уравнение неверно.
Что делать, когда $p$ меняется по ходу. Разрезать процесс на этапы так, чтобы внутри этапа вероятность успеха была постоянной. Этап стоит $1/p_k$ шагов в среднем, а общее число шагов — сумма стоимостей этапов; складывать их можно опять-таки по линейности, хотя этапы очевидно зависимы.
Пример на два этапа. Монету бросают, пока не выпадут и орёл, и решка. Первый бросок даёт какой-то результат — этап стоит ровно 1 бросок. Дальше ждём противоположный результат, его вероятность $\frac12$ на каждом броске — этап стоит 2 броска. Итого $\E = 1 + 2 = 3$.
Заход с хвоста
Есть третий способ обойти распределение: считать не «ровно $k$», а «не меньше $k$».
Хвостовая формулаДля целой неотрицательной величины
$$\E X = \sum_{k \ge 1} \P(X \ge k)$$Непрерывный аналог для неотрицательной величины: $\E X = \int_0^{\infty}\P(X > t)\,dt$.
Почему это верно: подставь $\P(X \ge k) = \sum_{m \ge k}\P(X = m)$ и посмотри, сколько раз войдёт каждое $\P(X = m)$. Ровно в $m$ слагаемых, при $k = 1, 2, \ldots, m$, — значит справа собирается $\sum_m m\,\P(X = m)$, то есть исходное определение матожидания.
Хвост особенно удобен для максимума: событие $\{\max \le t\}$ означает «все величины не больше $t$» и для независимых величин распадается в произведение, а $\{\max = t\}$ — нет.
Тождество, которое экономит половину работы. В каждом исходе
$$\max(X, Y) + \min(X, Y) = X + Y$$— слева и справа те же два числа, только в другом порядке, — поэтому и $\E\max + \E\min = \E X + \E Y$. Из пары «максимум и минимум» считают ту величину, чей хвост проще, а вторую получают вычитанием: у двух кубиков проще минимум, его хвост раскладывается в произведение сразу, без перехода к дополнению.
Симметрия промежутков
Есть класс задач, где хвост можно даже не начинать считать. Образец: в колоде из $n$ карт помечены $k$ (скажем, четыре туза среди 52); сколько карт в среднем приходится снять до первой помеченной включительно?
Лемма о промежутках$$\E = \frac{n+1}{k+1}$$Помеченные карты разбивают непомеченные на $k+1$ промежуток. Промежутки равноправны: замкни колоду в кольцо, добавив в место склейки ещё одну помеченную карту, и поверни кольцо случайно — любой промежуток переходит в любой другой поворотом, значит в среднем они равны. Непомеченных карт $n-k$, в промежутке в среднем $\frac{n-k}{k+1}$, а до первой помеченной проходят один промежуток и саму карту: $\E = \frac{n-k}{k+1} + 1 = \frac{n+1}{k+1}$.
Непрерывный близнец той же симметрии: $n$ независимых равномерных точек делят отрезок $[0,1]$ на $n+1$ в среднем равный кусок, поэтому среднее наименьшей из них равно $\frac{1}{n+1}$, а наибольшей $\frac{n}{n+1}$. Дискретная версия работает сегодня в b0405 и s0401, непрерывная — как проверка в b0403 и y0404.
Что должно остаться в голове
- Не строй распределение, пока не проверил, нельзя ли разложить величину в сумму.
- Линейность верна всегда; для сложения дисперсий достаточно нулевых ковариаций, в частности независимости.
- Индикатор вешается на объект, который считаешь, а не на действие.
- Вероятность слагаемого берётся симметрией, дополнением или обратным ходом из известного среднего.
- До первого успеха $\E = 1/p$; меняется $p$ — режь на этапы и складывай их стоимости.
- Максимум считай хвостом или через тождество «максимум плюс минимум равно сумме»; $k$ помеченных объектов делят ряд на $k+1$ в среднем равных промежутка.
ENOpening: one hundred rolls
Roll a die 100 times; let $S$ be the sum of the scores. Find $\E S$.
The direct route lists the values of $S$ from 100 to 600 and finds the probability of each: the number of ways to write it as a sum of one hundred terms from 1 to 6, divided by $6^{100}$. This route is not merely long—it is impossible. The shortcut is the theme of the day:
$$S=X_1+X_2+\cdots+X_{100},\qquad\E S=100\cdot\E X_1=100\cdot3.5=350$$One line. The point of the day is not how to average from the definition, but how to see a sum where it is not immediately visible.
Quantity, distribution, expectation
A random variable is a number determined by which outcome occurs. Its distribution is a list of its values and their probabilities; the probabilities sum to 1, a free check.
Expected value$$\E X=\sum_i x_i\,\P(X=x_i)$$The probability-weighted average. For a die, $\E X=\frac{1+2+3+4+5+6}{6}=3.5$.
Two observations will become tools. First: an expectation need not be a possible value—3.5 can never appear on a die; it is the distribution’s center of mass, not a forecast. Second, more important: if $X$ takes only the values 0 and 1, then
$$\E X=0\cdot\P(X=0)+1\cdot\P(X=1)=\P(X=1)$$The mean of such a variable is the probability of one. This is the foundation of indicators, and the reverse direction lets you recover an unknown probability from a known mean.
Linearity and why it needs no independence
The definition groups outcomes by the values of the variable. The same sum can be written over elementary outcomes—the value is unchanged; the summands have simply not been grouped:
$$\E X=\sum_{\omega}X(\omega)\,\P(\omega)$$Now the key identity is immediate:
$$\E(X+Y)=\sum_{\omega}(X(\omega)+Y(\omega))\P(\omega)=\sum_{\omega}X(\omega)\P(\omega)+\sum_{\omega}Y(\omega)\P(\omega)=\E X+\E Y$$The derivation has no line where we need to know how $X$ and $Y$ are related: they are added outcome by outcome, over the same outcomes.
Linearity of expectation$$\E(aX+bY)=a\,\E X+b\,\E Y$$True always. $X$ and $Y$ need not be independent, and independence is never mentioned in the derivation.
The indicator method
The indicator of event $A$ is a variable $I_A$ equal to 1 when $A$ occurs and 0 otherwise. By the second observation, $\E I_A=\P(A)$; that is all you need to know.
Three steps- Decide what you are counting and introduce an indicator $I_j$ for each such object.
- Check $X=I_1+I_2+\cdots+I_n$; it must hold for every outcome.
- Add the probabilities: $\E X=\P(I_1=1)+\cdots+\P(I_n=1)$.
Worked example. Randomly place 100 letters into 100 labeled envelopes, one letter per envelope. How many letters land in their own envelope on average? Directly, we would need the distribution of the number of matches—the derangement formula and half a page of work. With indicators, let $I_j=1$ if letter $j$ reaches its own envelope. Every letter is equally likely to be in any of the 100 envelopes, so $\P(I_j=1)=\frac1{100}$, and
$$\E X=100\cdot\frac1{100}=1$$The answer does not depend on the number of letters. Notice that the indicators are visibly dependent (if 99 letters are correct, the hundredth must be correct too), but linearity does not care.
Where to attach the indicatorThis is the main decision in every such problem, and it comes before any calculation. Look for the word immediately after “number of” or “how many”: if you count letters, attach the indicator to a letter; if faces, to a face; if neighboring pairs, to a pair. An indicator attached to an action (a roll or a person) is almost always meaningless: it is unclear what its sum would represent.
Finding the probability of one summand
The decomposition is ready; now find $\P(I_j=1)$. Three moves cover almost everything.
Symmetry. If objects are interchangeable, all $\P(I_j=1)$ equal the same $p$, so $\E X=np$ immediately. This was true for the letters and works for sampling without replacement as well.
Complement. The property “an object appears at least once” breaks into “exactly once,” “exactly twice,” and so on under a direct count. Its opposite—“the object never appears”—is one event and one product:
$$\P(I_j=1)=1-\P(\text{object }j\text{ never appears})$$Reverse direction. Sometimes the summand probability is unknown but the mean of the whole sum is known. Then $\E X=\sum_j\P(I_j=1)$ is read right to left, as an equation.
Example. A device has at most one failure per hour, and the probability of a failure in an hour is $0.12$. The four 15-minute quarters are symmetric; find the probability $q$ of failure in a particular quarter. The hourly count $X$ takes only 0 and 1, so $\E X=0.12$. Also $X=I_1+I_2+I_3+I_4$, hence $\E X=4q$ and $q=0.03$.
How to read “at most one event per period”This phrase is not decorative; it tells you how to combine probabilities. “Failure in the first quarter,” …, “failure in the fourth quarter” are pairwise disjoint: two cannot happen at once. Therefore the Bridge rule gives $\P(\text{failure in an hour})=4q$, not $1-(1-q)^4$. The other side of the same phrase is that $X$ takes only 0 and 1, so its mean is $\P(X=1)$.
Variance: when addition is valid
Variance measures how far values spread from the center:
$$\D X=\E[(X-\E X)^2]=\E X^2-(\E X)^2$$The right-hand form is easier to calculate. For a die, $\E X^2=\frac{91}{6}$, so $\D X=\frac{91}{6}-3.5^2=\frac{35}{12}\approx2.92$.
Check covarianceFor finite variances, $\D(X+Y)=\D X+\D Y+2\Cov(X,Y)$. Independence is sufficient for zero covariance, but not necessary. Zero covariance also permits variance addition. When $Y=X$, $\D(X+X)=4\D X$, not $2\D X$: the cross term must be retained. Derivation and weighted-estimator practice appear in day 15.
No problem today needs variance. It appears here because the independence qualification becomes visible only next to linearity, which needs no such qualification.
Six distributions to know by heart
| Distribution | When it occurs | $\E$ | $\D$ |
|---|
| Bernoulli $(p)$ | one trial: success or failure | $p$ | $p(1-p)$ |
| Binomial $(n,p)$ | number of successes in $n$ independent trials | $np$ | $np(1-p)$ |
| Geometric $(p)$ | number of trials through the first success | $\dfrac1p$ | $\dfrac{1-p}{p^2}$ |
| Poisson $(\lambda)$ | number of rare events in a period | $\lambda$ | $\lambda$ |
| Uniform $[a,b]$ | a random point on an interval | $\dfrac{a+b}{2}$ | $\dfrac{(b-a)^2}{12}$ |
| Exponential $(\lambda)$ | time until an event | $\dfrac1\lambda$ | $\dfrac1{\lambda^2}$ |
The binomial variable is a sum of $n$ Bernoulli variables, so both of its formulas can be derived on the spot: expectation by linearity and variance by independence. The other four rows—geometric, Poisson, uniform, and exponential—are not derived by today’s tools; memorize them. In the geometric distribution, “through” (including the successful trial) matters: if the successful trial is not counted, the mean becomes $\frac{1-p}{p}$.
Processes: how many steps until success
The quantity “number of steps until something happens” does not decompose into a sum: the summands are not known in advance, and their number is random. Use a different move.
Condition on the first stepAlways take the first step. Then two possibilities: with probability $p$ it succeeds and the process ends; with probability $1-p$ it fails and we are exactly back in the original situation. This is the law of total probability applied to an expectation:
$$\E=1+(1-p)\E\;\Longrightarrow\;p\E=1\;\Longrightarrow\;\E=\frac1p$$ “Exactly” is the essential word: the method is valid only because after a failure the remaining process has exactly the same structure as at the start. If the conditions change after failure, the equation is false.
When $p$ changes over time. Split the process into stages in which the success probability is constant. Stage $k$ costs $1/p_k$ steps on average, and the total number of steps is the sum of the stage costs; linearity allows this even though the stages are plainly dependent.
Two-stage example: toss a coin until both heads and tails have appeared. The first toss gives one result and costs exactly 1 toss. Then wait for the opposite result, whose chance is $\frac12$ on each toss; that stage costs 2 tosses. Thus $\E=1+2=3$.
Approach from the tail
A third way around a distribution is to count not “exactly $k$” but “at least $k$.”
Tail formulaFor a nonnegative integer-valued variable,
$$\E X=\sum_{k\ge1}\P(X\ge k)$$The continuous analogue for a nonnegative variable is $\E X=\int_0^\infty\P(X>t)\,dt$.
Why it works: substitute $\P(X\ge k)=\sum_{m\ge k}\P(X=m)$ and count how often each $\P(X=m)$ appears. It appears in exactly $m$ terms, for $k=1,2,\ldots,m$, so the right side becomes $\sum_m m\,\P(X=m)$, the original definition of expectation.
The tail is particularly convenient for a maximum: $\{\max\le t\}$ means that all variables are at most $t$ and factors for independent variables, whereas $\{\max=t\}$ does not.
An identity that halves the work. For every outcome,
$$\max(X,Y)+\min(X,Y)=X+Y$$The same two numbers appear on both sides, just in a different order, so $\E\max+\E\min=\E X+\E Y$. For maximum and minimum, compute whichever has the simpler tail, then subtract to obtain the other. For two dice, the minimum is easier: its tail factors immediately, without a complement.
Spacing symmetry
There is a class of problems where you do not even need to start the tail calculation. Example: a deck of $n$ cards contains $k$ marked cards (say, four aces among 52). How many cards must be drawn on average before the first marked card, inclusive?
Spacing lemma$$\E=\frac{n+1}{k+1}$$The marked cards split the unmarked cards into $k+1$ gaps. The gaps are symmetric: close the deck into a circle by adding one more marked card at the join, then rotate the circle uniformly; any gap maps to any other. Therefore their expected sizes are equal. There are $n-k$ unmarked cards, so each gap has expected size $\frac{n-k}{k+1}$. To reach the first marked card, cross one gap and the card itself:
$$\E=\frac{n-k}{k+1}+1=\frac{n+1}{k+1}$$ The continuous twin is the same symmetry: $n$ independent uniform points split $[0,1]$ into $n+1$ gaps of equal expected length, so the expected minimum is $\frac1{n+1}$ and the expected maximum is $\frac n{n+1}$. The discrete version is used in b0405 and s0401; the continuous version checks b0403 and y0404.
What should stay with you
- Do not construct a distribution until you have checked whether the quantity can be decomposed as a sum.
- Linearity always holds; zero covariances suffice for variance addition, in particular under independence.
- Attach an indicator to the object you are counting, not to the action.
- Find the summand probability by symmetry, the complement, or reversing a known expectation.
- Until the first success, $\E=1/p$; if $p$ changes, split into stages and add their costs.
- Compute a maximum via its tail or the identity “maximum plus minimum equals the sum”; $k$ marked objects divide a row into $k+1$ equal-in-expectation gaps.