{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Sets, Combinatorics, & Probability" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Probability versus Statistics\n", "\n", "In probability, we assume we know what the world is like, and predict what we would then see.\n", "\n", "In statistics, we make observations and use them to learn something about the world.\n", "That generally requires a mathematical model for how the obervations were generated, to relate the observations to properties of the world.\n", "Sometimes, that model arises naturally from knowledge of the process that generated the data,\n", "for instance, a randomized experiment or a physical measurement where the\n", "underlying physics is understood.\n", "In other cases, the model is basically an assumption.\n", "When the model does not have a firm basis in actual knowledge, inferences are suspect.\n", "As Robert L. Parker says, \"the more you assume, the less you know.\"\n", "\n", "Probability is like a _forward problem_ in science or engineering: the the physics, including any parameters,\n", "is known. The issue is to predict what will be observed, up to instrumental error and other noise.\n", "\n", "Statistics, at least inferential statistics, is like an _inverse problem_. The physics is known\n", "but there are unknown parameters. The issue is to use the (noisy) data to learn about parameters\n", "of the system.\n", "\n", "Probability is a combination of mathematics and philosophy.\n", "The philosophy connects the mathematics to the world.\n", "\n", "We will start with the mathematics." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sets\n", "\n", "The mathematics of probability is expressed most naturally using set theory.\n", "We will review the basic terminology and reviews naive set theory: how to define and\n", "manipulate sets, operations on sets that yield other sets, special\n", "relationships among sets, and so on.\n", "\n", "A _set_ is a collection of objects, called _members_ or _elements_ of the set, without\n", "regard for their order.\n", "$a \\in A$, pronounced \"$a$ is an element of $A$,\" \"$a$ is in $A$,\" or \"$a$ is a member of\n", "$A$\" means that $a$ is an element of the set $A$.\n", "This is the same as writing $A \\ni a$, which is pronounced \"$A$ contains $a$.\"\n", "If $a$ is not an element of $A$, we write $a \\not \\in A$.\n", "Sets may be described explicitly by listing their contents, or implicitly\n", "by specifying a property that all elements of the set share, or a condition\n", "that they satisfy.\n", "The contents of sets are enclosed in curly braces: $\\{ \\}$.\n", "\n", "Here are some examples:\n", "+ $A = \\{a, b, c, d \\}$: the set containing the four elements $a$, $b$, $c$, and $d$.\n", "+ $\\emptyset = \\{ \\}$: the empty set, the set that contains no elements.\n", "+ ${\\mathbf Z} \\equiv \\{ \\ldots, -2, -1, 0, 1, 2, \\ldots \\}$: the integers.\n", "+ ${\\mathbf N} \\equiv \\{1, 2, 3, \\ldots \\}$: the natural (counting) numbers.\n", "+ $\\Re \\equiv (-\\infty, \\infty)$: the real numbers.\n", "+ $\\Re^+ \\equiv [-\\infty, \\infty]$: the extended real numbers.\n", "+ ${\\mathbf C} \\equiv \\{ a + bi: a, b \\in \\Re \\}$, where $i = \\sqrt{-1}$: the complex numbers.\n", "+ ${\\mathbf Q} \\equiv \\{ a/b: a, b \\in {\\mathbf Z}, b \\ne 0\\}$: the rational numbers.\n", "\n", "\n", "$B$ is a _subset_ of $A$, written $B \\subset A$ or $A \\supset B$, if every element\n", "of the set $B$ is also an element of the set $A$.\n", "Thus ${\\mathbf N} \\subset {\\mathbf Z} \\subset {\\mathbf Q} \\subset \\Re \\subset {\\mathbf C}$.\n", "The empty set $\\emptyset$ is a subset of every set.\n", "If $A \\subset B$ and $B \\subset A$, $A$ and $B$ are the same set, and we write $A = B$.\n", "If $B$ is not a subset of $A$, we write $B \\not \\subset A$ or $A \\not \\supset B$.\n", "$B$ is a _proper subset_ of $A$ if $B \\subset A$ but\n", "$A \\not \\subset B$.\n", "\n", "The _complement_ of $A$ (with respect to the universe ${\\mathcal X}$), written $A^c$ or $A'$,\n", "is the set of all objects under consideration (${\\mathcal X}$) that are not elements of $A$.\n", "That is, $A^c \\equiv \\{ a \\in {\\mathcal X} : a \\not \\in A\\}$.\n", "\n", "The _intersection_ of $A$ and $B$, written $A \\cap B$ or $AB$, is the set of all objects that\n", "are elements of both $A$ and $B$:\n", "$$\n", "A \\cap B \\equiv \\{a: a \\in A \\mbox{ and } a \\in B \\}.\n", "$$\n", "If $A \\cap B = \\emptyset$, we say $A$ and $B$ are _disjoint_ or _mutually\n", "exclusive_.\n", "\n", "The _union_ of $A$ and $B$, written $A \\cup B$, is the set of all objects that\n", "are elements of $A$ or of $B$ (or both):\n", "$$\n", "A \\cup B \\equiv \\{a: a \\in A \\mbox{ or } a \\in B \\mbox{ or both} \\}.\n", "$$\n", "\n", "The _difference_ or _set difference_ of $A$ and $B$, $A \\setminus B$, pronounced \"$A$ minus $B$,\" is\n", "the set of all elements of $A$ that are not elements of $B$:\n", "$$\n", "A \\setminus B \\equiv \\{a \\in A : a \\not \\in B \\} = A \\cap B^c.\n", "$$\n", "\n", "_Intervals_ are special subsets of ${\\mathbf R}$:\n", "$$\n", "[a, b] \\equiv \\{x \\in \\Re : a \\le x \\le b\\}\n", "$$\n", "$$\n", "(a, b] \\equiv \\{x \\in \\Re : a < x \\le b\\}\n", "$$\n", "$$\n", "[a, b) \\equiv \\{x \\in \\Re : a \\le x < b\\}\n", "$$\n", "$$\n", "(a, b) \\equiv \\{x \\in \\Re : a < x < b\\}.\n", "$$\n", "Sometimes we have a collection of sets, _indexed_ by elements of another\n", "set: $\\{A_\\beta : \\beta \\in B \\}$.\n", "Then $B$ is called an _index set_.\n", "If $B$ is a subset of the integers ${\\mathbf Z}$, usually we write $A_i$ or $A_j$, etc.,\n", "rather than $A_\\beta$.\n", "If $B = {\\mathbf N}$, we usually write $\\{A_j\\}_{j=1}^\\infty$ rather than\n", "$\\{A_\\beta : \\beta \\in {\\mathbf N} \\}$.\n", "$$\n", "\\bigcap_{\\beta \\in B} A_\\beta \\equiv \\{a: a \\in A_\\beta \\;\\;\\forall \\beta \\in B \\}.\n", "$$\n", "($\\forall$ means \"for all.\")\n", "If $B = \\{1, 2, \\ldots, n\\}$, we usually write $\\bigcap_{j=1}^n A_j$ rather than\n", "$\\bigcap_{j \\in \\{1, 2, \\ldots, n\\}} A_j$.\n", "The notation $\\bigcup_{\\beta \\in B} A_\\beta$ and $\\bigcup_{j=1}^n A_j$ are defined analogously.\n", "\n", "A collection of sets $\\{A_\\beta : \\beta \\in B \\}$ is _pairwise disjoint_\n", "if $A_\\beta \\cap A_{\\beta'} = \\emptyset$ whenever $\\beta \\ne \\beta'$.\n", "The collection $\\{A_\\beta : \\beta \\in B\\}$ _exhausts_ or _covers_\n", "the set $A$ if $A \\subset \\bigcup_{\\beta \\in B} A_\\beta$.\n", "The collection $\\{A_\\beta : \\beta \\in B \\}$ is a _partition_ of the\n", "set $A$ if $A = \\cup_{\\beta \\in B} A_\\beta$ and the \n", "sets $\\{A_\\beta : \\beta \\in B \\}$\n", "are pairwise disjoint.\n", "If $\\{A_\\beta : \\beta \\in B \\}$ are pairwise disjoint and exhaust $A$, then\n", "$\\{A_\\beta \\cap A : \\beta \\in B \\}$ is a partition of $A$.\n", "\n", "A set is _countable_ if its elements can be put in one-to-one correspondence with\n", "a subset of ${\\mathbf N}$.\n", "A set is _finite_ if its elements can be put in one-to-one correspondence with\n", "$\\{1, 2, \\ldots, n\\}$ for some $n \\in {\\mathbf N}$.\n", "If a set is not finite, it is infinite.\n", "${\\mathbf N}$, ${\\mathbf Z}$, and ${\\mathbf Q}$ are infinite and countable\n", "(_countably infinite_);\n", "${\\mathbf R}$ is infinite and uncountable.\n", "\n", "The notation $\\# A$, pronounced \"the cardinality of $A$\" is the size of the set $A$, suitably defined.\n", "If $A$ is finite, $\\# A$ is the number of elements in $A$.\n", "If $A$ is not finite but $A$ is countable (if its elements can be put in one-to-one\n", "correspondence with the elements of ${\\mathbf N}$), then $\\# A = \\aleph_0$ (aleph-null).\n", "If the elements of $A$ can be put in one-to-one correspondence with the elements of $\\mathbf{R}$, then\n", "$\\#A = c$, _the cardinality of the continuum_.\n", "\n", "The _power set_ of a set $A$, denoted $2^A$, is the set of all subsets of the set $A$.\n", "For example, the power set of $\\{a, b, c\\}$ is\n", "$$\n", "\\{ \\emptyset, \\{a\\}, \\{b\\}, \\{c\\}, \\{a, b\\}, \\{a, c\\}, \\{b, c\\}, \\{a, b, c\\} \\}.\n", "$$\n", "If $A$ is a finite set, the cardinality of the power set of $A$ is $2^{\\# A}$.\n", "This can be seen as follows: suppose $\\# A = n$ is finite.\n", "Consider the elements of $A$ to be written in some canonical order.\n", "We can specify an element of the power set by an $n$-digit binary number.\n", "The first digit is 1 if the first element of $A$ is in the subset, and 0 otherwise.\n", "The second digit is 1 if the second element of $A$ is in the subset, and 0 otherwise,\n", "etc.\n", "There are $2^n$ $n$-digit binary numbers, so there are $2^n$ subsets.\n", "The cardinality of the power set of ${\\mathbf N}$ is not $\\aleph_0$.\n", "\n", "If $A$ is a finite set, $B$ is a countable set\n", "and $\\{A_j : \\beta \\in B \\}$ is a partition of $A$, then\n", "$$\n", "\\# A = \\sum_{\\beta \\in B} \\# A_\\beta.\n", "$$\n", "\n", "Suppose $A = A_1 \\cup A_2$, but that possibly $A_1 A_2 \\ne \\emptyset$,\n", "so $\\{A_1, A_2\\}$ might not be a partition of $A$, because\n", "$A_1$ and $A_2$ are not necessarily disjoint.\n", "Then still \n", "$$\\#A = \\#A_1 + \\#A_2 - \\#A_1A_2.$$\n", "\n", "This is seen most easily using a Venn diagram, and can be proved\n", "by constructing a partition of $A$,\n", "$A = A_1A_2^c \\cup A_1^cA_2 \\cup A_1A_2$, and noting that\n", "$\\#A_1 + \\#A_2 = \\#A_1A_2^c + \\#A_1^cA_2 + 2\\#A_1A_2$.\n", "\n", "If \n", "$A = A_1 \\cup A_2 \\cup A_3$ but $\\{A_1, A_2, A_3\\}$ are not necessarily disjoint,\n", "then still\n", "\n", "$$\\#A = \\#A_1 + \\#A_2 + \\#A_3 - \\#A_1A_2 - \\#A_1A_3 - \\#A_2A_3 + \\#A_1A_2A_3.$$\n", "\n", "More generally, if $A = \\cup_{i=1}^n A_i$, then the _Inclusion-Exclusion Principle_ holds:\n", "\n", "$$ \\#A = \\sum_{i=1}^n \\#A_i - \\sum_{1 \\le i_1 < i_2 \\le n} \\#(A_{i_1}A_{i_2}) +\n", "\\sum_{1 \\le i_1 < i_2 < i_3 \\le n} \\#(A_{i_1}A_{i_2}A_{i_3}) - \\cdots \n", "+(-1)^{k-1} \\sum_{1 \\le i_1 < i_2 < \\cdots < i_k \\le n} \\# (A_{i_1}A_{i_2} \\cdots A_{i_k}) + \\cdots\n", "$$\n", "\n", "### Some useful set relations\n", "\n", "+ If $A\\subset B$ and $B\\subset A$ then $A = B$. (If two sets are subsets of each other, they are the same set.)\n", "\n", "+ $\\emptyset \\subset A$. (The empty set is a subset of every set.)\n", "\n", "+ $\\emptyset \\cup A = A$.\n", "(The union of the empty set and any other set is that set.)\n", "\n", "+ $\\emptyset \\cap A = \\emptyset$.\n", "(The intersection of the empty set and any other set is empty.)\n", "\n", "+ If $A \\subset B$ and $B \\subset C$ then $A \\subset C$. (The subset relation is transitive.)\n", "\n", "+ If $A \\subset B$ then $B^c \\subset A^c$.\n", "(Complementation reverses the subset relation.)\n", "\n", "+ $A \\cap B \\subset A$. Moreover, $A\\cap B = A$ if and only if $A \\subset B$.\n", "\n", "+ $A \\subset A\\cup B$. Moreover, $A = A\\cup B$ if and only if $B \\subset A$.\n", "\n", "+ $(A\\cap B)^c = A^c \\cup B^c$. (de Morgan)\n", "\n", "+ $(A\\cup B)^c = A^c\\cap B^c$. (de Morgan)\n", "\n", "+ $A \\cap B = B \\cap A$. (Intersection is commutative.)\n", "\n", "+ $A\\cup B = B\\cup A$. (Union is commutative.)\n", "\n", "+ $A\\cap (B\\cap C) = (A\\cap B)\\cap C$. (Intersection is associative.)\n", "\n", "+ $A\\cup (B\\cup C) = (A\\cup B)\\cup C$. (Union is associative.)\n", "\n", "+ $A\\cap (B\\cup C) = (A\\cap B)\\cup (A\\cap C)$. (Distribution of intersection over union.)\n", "\n", "+ $A\\cup (B\\cap C) = (A\\cup B)\\cap (A\\cup C)$. (Distribution of union over intersection.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "