Probability, Mathematical Statistics, and Stochastic Processes (Siegrist)

This text is devoted to probability, mathematical statistics, and stochastic processes, and is intended for teachers and students of these subjects. The site consists of an integrated set of components that includes expository text, interactive web apps, data sets, biographical sketches, and an object library.

In this chapter we review several mathematical topics that form the foundation of probability and mathematical statistics. These include the algebra of sets and functions, general relations with special emphasis on equivalence relations and partial orders, counting measure, and some basic combinatorial structures such as permuations and combinations. We also discuss some advanced topics from topology and measure theory. You may wish to review the topics in this chapter as the need arises.

Set theory is the foundation of probability and statistics, as it is for almost every branch of mathematics.

Sets and subsets

In this text, sets and their elements are primitive, self-evident concepts, an approach that is sometimes referred to as naive set theory.

Functions play a central role in probability and statistics, as they do in every other branch of mathematics. For the most part, the proofs in this section are straightforward, so be sure to try them yourself before reading the ones in the text.

Definitions and Properties

Basic Definitions

We start with the formal, technical definition of a function. It’s not very intuitive, but has the advantage that it only requires set theory.

Counting measure plays a fundamental role in discrete probability structures, and particularly those that involve sampling from a finite set. The set is typically very large, hence efficient counting methods are essential. The first combinatorial problem is attributed to the Greek mathematician Xenocrates.

In many cases, a set of objects can be counted by establishing a one-to-one correspondence between the given set and some other set. Naturally, the two sets have the same number of elements, but for various reasons, the second set may be easier to count.

Inequalities

Our next disucssion concerns two inequalities that are useful for obtaining bounds on the number of elements in a set. The first is Boole’s inequality (named after George Boole) which gives an upper bound on the cardinality of a union.

The key to a successful application of the multiplication rule to a counting problem is the clear formulation of an algorithm that generates the objects being counted, so that each object is generated once and only once. That is, we must neither over count nor under count. It’s also important to notice that the set of choices available at step may well depend on the previous steps; the assumption is only that the number of choices available does not depend on the previous steps.