Statistical Inference/Probability Theory: Difference between revisions
From Wiki**3
< Statistical Inference
No edit summary |
|||
| (29 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
{{TOCright}} | {{TOCright}} | ||
= Set Theory = | |||
== Sample Space == | |||
The set, ''S'', of all possible outcomes of a particular experiment is called the ''sample space'' for the experiment. | The set, ''S'', of all possible outcomes of a particular experiment is called the ''sample space'' for the experiment. [Definition 1.1.1] | ||
== Event == | |||
An ''event'' is any collection of possible outcomes of an experiment, that is, any subset of ''S'' (including ''S'' itself). | An ''event'' is any collection of possible outcomes of an experiment, that is, any subset of ''S'' (including ''S'' itself). [Definition 1.1.2] | ||
Let ''A'' be an event, a subset of ''S''. We say the event ''A'' occurs if the outcome of the experiment is in the set ''A''. When speaking of probabilities, we generally speak of the probability of an event, rather than a set. But we may use the terms interchangeably. | |||
=== | === Base relationships === | ||
We first need to define formally the following two relationships, which allow us to order and equate sets: | |||
'''Containment:''' <math>A \subset B \Leftrightarrow x \in A \Rightarrow x \in B</math> | |||
= | '''Equality:''' <math>A = B \Leftrightarrow A \subset B \land B \subset A</math> | ||
== | === Elementary operations === | ||
Given any two events (or sets) A and B , we have the following elementary set operations: | |||
'''Union:''' The union of A and B, written <math>A \cup B</math>, is the set of elements that belong to either A or B or both: | |||
= | <math>A \cup B = \{ x : x \in A \lor x \in B \}</math> | ||
== Density and Mass Functions | '''Intersection:''' The intersection of A and B, written <math>A \cap B</math>, is the set of elements that belong to both A and B: | ||
<math>A \cap B = \{ x : x \in A \land x \in B \}</math> | |||
'''Complementation:''' The complement of A, written <math>\overline{A}</math>, is the set of all elements that are not in A: | |||
<math>\overline{A} = \{ x : x \notin A \}</math> | |||
== Event operations == | |||
The elementary set operations can be combined: for any three events, A, B, and C, defined on a sample space S, the following relationships hold [Theorem 1.1.4]. | |||
=== Commutativity === | |||
* <math>A \cup B = B \cup A</math> | |||
* <math>A \cap B = B \cap A</math> | |||
=== Associativity === | |||
* <math>A \cup (B \cup C) = (A \cup B) \cup C</math> | |||
* <math>A \cap (B \cap C) = (A \cap B) \cap C</math> | |||
=== Distributive Laws === | |||
* <math>A \cap (B \cup C) = (A \cap B) \cup (A \cap C)</math> | |||
* <math>A \cup (B \cap C) = (A \cup B) \cap (A \cup C)</math> | |||
=== DeMorgan Laws === | |||
* <math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math> | |||
* <math>\overline{A \cap B} = \overline{A} \cup \overline{B}</math> | |||
== Disjoint events == | |||
Two events A and B are disjoint (or mutually exclusive) [Definition 1.1.5] if <math>A \cap B = \emptyset</math>. | |||
The events A1, A2, ... are pairwise disjoint (or mutually exclusive) if <math>A_i \cap A_j = \emptyset, \forall_{i\ne j}</math>. | |||
Disjoint sets are sets with no points in common. If we draw a Venn diagram for two disjoint sets, the sets do not overlap. The collection <math>A_i = [i, i + 1), i = 0,1,2, \dots</math> consists of pairwise disjoint sets. Note further that <math>\cup^\infty_{i=0} A_i = [0, \infty)</math>. | |||
== Event space partitions == | |||
If A1, A2,... are pairwise disjoint and <math>\cup^\infty_{i=0} A_i = S</math>, then the collection A1, A2, . . . forms a partition of S. [Definition 1.1.6] | |||
The sets <math>A_i = [i, i + 1)</math> form a partition of <math>[0, \infty)</math>. In general, partitions are very useful, allowing us to divide the sample space into small, non-overlapping pieces. | |||
= Basics of Probability Theory = | |||
== Axiomatic foundations == | |||
For each event A in the sample space S we want to associate with A a number between zero and one that will be called the probability of A, denoted by P(A). | |||
=== Sigma Algebra === | |||
A collection of subsets of S is called a sigma algebra (or Borel field) [Definition 1.2.1], denoted by <math>\cal{B}</math>, if it satisfies the following three properties: | |||
* (a) <math>\emptyset \in \cal{B}</math> (the empty set is an element of <math>\cal{B}</math>). | |||
* (b) if <math>A \in \cal{B}</math>, then <math>\overline{A} \in \cal{B}</math> (<math>\cal{B}</math> is closed under complementation). | |||
* (c) if <math>A_1, A_2, \dots \in \cal{B}</math>, then <math>\cup^\infty_{i=1} A_i \in \cal{B}</math> (<math>\cal{B}</math> is closed under countable unions). | |||
The empty set <math>\emptyset</math> is a subset of any set. Thus, <math>\emptyset \subset S</math>. Property (a) states that this subset is always in a sigma algebra. Since <math>S = \overline{\emptyset}</math>, properties (a) and (b) imply that S is always in <math>\cal{B}</math> also. In addition, from DeMorganªs Laws it follows that <math>\cal{B}</math> is closed under countable intersections. If <math>A_1, A_2, \dots \in \cal{B}</math>, then <math>\overline{A_1}, \overline{A_2}, \dots \in \cal{B}</math> by property (b), and therefore <math>\cup^\infty_{i=1} \overline{A_i} \in \cal{B}</math> . However, using DeMorgan's Law, we | |||
have <math>\overline{\cup^\infty_{i=1} \overline{A_i}} = \cap^\infty_{i=1} A_i</math>. Thus, again by property (b), <math>\cap^\infty_{i=1} A_i \in \cal{B}</math>. | |||
Associated with sample space S we can have many different sigma algebras. For example, the collection of the two sets <math>\{\emptyset, S\}</math> is a sigma algebra, usually called the trivial sigma algebra. The only sigma algebra we will be concerned with is the smallest one that contains all of the open sets in a given sample space S . | |||
=== Probability Function === | |||
Given a sample space S and an associated sigma algebra <math>\cal{B}</math>, a probability function [Definition 1.2.4] is a function P with domain <math>\cal{B}</math> that satisfies | |||
* 1. <math>P(A) \geq 0, \forall_{A \in \cal{B}}</math>. | |||
* 2. <math>P(S) = 1</math>. | |||
* 3. If <math>A_1, A_2, \dots \in \cal{B}</math> are pairwise disjoint, then <math>P(\cup^\infty_{i=1} A_i)=\Sigma^\infty_{i=1} P(A_i)</math>. [Axiom of Countable Additivity] | |||
These three properties are usually referred to as the Axioms of Probability (or the Kolmogorov Axioms, after A. Kolmogorov, one of the fathers of probability theory). Any function P that satisfies the Axioms of Probability is called a probability function. The axiomatic definition makes no attempt to tell what particular function P to choose; it merely requires P to satisfy the axioms. For any sample space many different probability functions can be defined. Which one(s) reflects what is likely to be observed in a particular experiment is still to be discussed. | |||
We need general methods of defining probability functions that we know will always satisfy Kolmogorov's Axioms. We do not want to have to check the Axioms for each new probability function. The following gives a common method of defining a legitimate probability function. | |||
=== Defining Probability Functions === | |||
Let <math>S = \{s_1, \dots, s_n\}</math> be a finite set. Let <math>\cal{B}</math> be any sigma algebra of subsets of S. Let <math>p_1, \dots, p_n</math> be nonnegative numbers that sum to 1. For any <math>A \in \cal{B}</math>, define <math>P(A) = \Sigma_{\{i:s_i\in A\}}p_i</math> (The sum over an empty set is defined to be 0.) Then P is a probability function on <math>\cal{B}</math>. This remains true if <math>S = \{s_1, s_2, \dots\}</math> is a countable set [Theorem 1.2.6]. | |||
The physical reality of the experiment might dictate the probability assígnment. | |||
== The Calculus of Probabilities == | |||
=== Properties of the probability function applied to a single event === | |||
If P is a. probability function and A is any set in <math>\cal{B}</math>, then [Theorem 1.2.8] | |||
* (a) <math>P(\emptyset) = 0</math>, where <math>\emptyset</math> is the empty set; | |||
* (b) <math>P(A) \le 1</math>; | |||
* (c) <math>P(\overline{A}) = 1 - P(A)</math>. | |||
=== Properties of the probability function applied to any set pairs === | |||
If P is a probability function and A and B are any sets in <math>\cal{B}</math>, then [Theorem 1.2.9] | |||
* (a) <math>P(B \cap \overline{A}) = P(B) - P(A \cap B)</math>; | |||
* (b) <math>P(A \cup B) = P(A) + P(B) - P(A \cap B)</math>; | |||
* (c) If <math>A \subset B</math>, then <math>P(A) \le P(B)</math>. | |||
=== Bonferroni's Inequality === | |||
Formula (b) of Theorem 1.2.9 gives a useful inequality for the probability of an intersection. Since <math>P(A \cup B) \le 1</math>, we have, after some rearranging, <math>P(A \cap B) \ge P(A) + P(B) - 1</math>. | |||
This inequality is a special case of what is known as Bonferroni's Inequality. Bonferroni's Inequality allows us to bound the probability of a simultaneous event (the intersectíon) in terms of the probabilities of the individual events. | |||
=== Properties of the probability function applied to collections of sets === | |||
If P is a probability function, then [Theorem 1.2.11] | |||
* (a) <math>P(A) = \Sigma^\infty_{i=1} P(A \cap C_i)</math>, for any partition <math>C_1, C_2, \dots</math>; | |||
* (b) <math>P(\cup^\infty_{i=1} A_i) \le \Sigma^\infty_{i=1} P(A_i)</math>, for any sets <math>A_1, A_2, \dots</math> (Boole's Inequality) | |||
There is a similarity between Boole's Inequality and Bonferroni's Inequality. In fact, they are essentially the same thing. We could have used Boole's Inequality to derive that <math>P(A \cap B) \ge P(A) + P(B) - 1</math> (the special case of Bonferroni's Inequality, presented above). If we apply Boole*s Inequality to <math>\overline{A}</math>, we have <math>P(\cup^n_{i=1} \overline{A_i}) \le \Sigma^n_{i=1} P(\overline{A_i})</math> and using the facts that <math>\cup\overline{A_i} = \overline{\cap A_i}</math> and <math>P(\overline{A_i}) = 1 - P(A_i)</math>, we obtain <math>1 - P(\cap^n_{i=1} A_i) \le n - \Sigma^n_{i=1} P(A_i)</math> | |||
This becomes, on rearranging terms, <math>P(\cap^n_{i=1} A_i) \ge \Sigma^n_{i=1} P(A_i) - (n -1)</math>, which is a more general version of the Bonferroni Inequality presented before. | |||
== Counting == | |||
Most often, methods of counting are used in order to construct probability assignments on finite sample spaces, although they can be used to answer other questions also. | |||
Counting problems, in general, sound complicated, and often we must do our counting subject to many restrictions. The way to solve such problems is to break them down into a series of simple tasks that are easy to count, and employ known rules of combining tasks. The following theorem is a first step in such a process and is sometimes known as the Fundamental Theorem of Counting. | |||
=== Fundamental Theorem of Counting === | |||
If a job consists of <math>k</math> separate tasks, the <math>i</math>-th of which can be done in <math>n_i</math> ways, <math>i = 1, \dots, k</math>, then the entire job can be done in <math>n_1 \times n_2 \times \dots \times n_k</math> ways. | |||
=== Possible Methods of Counting === | |||
Counting can be made with without replacement. Also, the order in which the task is performed may matter. Four types counting scenarios are thus possible: ordered or unordered, both of which may be done with or without replacement. | |||
=== Factorial === | |||
For a positive integer n, n! (read n factorial) is the product of all of the positive integers less than or equal to n [Definition 1.2.16]. That is, <math>n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1</math>. Furthermore, we define 0! = 1. | |||
== Enumerating Outcomes == | |||
= Conditional Probability and Independence = | |||
= Random Variables = | |||
= Distribution Functions = | |||
= Density and Mass Functions = | |||
[[category:Statistics]] | [[category:Statistics]] | ||
[[category:Statistical Inference]] | [[category:Statistical Inference]] | ||
Latest revision as of 22:27, 3 December 2018
Set Theory
Sample Space
The set, S, of all possible outcomes of a particular experiment is called the sample space for the experiment. [Definition 1.1.1]
Event
An event is any collection of possible outcomes of an experiment, that is, any subset of S (including S itself). [Definition 1.1.2]
Let A be an event, a subset of S. We say the event A occurs if the outcome of the experiment is in the set A. When speaking of probabilities, we generally speak of the probability of an event, rather than a set. But we may use the terms interchangeably.
Base relationships
We first need to define formally the following two relationships, which allow us to order and equate sets:
Containment:
Equality:
Elementary operations
Given any two events (or sets) A and B , we have the following elementary set operations:
Union: The union of A and B, written , is the set of elements that belong to either A or B or both:
Intersection: The intersection of A and B, written , is the set of elements that belong to both A and B:
Complementation: The complement of A, written , is the set of all elements that are not in A:
Event operations
The elementary set operations can be combined: for any three events, A, B, and C, defined on a sample space S, the following relationships hold [Theorem 1.1.4].
Commutativity
Associativity
Distributive Laws
DeMorgan Laws
Disjoint events
Two events A and B are disjoint (or mutually exclusive) [Definition 1.1.5] if .
The events A1, A2, ... are pairwise disjoint (or mutually exclusive) if .
Disjoint sets are sets with no points in common. If we draw a Venn diagram for two disjoint sets, the sets do not overlap. The collection consists of pairwise disjoint sets. Note further that .
Event space partitions
If A1, A2,... are pairwise disjoint and , then the collection A1, A2, . . . forms a partition of S. [Definition 1.1.6]
The sets form a partition of . In general, partitions are very useful, allowing us to divide the sample space into small, non-overlapping pieces.
Basics of Probability Theory
Axiomatic foundations
For each event A in the sample space S we want to associate with A a number between zero and one that will be called the probability of A, denoted by P(A).
Sigma Algebra
A collection of subsets of S is called a sigma algebra (or Borel field) [Definition 1.2.1], denoted by , if it satisfies the following three properties:
- (a) (the empty set is an element of ).
- (b) if , then ( is closed under complementation).
- (c) if , then ( is closed under countable unions).
The empty set is a subset of any set. Thus, . Property (a) states that this subset is always in a sigma algebra. Since , properties (a) and (b) imply that S is always in also. In addition, from DeMorganªs Laws it follows that is closed under countable intersections. If , then by property (b), and therefore . However, using DeMorgan's Law, we have . Thus, again by property (b), Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cap^\infty_{i=1} A_i \in \cal{B}} .
Associated with sample space S we can have many different sigma algebras. For example, the collection of the two sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{\emptyset, S\}} is a sigma algebra, usually called the trivial sigma algebra. The only sigma algebra we will be concerned with is the smallest one that contains all of the open sets in a given sample space S .
Probability Function
Given a sample space S and an associated sigma algebra Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cal{B}} , a probability function [Definition 1.2.4] is a function P with domain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cal{B}} that satisfies
- 1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A) \geq 0, \forall_{A \in \cal{B}}} .
- 2. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(S) = 1} .
- 3. If are pairwise disjoint, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\cup^\infty_{i=1} A_i)=\Sigma^\infty_{i=1} P(A_i)} . [Axiom of Countable Additivity]
These three properties are usually referred to as the Axioms of Probability (or the Kolmogorov Axioms, after A. Kolmogorov, one of the fathers of probability theory). Any function P that satisfies the Axioms of Probability is called a probability function. The axiomatic definition makes no attempt to tell what particular function P to choose; it merely requires P to satisfy the axioms. For any sample space many different probability functions can be defined. Which one(s) reflects what is likely to be observed in a particular experiment is still to be discussed.
We need general methods of defining probability functions that we know will always satisfy Kolmogorov's Axioms. We do not want to have to check the Axioms for each new probability function. The following gives a common method of defining a legitimate probability function.
Defining Probability Functions
Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{s_1, \dots, s_n\}} be a finite set. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cal{B}} be any sigma algebra of subsets of S. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1, \dots, p_n} be nonnegative numbers that sum to 1. For any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \in \cal{B}} , define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A) = \Sigma_{\{i:s_i\in A\}}p_i} (The sum over an empty set is defined to be 0.) Then P is a probability function on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cal{B}} . This remains true if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{s_1, s_2, \dots\}} is a countable set [Theorem 1.2.6].
The physical reality of the experiment might dictate the probability assígnment.
The Calculus of Probabilities
Properties of the probability function applied to a single event
If P is a. probability function and A is any set in , then [Theorem 1.2.8]
- (a) , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \emptyset} is the empty set;
- (b) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A) \le 1} ;
- (c) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\overline{A}) = 1 - P(A)} .
Properties of the probability function applied to any set pairs
If P is a probability function and A and B are any sets in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cal{B}} , then [Theorem 1.2.9]
- (a) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(B \cap \overline{A}) = P(B) - P(A \cap B)} ;
- (b) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A \cup B) = P(A) + P(B) - P(A \cap B)} ;
- (c) If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \subset B} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A) \le P(B)} .
Bonferroni's Inequality
Formula (b) of Theorem 1.2.9 gives a useful inequality for the probability of an intersection. Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A \cup B) \le 1} , we have, after some rearranging, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A \cap B) \ge P(A) + P(B) - 1} .
This inequality is a special case of what is known as Bonferroni's Inequality. Bonferroni's Inequality allows us to bound the probability of a simultaneous event (the intersectíon) in terms of the probabilities of the individual events.
Properties of the probability function applied to collections of sets
If P is a probability function, then [Theorem 1.2.11]
- (a) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A) = \Sigma^\infty_{i=1} P(A \cap C_i)} , for any partition Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1, C_2, \dots} ;
- (b) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\cup^\infty_{i=1} A_i) \le \Sigma^\infty_{i=1} P(A_i)} , for any sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1, A_2, \dots} (Boole's Inequality)
There is a similarity between Boole's Inequality and Bonferroni's Inequality. In fact, they are essentially the same thing. We could have used Boole's Inequality to derive that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A \cap B) \ge P(A) + P(B) - 1} (the special case of Bonferroni's Inequality, presented above). If we apply Boole*s Inequality to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{A}} , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\cup^n_{i=1} \overline{A_i}) \le \Sigma^n_{i=1} P(\overline{A_i})} and using the facts that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup\overline{A_i} = \overline{\cap A_i}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\overline{A_i}) = 1 - P(A_i)} , we obtain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 - P(\cap^n_{i=1} A_i) \le n - \Sigma^n_{i=1} P(A_i)}
This becomes, on rearranging terms, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\cap^n_{i=1} A_i) \ge \Sigma^n_{i=1} P(A_i) - (n -1)} , which is a more general version of the Bonferroni Inequality presented before.
Counting
Most often, methods of counting are used in order to construct probability assignments on finite sample spaces, although they can be used to answer other questions also.
Counting problems, in general, sound complicated, and often we must do our counting subject to many restrictions. The way to solve such problems is to break them down into a series of simple tasks that are easy to count, and employ known rules of combining tasks. The following theorem is a first step in such a process and is sometimes known as the Fundamental Theorem of Counting.
Fundamental Theorem of Counting
If a job consists of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} separate tasks, the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} -th of which can be done in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_i} ways, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = 1, \dots, k} , then the entire job can be done in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_1 \times n_2 \times \dots \times n_k} ways.
Possible Methods of Counting
Counting can be made with without replacement. Also, the order in which the task is performed may matter. Four types counting scenarios are thus possible: ordered or unordered, both of which may be done with or without replacement.
Factorial
For a positive integer n, n! (read n factorial) is the product of all of the positive integers less than or equal to n [Definition 1.2.16]. That is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1} . Furthermore, we define 0! = 1.