A large number of the problems which arise in applications of probability theory may be regarded as special cases of the following general problem, which we call the problem of addition of independent random variables; find, either exactly or approximately, the probability law of a random variable that arises as the sum of \(n\) independent random variables \(X_{1}, X_{2}, \ldots\) , \(X_{n}\) , whose joint probability law is known . The fundamental role played by this problem in probability theory is best described by a quotation from an article by Harald Cramér, “Problems in Probability Theory”, Annals of Mathematical Statistics , Volume 18 (1947), p. 169.

During the early development of the theory of probability, the majority of problems considered were connected with gambling. The gain of a player in a certain game may be regarded as a random variable, and his total gain in a sequence of repetitions of the game is the sum of a number of independent variables, each of which represents the gain in a single performance of the game. Accordingly, a great amount of work was devoted to the study of the probability distributions of such sums. A little later, problems of a similar type appeared in connection with the theory of errors of observation, when the total error was considered as the sum of a certain number of partial errors due to mutually independent causes. At first, only particular cases were considered; but gradually general types of problems began to arise, and in the classical work of Laplace several results are given concerning the general problem to study the distribution of a sum

\[S_{n}=X_{1}+X_{2}+\cdots+X_{n}\] 

of independent variables, when the distributions of the \(X_{j}\) are given. This problem may be regarded as the very starting point of a large number of those investigations by which the modern Theory of Probability was created. The efforts to prove certain statements of Laplace, and to extend his results further in various directions, have largely contributed to the introduction of rigorous foundations of the subject, and to the development of the analytical methods.

In this chapter we discuss the methods and notions by which a precise formulation and solution is given to the problem of addition of independent random variables. To begin with, in this section we discuss the two most important ways in which this problem can arise, namely in the analysis of sample averages and in the analysis of random walks .

Sample Averages . We have defined a sample of size \(n\) of a random variable \(X\) as a set of \(n\) jointly distributed random variables \(X_{1}, X_{2}, \ldots, X_{n}\) , whose individual probability laws coincide, for \(k=1,2, \ldots, n\) , with the probability law of \(X\) ; in particular, the distribution function \(F_{X_{k}}(\cdot)\) of \(X_{k}\) coincides with the distribution function \(F_{X}(\cdot)\) of \(X\) . We have defined the sample as a random sample if the random variables \(X_{1}, X_{2}, \ldots, X_{n}\) are independent.

Given a sample \(X_{1}, X_{2}, \ldots, X_{n}\) of size \(n\) of the random variable \(X\) and any Borel function \(g(\cdot)\) of a real variable, we define the sample average of \(g(\cdot)\) , denoted by \(M_{n}[g(x)]\) , as the arithmetic mean of the values \(g\left(X_{1}\right), g\left(X_{2}\right)\) , \(\ldots, g\left(X_{n}\right)\) of the function at the members of the sample; in symbols, \[M_{n}[g(x)]=\frac{1}{n} \sum_{k=1}^{n} g\left(X_{k}\right). \tag{1.1}\] 

Of special importance are the sample mean \(m_{n}\) , defined by \[m_{n}=M_{n}[x]=\frac{1}{n} \sum_{k=1}^{n} X_{k}, \tag{1.2}\] and the sample variance \(S_{n}^{2}\) , defined by \begin{align} S_{n}^{2} & =M_{n}\left[\left(x-m_{n}\right)^{2}\right]=M_{n}\left[x^{2}\right]-M_{n}^{2}[x] \tag{1.3}\\[5mm] & =\frac{1}{n} \sum_{k=1}^{n}\left(X_{k}-m_{n}\right)^{2}=\frac{1}{n} \sum_{k=1}^{n} X_{k}^{2}-\left(\frac{1}{n} \sum_{k=1}^{n} X_{k}\right)^{2}. \end{align} 

For a given function \(g(\cdot)\) the sample average \(M_{n}[g(x)]\) is a random variable , for it is a function of the random variables \(X_{1}, X_{2}, \ldots, X_{n}\) . The value of \(M_{n}[g(x)]\) will, in general, be different when it is computed on the basis of two different samples of size \(n\) . The sample average \(M_{n}[g(x)]\) , like any other random variable, has a mean \(E\left[M_{n}[g(x)]\right]\) , a variance \(\operatorname{Var}\left[M_{n}[g(x)]\right]\) , a distribution function \(F_{M_{n}[g(x)]}(\cdot)\) , a moment-generating function \(\psi_{M_{n}[g(x)]}(\cdot)\) , and, depending on whether it is a continuous or a discrete random variable, a probability density function \(f_{M_{n}[g(x)]}(\cdot)\) or a probability mass function \(p_{M_{n}[g(x)]}(\cdot)\) . Our aim in this chapter and the next is to develop techniques for computing these quantities, both exactly and approximately, and especially to study their behavior for large sample sizes. The reader who goes on to the study of mathematical statistics will find that these techniques provide the framework for many of the concepts of statistics.

To study sample averages \(M_{n}[g(x)]\) with respect to a random sample, it suffices to consider the sum \(\sum_{k=1}^{n} Y_{k}\) of independent random variables \(Y_{1}, \ldots, Y_{n}\) , since the random variables \(Y_{1}=g\left(X_{1}\right), \ldots, Y_{n}=g\left(X_{n}\right)\) are independent if the random variables \(X_{1}, \ldots, X_{n}\) are. Thus it is seen that the study of sample averages has been reduced to the study of sums of independent random variables .

Random Walk. Consider a particle that at a certain time is located at the point 0 on a certain straight line. Suppose that it then suffers displacements along the straight line in the form of a series of steps, denoted by \(X_{1}, X_{2}, \ldots, X_{n}\) , in which, for any integer \(k, X_{k}\) represents the displacement suffered by the particle at the \(k\) th step. The size \(X_{k}\) of the \(k\) th step is assumed to be a random variable with a known probability law. The particle can thus be imagined as executing a random walk along the line, its position (denoted by \(S_{n}\) ) after \(n\) steps being the sum of the \(n\) steps \(X_{1}, X_{2}, \ldots, X_{n}\) ; in symbols, \(S_{n}=X_{1}+X_{2}+\cdots+X_{n}\) . Clearly, \(S_{n}\) is a random variable, and the problem of finding the probability law of \(S_{n}\) naturally arises; in other words, one wishes to know, for any integer \(n\) and any interval \(a\) to \(b\) , the probability \(P\left[a \leq S_{n} \leq b\right]\) that after \(n\) steps the particle will lie between \(a\) and \(b\) , inclusive.

The problem of random walks can be generalized to two or more dimensions. Suppose that the particle at each stage suffers a displacement in an \((x, y)\) plane, and let \(X_{k}\) and \(Y_{k}\) denote, respectively, the change in the \(x\) - and \(y\) -coordinates of the particle at the \(k\) th step. The position of the particle after \(n\) steps is given by the random 2-tuple \(\left(S_{n}, T_{n}\right)\) , in which \(S_{n}=X_{1}+X_{2}+\cdots+X_{n}\) and \(T_{n}=Y_{1}+Y_{2}+\cdots+Y_{n}\) . We now have the problem of determining the joint probability law of the random variables \(S_{n}\) and \(T_{n}\) .

The problem of random walks occurs in many branches of physics, especially in its 2-dimensional form. The eminent mathematical statistician, Karl Pearson, was the first to formulate explicitly the problem of the 2-dimensional random walk. After Pearson had formulated this problem in 1905, the renowned physicist, Lord Rayleigh, pointed out that the problem of random walks was formally “the same as that of the composition of \(n\) isoperiodic vibrations of unit amplitude and of phases distributed at random”, which he had considered as early as 1880 (for this quotation and a history of the problem of random walks, see p. 87 of S. Chandrasekhar, “Stochastic Problems in Physics and Astronomy”, Reviews of Modern Physics , Volume 15 (1943), pp. 1–89). Almost all scattering problems in physics are instances of the problem of random walks.

In the study of sums of independent random variables a basic role is played by the notion of the characteristic function of a random variable. This notion is introduced in section 2.