Qu'est-ce que « Indicator decomposition » ?

Example 11.2 (Fixed points, runs, records)

A random permutation of $n$ items has on average one fixed point: item $i$ is in place with probability $1/n$, and there are $n$ items. A sequence of $n$ fair coin tosses has on average $1 + (n-1)/2$ runs: a new run starts at toss $i \ge 2$ with probability $\tfrac12$. A sequence of $n$ independent draws from a continuous law has on average $H_n = 1 + \tfrac12 + \dots + \tfrac1n$ records, since draw $i$ is the largest so far with probability $1/i$; for ten draws, about 2.93.

Example 11.3 (Distinct values)

$n$ draws from $N$ equally likely values show on average $N\big(1 - (1 - 1/N)^n\big)$ distinct values: value $v$ is missed by all draws with probability $(1-1/N)^n$. The same indicator gives the expected number of empty buckets in a hash table.