1 Probability and Statistics
It app ears to be a quite general principle
that, whenever there is a randomized way of
doing something, then there is a
nonrandomized way that delivers better
performance but requires more thought.
Edwin Thompson Jaynes
1.1 Counting (Permutation and Combinations)
All there is to know about elementary finite counting is the following table Table 1.
Table 1: Counting
Counting Ordered Unordered
With Replacement m
n
m+n+1
n
With No Replacement (m)
n
m
n
Understanding the derivation is one thing, and understanding why the derivation had to be that way
is just another, we will try understanding the why by deriving them without any tricks, or in other words
understanding by deriving the trick itself required to understand the derivation of the formulae above.
Even though it does not explain why the proofs are what they are, especially in the orderless sampling
with replacement case, [Chu94] in chapter 3 on counting makes it easy to see why counting is essentially
sampling, and that sampling problems correspond bijectively to allocation problems.
Counting is sampling because we are asking: “if there are m objects, and n of which are to be taken
out, that is sampled, then how many ways are there to do this?”, and it is allocation because we are
asking: “if there are m boxes and n objects to be filled with, that is allocation, then how many ways are
there to do this?”. Let’s study counting sampling first:
Ordered sampling of n objects from m objects is essentially a sequence of length n with elements
from some set M of size m, which can be represented by a function f : N → M from a set N of size
n to a set M of size m; with this representation, asking “how many ways of sampling” or “how many
samples exist” is translated into how many functions are there between these two sets.
Ordered counting, therefore, is about the counting of functions of sets.
As the table shows, we can ask a question now, of “how are the samples prepared?”, and the answer
could be all at once, or one element at a time, that is, if it is a time or a space representation of the
function representing sampling.
If all sample elements are sampled at the same time, there is no possibility of sampling the same
element twice, that is replacement is not possible; that is for the sampling function, each of its domain’s
elements correspond only to one element by definition of function
1
, and that no two elements of the
domain can map to the same element of codomain, that is the function has to be injective
2
.
Concept 1: Permutation: Ordered sampling without replacement
The total number of ordered samples of size n from a set of size m, without replacement, is the
same as the number
a
of injective functions f : N → M .
a
for each element in the domain some element of the codomain is assigned and the codomain elements can be used
only once: m · (m − 1) · · · (m − (n − 1)) =
:
(m)
n
is called Permutation and also sometimes denoted as P (m, n) or
m
P
n
, this is because ordered sample of some set is essentially an arrangement/permutation of the elements of that
set into smaller or equal number of positions; if it is smaller then it is called partial permutation, and if it is equal
then it is called full and is denoted by n! for arrangement/permutation of n objects sampled from n objects.
If all sample elements are not sampled at the same time, that is if sampled one at a time, one after
another, then there is a possibility of replacement, that is they’re put back, if not then it’s the same as
1
that is f : N → M is a function iff n
1
= n
2
=⇒ f (n
1
) = f(n
2
).
2
that is f : M → N is an injective function iff n
1
= n
2
=⇒ f (n
1
) = f(n
2
).
1
the Concept 1; if they’re put back then any two element of the domain of the sampling function can
share the same element in the codomain, that is there are no restrictions on the sampling function.
Concept 2: Ordered sampling with replacement
The total number of ordered samples of size n from a set of size m, with replacement, is same as
the number
a
of functions f : N → M.
a
for each element in the domain some element of the codomain is assigned and the codomain elements can be
used multiple times: m · m · · · · · m
| {z }
n times
=
:
m
n
So, for ordered counting, with replacement allows all sampling functions, and without replacement
allows only a subset of it, the injective sampling functions.
Unordered sampling of n objects from m objects can be represented by a subset of size n of a set M
of size m; with this representation, asking “how many ways of sampling” or “how many samples exist”
is translated into how many subsets of size n are there of the set M.
Since the ordered counting is about the counting of functions of sets, when, however, the order does
not matter, some of these sampling functions are to be identified. Any two sampling functions are to be
counted as one sampling if they differ only by an order, that is only by a bijection on the domain, that is
by a permutation of the domain, that is if one sampling can be obtained by first permuting the domain
and then applying the other sampling function to the resulting permuted domain.
3
Unordered counting, therefore, is about the counting of equivalence classes of equivalence relation on
the set of functions of sets.
Since equivalence classes partitions
4
the set, the sizes of classes sum up to the size of the set, that is
m =
P
m
i=0
[i × (number of classes of size i)].
Concept 3: Combination: Unordered sampling without replacement
xxx
3
i.e. if f
1
: N → M and f
2
: N → M are two sampling functions, and if σ : N → N is a bijection/permutation of N,
then f
1
∼ f
2
⇐⇒ f
1
= f
2
◦ σ, which is an equivalence relation because inverse permutations exist, and two composed
permutations is also a permutation.
4
Partition, by definition, is a set of subsets such that no two of them intersect and the union of them all is the entire
set.
2
My Tastefully Curated Sources of Learning
I cannot remember the bo oks I’ve read any
more than the meals I have eaten; even so,
they have made me.
Ralph Waldo Emerson
Probability and Statistics
[CB24] George Casella and Roger L. Berger. Statistical Inference. CRC Press, Boca Raton, FL, 2nd edition, 2024.
URL: https://www.routledge.com/Statistical-Inference/Casella-Berger/p/book/9781032593036.
[Chu94] Kai Lai Chung. Elementary Probability Theory: With Stochastic Processes and an Introduction to Mathe-
matical Finance. Springer, New York, NY, 4th edition, 1994. URL: https://www.springer.com/gp/book/
9780387955780.
[Sta11] Richard P. Stanley. Enumerative Combinatorics, volume 1 of Cambridge Studies in Advanced Mathemat-
ics. Cambridge University Press, Cambridge, UK, 2nd edition, 2011. URL: https://www.cambridge.org/
9781107602625.
Linear Algebra
[SR13] Igor R. Shafarevich and Alexey O. Remizov. Linear Algebra and Geometry. Springer, Berlin, Heidelberg, 2013.
URL: https://link.springer.com/book/10.1007/978-3-642-30994-6.
Calculus and Optimization
[MN19] Jan R. Magnus and Heinz Neudecker. Matrix Differential Calculus with Applications in Statistics and Econo-
metrics. Wiley, Hoboken, NJ, 3rd edition, 2019. URL: https://www.wiley.com/en-us/Matrix+Differential+
Calculus+with+Applications+in+Statistics+and+Econometrics%2C+3rd+Edition-p-9781119541202.
[Tik86] V. M. Tikhomirov. Stories About Maxima and Minima, volume 1 of Mathematical World. American Mathe-
matical Society, Providence, RI, 1986. URL: https://bookstore.ams.org/mwm-1.
[Tik00] V. M. Tikhomirov. Optimization: Insights and Applications, volume 169 of Translations of Mathematical
Monographs. American Mathematical Society, Providence, RI, 2000. URL: https://bookstore.ams.org/
trans2-169.
Programming, Data Structures and Algorithms
[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Al-
gorithms. MIT Press, Cambridge, MA, 3rd edition, 2009. URL: https://mitpress.mit.edu/books/
introduction-algorithms-third-edition.
[Lut13] Mark Lutz. Learning Python. O’Reilly Media, Sebastopol, CA, 5th edition, 2013. URL: https://www.oreilly.
com/library/view/learning-python-5th/9781449355722/.
Database Management and Warehousing
[KR13] Ralph Kimball and Margy Ross. The Data Warehouse Toolkit: The Definitive Guide to Dimensional Mod-
eling. Wiley, Indianapolis, IN, 3rd edition, 2013. URL: https://www.wiley.com/en-us/The+Data+Warehouse+
Toolkit%3A+The+Definitive+Guide+to+Dimensional+Modeling%2C+3rd+Edition-p-9781118530801.
[RG03] Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems. McGraw-Hill, New York, NY,
3rd edition, 2003. URL: https://pages.cs.wisc.edu/
~
dbbook.
Machine Learning
[GBC16] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, 2016. URL:
https://www.deeplearningbook.org/.
[HTF09] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining,
Inference, and Prediction. Springer, New York, NY, 2nd edition, 2009. URL: https://hastie.su.domains/
ElemStatLearn/.
GPG fingerprint: 4685 9091 7AAE 9B94 36E3 203A 82F2 B0B9 DF18 C1FB
[JWHT21] Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An Introduction to Statistical Learning:
With Applications in Python. Springer, New York, NY, 2nd edition, 2021. URL: https://www.statlearning.
com/.
[Mur12] Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, Cambridge, MA, 2012. URL:
https://mitpress.mit.edu/books/machine-learning-0.
[Nie15] Michael A. Nielsen. Neural Networks and Deep Learning. Determination Press, San Francisco, CA, 2015. URL:
http://neuralnetworksanddeeplearning.com/.
AI
[RN20] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, Harlow, UK,
4th edition, 2020. URL: https://www.pearson.com/store/p/artificial-intelligence-a-modern-approach/
P100000956507.