Schuette–Nesbitt formula

In mathematics, the Schuette–Nesbitt formula is a generalization of the inclusion–exclusion principle. It is named after Donald R. Schuette and Cecil J. Nesbitt.

The probabilistic version of the Schuette–Nesbitt formula has practical applications in actuarial science, where it is used to calculate the net single premium for life annuities and life insurances based on the general symmetric status.

Combinatorial versions edit

Consider a set $Ω$ and subsets $A 1, ..., A m$ . Let

N(\omega )=\sum _{n=1}^{m}1_{A_{n}}(\omega ),\qquad \omega \in \Omega ,

(1)

denote the number of subsets to which $ω \in Ω$ belongs, where we use the indicator functions of the sets $A 1, ..., A m$ . Furthermore, for each $k \in {0, 1, ..., m}$ , let

N_{k}(\omega )=\sum _{\scriptstyle J\subset \{1,\ldots ,m\} \atop \scriptstyle |J|=k}1_{\cap _{j\in J}A_{j}}(\omega ),\qquad \omega \in \Omega ,

(2)

denote the number of intersections of exactly $k$ sets out of $A 1, ..., A m$ , to which $ω$ belongs, where the intersection over the empty index set is defined as $Ω$ , hence $N 0 = 1 Ω$ . Let $V$ denote a vector space over a field $R$ such as the real or complex numbers (or more generally a module over a ring $R$ with multiplicative identity). Then, for every choice of $c 0, ..., c m \in V$ ,

\sum _{n=0}^{m}1_{\{N=n\}}c_{n}=\sum _{k=0}^{m}N_{k}\sum _{l=0}^{k}(-1)^{k-l}{\binom {k}{l}}c_{l},

(3)

where $1 {N = n}$ denotes the indicator function of the set of all $ω \in Ω$ with $N (ω) = n$ , and $\textstyle {\binom {k}{l}}$ is a binomial coefficient. Equality (3) says that the two $V$ -valued functions defined on $Ω$ are the same.

Proof of (3) edit

We prove that (3) holds pointwise. Take $ω \in Ω$ and define $n = N (ω)$ . Then the left-hand side of (3) equals $c n$ . Let $I$ denote the set of all those indices $i \in {1, ..., m}$ such that $ω \in A i$ , hence $I$ contains exactly $n$ indices. Given $J \subset {1, ..., m}$ with $k$ elements, then $ω$ belongs to the intersection $\cap j \in J A j$ if and only if $J$ is a subset of $I$ . By the combinatorial interpretation of the binomial coefficient, there are $N k =$ $\textstyle {\binom {n}{k}}$ such subsets (the binomial coefficient is zero for $k > n$ ). Therefore the right-hand side of (3) evaluated at $ω$ equals

\sum _{k=0}^{m}{\binom {n}{k}}\sum _{l=0}^{k}(-1)^{k-l}{\binom {k}{l}}c_{l}=\sum _{l=0}^{m}\underbrace {\sum _{k=l}^{n}(-1)^{k-l}{\binom {n}{k}}{\binom {k}{l}}} _{=:\,(*)}c_{l},

where we used that the first binomial coefficient is zero for $k > n$ . Note that the sum (*) is empty and therefore defined as zero for $n < l$ . Using the factorial formula for the binomial coefficients, it follows that

{\begin{aligned}(*)&=\sum _{k=l}^{n}(-1)^{k-l}{\frac {n!}{k!\,(n-k)!}}\,{\frac {k!}{l!\,(k-l)!}}\\&=\underbrace {\frac {n!}{l!\,(n-l)!}} _{={\binom {n}{l}}}\underbrace {\sum _{k=l}^{n}(-1)^{k-l}{\frac {(n-l)!}{(n-k)!\,(k-l)!}}} _{=:\,(**)}\\\end{aligned}}

Rewriting (**) with the summation index $j = k - l$ und using the binomial formula for the third equality shows that

{\begin{aligned}(**)&=\sum _{j=0}^{n-l}(-1)^{j}{\frac {(n-l)!}{(n-l-j)!\,j!}}\\&=\sum _{j=0}^{n-l}(-1)^{j}{\binom {n-l}{j}}=(1-1)^{n-l}=\delta _{ln},\end{aligned}}

which is the Kronecker delta. Substituting this result into the above formula and noting that $n$ choose $l$ equals $1$ for $l = n$ , it follows that the right-hand side of (3) evaluated at $ω$ also reduces to $c n$ .

Representation in the polynomial ring edit

As a special case, take for $V$ the polynomial ring $R [x]$ with the indeterminate $x$ . Then (3) can be rewritten in a more compact way as

\sum _{n=0}^{m}1_{\{N=n\}}x^{n}=\sum _{k=0}^{m}N_{k}(x-1)^{k}.

(4)

This is an identity for two polynomials whose coefficients depend on $ω$ , which is implicit in the notation.

Proof of (4) using (3): Substituting $c n = x n$ for $n \in {0, ..., m}$ into (3) and using the binomial formula shows that

\sum _{n=0}^{m}1_{\{N=n\}}x^{n}=\sum _{k=0}^{m}N_{k}\underbrace {\sum _{l=0}^{k}{\binom {k}{l}}(-1)^{k-l}x^{l}} _{=\,(x-1)^{k}},

which proves (4).

Representation with shift and difference operators edit

Consider the linear shift operator $E$ and the linear difference operator $Δ$ , which we define here on the sequence space of $V$ by

{\begin{aligned}E:V^{\mathbb {N} _{0}}&\to V^{\mathbb {N} _{0}},\\E(c_{0},c_{1},c_{2},c_{3},\ldots )&\mapsto (c_{1},c_{2},c_{3},\ldots ),\\\end{aligned}}

and

{\begin{aligned}\Delta :V^{\mathbb {N} _{0}}&\to V^{\mathbb {N} _{0}},\\\Delta (c_{0},c_{1},c_{2},c_{3}\ldots )&\mapsto (c_{1}-c_{0},c_{2}-c_{1},c_{3}-c_{2},\ldots ).\\\end{aligned}}

Substituting $x = E$ in (4) shows that

\sum _{n=0}^{m}1_{\{N=n\}}E^{n}=\sum _{k=0}^{m}N_{k}\Delta ^{k},

(5)

where we used that $Δ = E - I$ with $I$ denoting the identity operator. Note that $E 0$ and $Δ 0$ equal the identity operator $I$ on the sequence space, $E k$ and $Δ k$ denote the $k$ -fold composition.

Direct proof of (5) by the operator method

To prove (5), we first want to verify the equation

\sum _{n=0}^{m}1_{\{N=n\}}E^{n}=\prod _{j=1}^{m}(1_{A_{j}^{\mathrm {c} }}I+1_{A_{j}}E)

(✳)

involving indicator functions of the sets $A 1, ..., A m$ and their complements with respect to $Ω$ . Suppose an $ω$ from $Ω$ belongs to exactly $k$ sets out of $A 1, ..., A m$ , where $k \in {0, ..., m}$ , for simplicity of notation say that $ω$ only belongs to $A 1, ..., A k$ . Then the left-hand side of (✳) is $E k$ . On the right-hand side of (✳), the first $k$ factors equal $E$ , the remaining ones equal $I$ , their product is also $E k$ , hence the formula (✳) is true.

Note that

{\begin{aligned}1_{A_{j}^{\mathrm {c} }}I+1_{A_{j}}E&=I-1_{A_{j}}I+1_{A_{j}}E\\&=I+1_{A_{j}}(E-I)=I+1_{A_{j}}\Delta ,\qquad j\in \{0,\ldots ,m\}.\end{aligned}}

Inserting this result into equation (✳) and expanding the product gives

\sum _{n=0}^{m}1_{\{N=n\}}E^{n}=\sum _{k=0}^{m}\sum _{\scriptstyle J\subset \{1,\ldots ,m\} \atop \scriptstyle |J|=k}1_{\cap _{j\in J}A_{j}}\Delta ^{k},

because the product of indicator functions is the indicator function of the intersection. Using the definition (2), the result (5) follows.

Let $(Δ k c) 0$ denote the 0th component of the $k$ -fold composition $Δ k$ applied to $c = (c 0, c 1, ..., c m, ...)$ , where $Δ 0$ denotes the identity. Then (3) can be rewritten in a more compact way as

\sum _{n=0}^{m}1_{\{N=n\}}c_{n}=\sum _{k=0}^{m}N_{k}(\Delta ^{k}c)_{0}.

(6)

Probabilistic versions edit

Consider arbitrary events $A 1, ..., A m$ in a probability space $\mathbb {P}$ and let $E$ denote the expectation operator. Then $N$ from (1) is the random number of these events which occur simultaneously. Using $N k$ from (2), define

S_{k}=\mathbb {E} [N_{k}]=\sum _{\scriptstyle J\subset \{1,\ldots ,m\} \atop \scriptstyle |J|=k}\mathbb {P} {\biggl (}\bigcap _{j\in J}A_{j}{\biggr )},\qquad k\in \{0,\ldots ,m\},

(7)

where the intersection over the empty index set is again defined as $Ω$ , hence $S 0 = 1$ . If the ring $R$ is also an algebra over the real or complex numbers, then taking the expectation of the coefficients in (4) and using the notation from (7),

\sum _{n=0}^{m}\mathbb {P} (N=n)x^{n}=\sum _{k=0}^{m}S_{k}(x-1)^{k}

(4')

in $R [x]$ . If $R$ is the field of real numbers, then this is the probability-generating function of the probability distribution of $N$ .

Similarly, (5) and (6) yield

\sum _{n=0}^{m}\mathbb {P} (N=n)E^{n}=\sum _{k=0}^{m}S_{k}\Delta ^{k}

(5')

and, for every sequence $c = (c 0, c 1, c 2, c 3, ..., c m, ...)$ ,

\sum _{n=0}^{m}\mathbb {P} (N=n)\,c_{n}=\sum _{k=0}^{m}S_{k}\,(\Delta ^{k}c)_{0}.

(6')

The quantity on the left-hand side of (6') is the expected value of $c N$ .

Remarks edit

In actuarial science, the name Schuette–Nesbitt formula refers to equation (6'), where $V$ denotes the set of real numbers.
The left-hand side of equation (5') is a convex combination of the powers of the shift operator $E$ , it can be seen as the expected value of random operator $E N$ . Accordingly, the left-hand side of equation (6') is the expected value of random component $c N$ . Note that both have a discrete probability distribution with finite support, hence expectations are just the well-defined finite sums.
The probabilistic version of the inclusion–exclusion principle can be derived from equation (6') by choosing the sequence $c = (0, 1, 1, ...)$ : the left-hand side reduces to the probability of the event ${N \geq 1}$ , which is the union of $A 1, ..., A m$ , and the right-hand side is $S 1 - S 2 + S 3 - ... - (-1) m S m$ , because $(Δ 0 c) 0 = 0$ and $(Δ k c) 0 = -(-1) k$ for $k \in {1, ..., m}$ .
Equations (5), (5'), (6) and (6') are also true when the shift operator and the difference operator are considered on a subspace like the $ℓ p$ spaces.
If desired, the formulae (5), (5'), (6) and (6') can be considered in finite dimensions, because only the first $m + 1$ components of the sequences matter. Hence, represent the linear shift operator $E$ and the linear difference operator $Δ$ as mappings of the $(m + 1)$ -dimensional Euclidean space into itself, given by the $(m + 1) \times (m + 1)$ -matrices

E={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &0\\0&\cdots &0&0&1\\0&\cdots &0&0&0\end{pmatrix}},\qquad \Delta ={\begin{pmatrix}-1&1&0&\cdots &0\\0&-1&1&\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &0\\0&\cdots &0&-1&1\\0&\cdots &0&0&-1\end{pmatrix}},

and let

I

denote the

(m + 1)

-dimensional identity matrix. Then (6) and (6') hold for every vector

c = (c 0, c 1, ..., c m) T

in

(m + 1)

-dimensional Euclidean space, where the exponent

T

in the definition of

c

denotes the transpose.

Equations (5) and (5') hold for an arbitrary linear operator $E$ as long as $Δ$ is the difference of $E$ and the identity operator $I$ .
The probabilistic versions (4'), (5') and (6') can be generalized to every finite measure space.

For textbook presentations of the probabilistic Schuette–Nesbitt formula (6') and their applications to actuarial science, cf. Gerber (1997). Chapter 8, or Bowers et al. (1997), Chapter 18 and the Appendix, pp. 577–578.

History edit

For independent events, the formula (6') appeared in a discussion of Robert P. White and T.N.E. Greville's paper by Donald R. Schuette and Cecil J. Nesbitt, see Schuette & Nesbitt (1959). In the two-page note Gerber (1979), Hans U. Gerber, called it Schuette–Nesbitt formula and generalized it to arbitrary events. Christian Buchta, see Buchta (1994), noticed the combinatorial nature of the formula and published the elementary combinatorial proof of (3).

Cecil J. Nesbitt, PhD, F.S.A., M.A.A.A., received his mathematical education at the University of Toronto and the Institute for Advanced Study in Princeton. He taught actuarial mathematics at the University of Michigan from 1938 to 1980. He served the Society of Actuaries from 1985 to 1987 as Vice-President for Research and Studies. Professor Nesbitt died in 2001. (Short CV taken from Bowers et al. (1997), page xv.)

Donald Richard Schuette was a PhD student of C. Nesbitt, he later became professor at the University of Wisconsin–Madison.

The probabilistic version of the Schuette–Nesbitt formula (6') generalizes much older formulae of Waring, which express the probability of the events ${N = n}$ and ${N \geq n}$ in terms of $S 1$ , $S 2$ , ..., $S m$ . More precisely, with $\textstyle {\binom {k}{n}}$ denoting the binomial coefficient,

\mathbb {P} (N=n)=\sum _{k=n}^{m}(-1)^{k-n}{\binom {k}{n}}S_{k},\qquad n\in \{0,\ldots ,m\},

(8)

and

\mathbb {P} (N\geq n)=\sum _{k=n}^{m}(-1)^{k-n}{\binom {k-1}{n-1}}S_{k},\qquad n\in \{1,\ldots ,m\},

(9)

see Feller (1968), Sections IV.3 and IV.5, respectively.

To see that these formulae are special cases of the probabilistic version of the Schuette–Nesbitt formula, note that by the binomial theorem

\Delta ^{k}=(E-I)^{k}=\sum _{j=0}^{k}{\binom {k}{j}}(-1)^{k-j}E^{j},\qquad k\in \mathbb {N} _{0}.

Applying this operator identity to the sequence $c = (0, ..., 0, 1, 0, 0, ...)$ with $n$ leading zeros and noting that $(E j c) 0 = 1$ if $j = n$ and $(E j c) 0 = 0$ otherwise, the formula (8) for ${N = n}$ follows from (6').

Applying the identity to $c = (0, ..., 0, 1, 1, 1, ...)$ with $n$ leading zeros and noting that $(E j c) 0 = 1$ if $j \geq n$ and $(E j c) 0 = 0$ otherwise, equation (6') implies that

\mathbb {P} (N\geq n)=\sum _{k=n}^{m}S_{k}\sum _{j=n}^{k}{\binom {k}{j}}(-1)^{k-j}.

Expanding $(1 - 1) k$ using the binomial theorem and using equation (11) of the formulas involving binomial coefficients, we obtain

\sum _{j=n}^{k}{\binom {k}{j}}(-1)^{k-j}=-\sum _{j=0}^{n-1}{\binom {k}{j}}(-1)^{k-j}=(-1)^{k-n}{\binom {k-1}{n-1}}.

Hence, we have the formula (9) for ${N \geq n}$ .

Applications edit

In actuarial science edit

Problem: Suppose there are $m$ persons aged $x 1, ..., x m$ with remaining random (but independent) lifetimes $T 1, ..., T m$ . Suppose the group signs a life insurance contract which pays them after $t$ years the amount $c n$ if exactly $n$ persons out of $m$ are still alive after $t$ years. How high is the expected payout of this insurance contract in $t$ years?

Solution: Let $A j$ denote the event that person $j$ survives $t$ years, which means that $A j = {T j > t}$ . In actuarial notation the probability of this event is denoted by $t p x j$ and can be taken from a life table. Use independence to calculate the probability of intersections. Calculate $S 1, ..., S m$ and use the probabilistic version of the Schuette–Nesbitt formula (6') to calculate the expected value of $c N$ .

In probability theory edit

Let $σ$ be a random permutation of the set ${1, ..., m}$ and let $A j$ denote the event that $j$ is a fixed point of $σ$ , meaning that $A j = {σ (j) = j}$ . When the numbers in $J$ , which is a subset of ${1, ..., m}$ , are fixed points, then there are $(m - | J |)!$ ways to permute the remaining $m - | J |$ numbers, hence

\mathbb {P} {\biggl (}\bigcap _{j\in J}A_{j}{\biggr )}={\frac {(m-|J|)!}{m!}}.

By the combinatorical interpretation of the binomial coefficient, there are $\textstyle {\binom {m}{k}}$ different choices of a subset $J$ of ${1, ..., m}$ with $k$ elements, hence (7) simplifies to

S_{k}={\binom {m}{k}}{\frac {(m-k)!}{m!}}={\frac {1}{k!}}.

Therefore, using (4'), the probability-generating function of the number $N$ of fixed points is given by

\mathbb {E} [x^{N}]=\sum _{k=0}^{m}{\frac {(x-1)^{k}}{k!}},\qquad x\in \mathbb {R} .

This is the partial sum of the infinite series giving the exponential function at $x - 1$ , which in turn is the probability-generating function of the Poisson distribution with parameter $1$ . Therefore, as $m$ tends to infinity, the distribution of $N$ converges to the Poisson distribution with parameter $1$ .

References edit

Bowers, Newton L.; Gerber, Hans U.; Hickman, James C.; Jones, Donald A.; Nesbitt, Cecil J. (1997), Actuarial Mathematics (2nd ed.), The Society of Actuaries, ISBN 0-938959-46-8, Zbl 0634.62107
Buchta, Christian (1994), "An elementary proof of the Schuette–Nesbitt formula", Mitteilungen der Schweiz. Vereinigung der Versicherungsmathematiker, 1994 (2): 219–220, Zbl 0825.62745
Feller, William (1968) [1950], An Introduction to Probability Theory and Its Applications, Wiley Series in Probability and Mathematical Statistics, vol. I (revised printing, 3rd ed.), New York, London, Sydney: John Wiley and Sons, ISBN 0-471-25708-7, Zbl 0155.23101
Gerber, Hans U. (1979), "A proof of the Schuette–Nesbitt formula for dependent events" (PDF), Actuarial Research Clearing House, 1: 9–10
Gerber, Hans U. (1997) [1986], Life Insurance Mathematics (3rd ed.), Berlin: Springer-Verlag, ISBN 3-540-62242-X, Zbl 0869.62072
Schuette, Donald R.; Nesbitt, Cecil J. (1959), "Discussion of the preceding paper by Robert P. White and T.N.E. Greville" (PDF), Transactions of Society of Actuaries, 11 (29AB): 97–99

External links edit

Cecil J. Nesbitt at the Mathematics Genealogy Project
Donald R. Schuette at the Mathematics Genealogy Project