5.3.1 Sampling: The Diverse Ways

Sampling from a population can be carried out in many different ways. Suppose that we have balls in an urn, and each ball carries a unique label along with it. Without loss of generality, we can label the balls 1 to . In this case we say that the balls are ordered. If the label of the balls carry no meaning, or are not available, that is, indistinguishable, we are dealing with sampling problems with unordered units.

5.3.1.1 Sampling with Replacement and with Ordering

Consider the situation where we draw units sequentially from units. Before each draw, the balls in the urn are shaken well so that any ordered ball has the same chance of being selected. At each stage after the draw, the label of the drawn unit is noted and the order of labeled units is duly recorded before placing it back in the urn. Thus, if denotes the label of the unit drawn on the occasion, we have an ordered - tuple , with taking a value between , . The fundamental counting theorem then gives the answer of doing this task in

5.1

distinct ways.

5.3.1.2 Sampling without Replacement and with Ordering

Suppose that the experiment remains the same as above, with a variation being that the drawn ball is not put back in the urn. That is, at the first draw we have units to choose from. At the second draw, we have units to choose from, at the third draw units, and so on. Thus, at the draw, we have units for drawing the unit. Thus, sampling with replacement from ordered units can be performed in distinct ways. Since we cannot draw more than units among , we have the constraint of . We have again applied the fundamental theorem of counting. Let us introduce a notation here of continued product: to denote . That is

5.2

In popular terms, this is the permutation of units sampled from a pool of units. An interesting case is the permutation of obtaining all the units. This experiment is about drawing all the units without replacement from the urn and is given by

To see the behavior of the number of ways we can possibly draw, let us look at the permutation of drawing 1 to 12 units.

> sapply(1:12,factorial)
[1]  1 2 6 24 120 720 5040  40320 362880
[10] 3628800  39916800 479001600

The sapply function ensures that the factorial function is applied on each integer 1 to12.

5.3.1.3 Sampling without Replacement and without Ordering

We now consider a sampling variation of the previous experiment. In this experiment we do not record the order of the occurrence of the sampling unit. Alternatively, we can think of this experiment as seeing the final result of sampling the desired number of units. We have seen that a sample of units can be obtained in different ways. Furthermore, the number of distinct ways of obtaining a sample of units from is given by the continued product . Thus, the number of ways of obtaining an unordered sample of units by sampling without replacement from units is . By multiplying the numerator and denominator by , we get the desired result

5.3

5.3.2 The Binomial Coefficients and the Pascals Triangle

The Pascal's triangle is a simplistic and useful triangle for obtaining the binomial coefficients. To begin with, consider the following relationship:

This relationship says that to obtain , we can obtain it as the sum of ways of selecting and objects from . Thus, we can move to higher levels using the quantities at one level below it. This leads to the famous Pascal's triangle. A short program is given below to obtain the triangle.

> pascal <- function(n){
+ if(n<=1) pasc=1
+ if(n==2) pasc=c(1,1)
+ if(n>2){
+ pasc <- c(1,1)
+ j <- 2
+ while(j<n){
+     j <- j+1
+     pasc=c(1,as.numeric(na.omit(filter(pasc,rep(1,2)))),1)
+ }
+ }
+ return(pasc)
+ }
> sapply(1:7, pascal)
[[1]]
[1] 1
[[2]]
[1] 1 1
[[3]]
[1] 1 2 1
[[4]]
[1] 1 3 3 1
[[5]]
[1] 1 4 6 4 1
[[6]]
[1]  1  5 10 10  5  1
[[7]]
[1]  1  6 15 20 15  6  1

With the basics of combinatorics with us, we are now equipped to develop R solutions for some interesting problems in probability.

5.3.3 Some Problems Based on Combinatorics

Feller (1968) has a very deep influence on almost all the Probabilists. Diaconis and Holmes (2002) considered some problems from Feller's Volume 1 in the Bayesian paradigm. Particularly, we consider two of those three problems here: (i) The Birthday Problem, and (ii) The Banach Match Box Problem. The problems selected here serve the point that probability on some occasions can be very counter-intuitive. A survey of some of these problems may also be found in Mosteller (1962).

The next R program gives us the birthday probabilities where we compute the probability of obtaining the same birthday if there are 2, 5, 10, 20, …, 50, people in a classroom.

> k <- c(2,5,10,20,30,40,50)
> probdiff <- c(); probat2same <- c()
> for(i in 1:length(k))  {
+   kk <- k[i]
+   probdiff[i] <- prod(365:(365-kk+1))/(365^{k}k)
+   probat2same[i] <- 1- prod(365:(365-kk+1))/(365^{k}k)
+                         }
> plot(k,probat2same,xlab="Number of Students in Classroom",
+      ylab="Birthday Probability",col="green","l")
> lines(k,probdiff,col="red","l")
> legend(10,1,"Birthdays are not same",box.lty=NULL)
> legend(30,.7,"Birthdays are same",,box.lty=NULL)
> title("A: The Birthday Problem")

The R numeric vectors probdiff and probat2same respectively compute and . The code prod(365:(365-kk + 1))/(365^kk)!birthday probability"?> gives , and by using it we easily obtain probat2same. The plot functions, lines, legend, and title are simple to follow.

	ordered = True	ordered = False
replace = True
replace = False

The birthday probabilities are summarized in Table 5.2. It can be seen from the table that we need to have just 50 people in a classroom to be almost sure of finding a pair of birthday mates. Part A of Figure 5.2 gives the visual display of the table probabilities. The meeting point of the complementary curves at 0.5 gives k=23 as claimed in Williams (2001).□

We will now digress a little here and have a close look at the failure of the definition of probability discussed thus far. It seems to our intuition that if , the probability for any subset must exist. That is, any subset must have a well defined measure. Ross and Pekoz (2007) consider a very elegant example of a subset for which the measure cannot be defined in any rational way. Suppose that we begin at the top of a unit circle and take a step of one unit radian in a counter-clockwise direction. If required, we may perform more than one loop. The task is then computation of the probability of returning to the point from which we started our journey. Suppose that it takes steps and loops to return to the top of the circle. This implies that . As is an irrational number, it cannot be expressed as the ratio of two integers . Thus, the probability of returning to the start point cannot be measured.

This and some other limitations of the definition of probability considered up to now are overcome using the Kolmogorov's definition of probability, which is based on Measure Theory. We will leave out the details of these important discussions!

5.4.1 The Prerequisites

Let us consider a class of sets of , say . The sequence is said to be monotone increasing if for each . The sequence is said to be monotone decreasing if for each . We introduce two sequences infimum and supremum as below:

5.5

The symbol is used to convey that the quantity on the left-hand side is by definition equal to that on the right-hand side. It is easier to see that the sequence is monotone increasing sequence, whereas the sequence is a monotone decreasing sequence. We further define sequences and as follows:

5.6

It is also common to refer to the couplet as a field. It may be easily proved that a field is also closed under finite union.

In plain words, the minimal field is the least collection of sets containing , which is a field.

Fields need a generalization and especially in the case of countably infinite or continuous set .

The couplet is sometimes called the -field.

As earlier, we can define the minimal -field as an extension of the minimal field. There is an important class of -field, which will be defined now.

It may be verified that the Borel -field consists of the intervals, for all , of the following types:

The definition of may be extended to and the reader may refer to Chung (2001). Starting with the sample space , a general class of sets has been defined. Next a formal definition of a measure is required.

Let us now look at two important types of measures.

We are now equipped with the necessary tools for a proper construction of a probability measure.

5.4.2 The Kolmogorov Definition

Here, the finiteness refers to the collection of sets in and additiveness refers to disjoint collection of events. Any set is called an event or (more precisely) a measurable event. Next, we list some properties of the finitely additive probability measure:

• .
• .
• If , then .
• .
• The General Additive Rule: , and hence .
• For an arbitrary set and a collection of mutually exclusive and exhaustive sets :

We now extend the finitely additive probability measure to the countably infinite case.

5.7.1 The Definition

Sample events on their own are not always of interest, as we may only be interested in general events. For instance, if 100 coins are thrown, we may not be interested in the probabilities of the event itself, but we may question the number of heads in the range of 10 to 40, or > 80. Thus, we need to consider functions of the events which help to answer generic questions. This will lead us to the concept of random variable.

In plain words, it is required that for any Borel set , the inverse image must belong to :

A random variable will be simply abbreviated as RV. A commonly accepted convention is to denote the random variables by capital letters , , , etc., and the observed values by small letters , , , etc. respectively. Random variables are identified to be of three types: (i) simple random variable, (ii) elementary random variable, and (iii) extended random variable. A random variable is said to be simple if there exists a finite partition of in , finite, implying , such that

5.10

where if and 0 otherwise. The random variable is said to be elementary if for a countably infinite partition of in

5.11

Finally, the random variable is said to be an extended random variable if . An extended RV is often split into a positive part and a negative part defined by

5.12

It can be easily seen that .

We next consider some important properties of random variables.

Properties of Random Variables

• Borel function of a random variable is also a random variable.
• If is an RV, then is also a RV for .
• Let and be two RVs in a probability space . Then and are also RVs.
• Consider an independent sequence of RVs . Define, for all ,
  

  Then , , , and are all RVs.

• If converges as for every , then is also an RV.

An RV is better understood through important summaries such as mean and variance. We next define expectation of RV, which further helps in obtaining these summaries.

5.7.2 Expectation of Random Variables

As an introductory, the expectation of a discrete RV is defined by , and for a continuous RV, by . In light of the three types of RV discussed earlier, we need to now define the expectation of an RV for simple, elementary, and extended RVs defined in a probability space . For the moment, we will assume that the extended RVs are non-negative RVs.

The expectations of simple RV and elementary RV as defined respectively in Equations 5.10 and 5.11 are given by

5.13

5.14

The expectation of a non-negative random variable is defined by

5.15

It may be noted that the limit can be too. The expectation of an arbitrary (extended) RV, as given in Equation 5.12, is defined by

5.16

provided that at least one of and is finite. If both and are infinite, the expectation of the RV is not defined.

Let us now consider some properties of expectations of RVs.

Properties of Expectation of Random Variables

• If and are two partitions of a simple RV such that
  

  then

  
• If is a non-negative and simple RV, then . This property continues to hold for non-negative RVs too.
• If and are two non-negative (simple or otherwise) RVs, and , then . This property is also known as the linearity of expectations.

The third counter-intuitive problem from Diaconis and Holmes (2002) will be discussed next.

Higher-order expectations are of interest for many RVs.

The forthcoming section will consider three important functions related to an RV.

5.9.1 The Markov Inequality

5.9.2 The Jensen's Inequality

The Jensen's inequality is a very useful technique, especially when we deal with the theory of the subject.

5.9.3 The Chebyshev Inequality

Consider a random variable with mean and variance . The Chebyshev's inequality states that

5.18

This inequality has a very useful interpretation: “Not more than of the distribution's values can be more than standard deviations away from the mean.” Note that the inequality does not make any assumptions about the probability distribution of .

A one-tailed version of the Chebyshev's inequality is

The forthcoming section will deal with various convergence concepts of RVs.

5.10.1 Convergence in Distributions

Consider a sequence of probability spaces , and let the random variable sequence be such that for each , is - measurable and . Furthermore, let be the cumulative distribution function associated with . Also, let be another probability space and we consider an -measurable random variable , whose associated cumulative probability distribution function is . Then we say that the sequence converges in distribution to if as

5.19

The standard notation for convergence in distribution is or . Sometimes the convergence in the distribution is also denoted by .

We next state an important result, see page 259 of Rohatgi and Saleh (2000).

The above theorem is now illustrated through an example.

5.10.2 Convergence in Probability

Consider a probability space and let be a sequence of random variables defined in this space. We say that the sequence converges in probability to a random variable if for each

5.21

5.22

Symbolically, we denote this as .

Convergence in probability implies convergence in distribution. However, the converse is not true.

5.10.3 Convergence in Mean

We begin with a probability space and let be a sequence of random variables defined in it. We say that the sequence converges in mean to an RV if and as

5.23

5.10.4 Almost Sure Convergence

Let be a sequence of random variables on the probability space . The sequence is said to converge almost surely to a RV if

The next result is very useful in establishing almost sure convergence. Almost sure convergence is denoted by

5.11.1 The Weak Law of Large Numbers

Let be a sequence of random variables and define . The sequence is said to obey the weak law of large numbers, WLLN, with respect to a sequence of constants , , if there exists a sequence of constants which satisfies

The sequence is called centering sequence and the sequence is called norming sequence. We state below a result which helps to determine whether the WLLN holds true for the sequence under consideration.

5.12.1 The de Moivre-Laplace Central Limit Theorem

A complete de-mystification of the de Moivre-Laplace CLT appears in Ramasubramaniam (1997). Suppose that . Let . Define

5.24

We will begin with a statement of this result.

Typically, CLT is demonstrated using a simulation study. Though that approach is not wrong, we would like to make a few pointers here. In a simulation study we actually use the realized values of the RVs as in . However, the CLT is truly about the convergence of RVs as in . The principal point is that we cannot pretend that is the same as . Thus, our illustration, at least in this section, will not resort to a simulation study.

We give an animated version of the convergence in the following program.

> n <- 10:1000
> p <- 0.4
> for(i in 1:length(n)){
+     plot(0:n[i],dbinom(0:n[i],p=0.4,n[i]),
+     "h",xaxt="n",yaxt="n",xlab="x",ylab="PDF")
+     title("The de Moivre's Laplace Central Limit Theorem")
+     curve(dnorm(x,mean=n[i]*0.4,sd=sqrt(n[i]*0.4*0.6)),
+     from=0,to=n[i],add=TRUE)
+ }

Change the values of for different levels and enjoy the convergence. Consider the general iid case next.

5.12.2 CLT for iid Case

Let be iid random variables with finite first and second moments, that is, . Define . Let and denote the mean and variance for . The general CLT for the iid case is stated below.

Two equivalent forms of the CLT statement are that as

This statement appears very generic and we consider an illustration with varied distributions.

The more general case of a sequence of independent RVs is considered next.

5.12.3 The Lindeberg-Feller CLT

The previous theorem along with Equation 5.26 handles a sequence of iid RVs. An extension of this result for the more generic case of a sequence of independent RVs is then required. The Lindeberg-Feller theorem gives a set of necessary and sufficient conditions which help establish CLT for a sequence of independent RVs. A few notations are in order towards this end.

Let be a sequence of RVs, and let their respective probability spaces be defined by the sequence . In the case of the iid sequence, we have . Assume that , and . Define , , and . It may be noted by the reader here that does not correspond to the realized value of the sum . The next theorem is the famous result sought in this section.

From a programming perspective, it is better to first consider the simpler case of a sequence of iid RVs for verifying the Feller condition 5.27 and also the Lindeberg condition 5.28. It will become more clear why the simpler case has been considered first.

A stronger, but more restrictive, condition can be imposed, which can be used for examining the CLT for a sequence of independent RVs.

5.12.4 The Liapounov CLT

The Liapounov's CLT is given in the next theorem.

Since the Liapounov's condition 5.29 requires a higher-order moment condition, it is more difficult in general to establish whether it holds for a given sequence of RVs. However, it is sometimes very useful for a sequence of discrete RVs.

5.13.1 Intuitive, Elementary, and First Course Source

Chung and AitSahlia (2004) is an appealing beginner's starting point. Chung and AitSahlia (2004) is a fourth edition enhancement of Chung (1979), which has been an excellent introduction since its first print. A higher secondary school introduction to probability has been written by two eminent Russian probabilists Gnedenko and Khinchin (1964). Ash (1969), Chandra and Chatterjee (2001), Gnedenko (1978), Durrett (2009), and Ross (2010) are some of the competitive first course texts on probability theory.

As far as intuition is concerned, one of the unrivalled works in the literature ever is the two volumes of Feller (1968 and 1971). A testimony and tribute to this fact is that almost any decent work on probability theory will cite Feller.

5.13.2 The Classics and Second Course Source

Feller's (1968 and 1971) two volumes are intuitive, classic, advanced courses, and also almost everything else too. The measure theoretic approach was first detailed in Kolmogorov (1933). This short book served as a cornerstone for the way probability would be written from that point onward. It is generally agreed that Loéve (1955) has been the first comprehensive take on the measure theoretic approach to probability and the last edition of his work appeared in two volumes, Loeve (1977). Chung (2000) has been another famous probabilitist researcher who has also written some of the best probability books.

Ash and Doléans-Dade (2000), Shiryaev (1995), Chow and Teicher (1995), Athreya and Lahiri (2005), Durrett (2010), and Breiman (1962, 1992), among others, are some of the excellent measure theoretic approaches to probability. Parthasarathy (1978) and Billingsley (1995) have also stood the test of time and are still a favorite of many probability readers. In most of the books mentioned in this paragraph, the first editions have appeared a couple of decades earlier than their most recent editions that we have listed here.

Rosenthall (2006) and Kallenberg (2002) are two of the modern texts on measure theoretic probability. In the Indian subcontinent, students and teachers have benefited from Bhat (2012) and Basu (1998) and both the books make a great read.

5.13.3 The Problem Books

If the intimidated people could have their way, we are sure that most of the authors mentioned in this subsection would be facing capital punishment! After all, the offense of these authors is not any less. Mosteller (1962), Grimmet and Stirzaker (2001), Cacoullus (1989), Schwarz (2007), Capiński and Zastawniak (2001), Nahin (2008), Sveshnikov (1968), and Chaumont and Yor (2003) all are guilty of the same offense. They batter the readers with a never-ending sequence of problems and thereby give a proof that is the way to understand infinity! To be fair to these authors, some of them have been really nice! They clearly mention that their book has only 40, 50, or 100 problems in contrast to some of them, who blatantly emphasize that the reader must solve 1000 problems!

5.13.4 Other Useful Sources

Johnson and Kotz (1969–73) have written a four-volume book on the distributions that arise in probability and statistics. An update to this work has appeared in the late 1990s by Johnson and Kotz and co-workers. DasGupta (2011) and DasGupta (2010) cover a lot of topics and modern advancements. Dworsky (2008) offers a different view and makes a smart read. Stoyanov (1997) is an entirely different type of book, with its focus mainly on counter examples.

5.13.5 R for Probability

Prof Jay Kerns' open source book, Kerns (2010), has been an influence on the first few sections of this chapter. Horgan (2008) and Baclawski (2008) are two introductory books who demonstrate a lot of probability aspect that can be understood through R.