Created At: [[2025-02-11]] > [!info] > I am trying to practice the Feynman technique for learning here, and try to explain the core concepts covered in this chapter using my own words. # Chapter 01 - Events and Probability This chapter covers several interesting applications of how probability can be applied to some real-world applications, and drastically improve the time complexity of such problems. Namely, it covers the following examples: 1. How we can utilise randomness to verify the expansion of polynomial multiplications 2. How we can utilise randomness to verify matrix multiplications 3. How the naive bayesian classifier works 4. How we can devise a randomised min-cut algorithm (that's surprisingly simple yet works quite well). ## 1. Verifying Polynomials ### 1.1. Problem Setup Say that we are given a polynomial in the factorised form: $ p^{(n)}(x) := \prod_{i=1}^{n}(a_ix+b_i), $ where $a_is and $b_is are some constants. We know that it can be expanded to the following form: $ p^{(n)}(x) = \sum_{i=0}^{n} c_ix^i, $ where $b_is are some constants as well. How can we be sure that this expansion is correct? ### 1.2. Naive Verification & Complexity The naive way of doing this is that we do the expansion again. However, the complexity of performing such an action is quite high. It can be modelled as such: we are having $n$ terms, and for each term, we are picking either $a_i x$ or $b_i$, as having 2 possible cases. Therefore, we would be having $ 2^n $ expanded terms in the resulting polynomial. And, summing them together would give us a complexity of roughly equal to $O(2^n).$ In addition to the high complexity, there is one additional downside to this approach as well. If our algorithm for polynomial expansion was wrong initially, it is quite likely that our verification algorithm would be wrong again. This could be said generally about most of the verification problems that we see within this chapter. So, could there be any better solutions to this problem? ### 1.3. Randomised Verification #### 1.3.1 Basic Setup We can apply randomisation to help. However, before that, we will need to define two functions for convenience. Let $ f^{(n)}(x) := \prod_{i=1}^{n}(a_ix + b_i) $ be the original, unexpanded (factorised) form of the polynomial, and let $ g^{(n)}(x) := \sum_{i=0}^{n}c_i x^i $ be the solution (of expansion) that we need to verify. Note $f \stackrel{?}{=} g$, as that equality is what we are trying to verify here. We now look at the following $h^{(n)}$ defined as follows: $ h(x) := f(x) - g(x). $ Clearly, if $f=g$ holds, i.e. if the solution was correct, then we have $ h(x) = 0 $ for all $x$ chosen. Otherwise, there would exist some $x \in \mathcal{D}$ (let $\mathcal{D}$ define the domain of the functions) such that $h(x) \neq 0$. #### 1.3.2. Probability of Error Let $\mathcal{S}\subseteq \mathcal{D}$ be a subset of the domain $\mathcal{D}$. We define the set $\mathcal{H}$ as follows: $ \mathcal{H}:=\{s \in \mathcal{S}\mid h(s) = 0\}, $ i.e. the values within $\mathcal{S}$ such that $h(s) = 0$. Let $\mathcal{E}$ denote the event that $f \neq g$. Then, essentially, we want to find $ P(\mathcal{H}\mid \mathcal{E}), $ which is the probability of the function $h$ yielding $0$ given $f \neq g$ (i.e. the solution was incorrect). This would be the probability of having a 'false positive', i.e. successfully passing the verification algorithm but the solution is not correct. Since $h$ is a function of maximumly degree $n$ (it is the difference between two functions of degree $n$, and as such it can maximumly have degree $n$), we know that it can maximumly have $n$ roots. $ \begin{aligned} P(\mathcal{H}\mid \mathcal{E}) \leq \dfrac{n}{|\mathcal{S}|}. \end{aligned} $ Therefore, we would be having the probability of error of $\dfrac{n}{|\mathcal{S}|}$ for a polynomial of degree $n$. #### 1.3.3. Reducing Error Rates There are two ways of reducing the error rate. First, is that we increase the cardinality (size) of the set $\mathcal{S}$. Clearly, as $|\mathcal{S}|$ increases, the probability dips lower. The second way of reducing the error rate is to repeat such experiments. The more times we repeat, the lesser the likelihood of error would be. There are, however, two cases for such randomised sampling: sampling with replacement, and without replacement. > [!todo] Write about drawing with / without replacement ## 2. Verifying Matrix Multiplication ### 2.1. Problem Setup There is another set of problems that is quite complex: verifying that the multiplication of two matrices of rank $n$ are indeed correct. Let's define two matrices $A$ and $B$ as follows: $ A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}\quad \text{and}\quad B = \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1n} \\ b_{21} & b_{22} & \cdots & b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{pmatrix}. $ We also have a matrix $C$: $ C = \begin{pmatrix} c_{11} & c_{12} & \cdots & c_{1n} \\ c_{21} & c_{22} & \cdots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{n1} & c_{n2} & \cdots & c_{nn} \end{pmatrix} $ that is the result of such multiplication. Note that $AB \stackrel{?}{=} C$, as that equality is what we wish to verify. Normally, it takes an $O(n^3)$ to verify such multiplications. This is because for each $c_{ij}$, we need to verify the following equation $ \begin{aligned} c_{ij} \stackrel{?}{=} \sum_{k=1}^{n}a_{ik}b_{kj}, \end{aligned} $ which takes $n$ pairwise multiplications. There are total $n^2$ entries in the resulting matrix. As such, we would have $n^3$ operations in total (roughly). There are algorithms that are faster, say Strassen's algorithm, but for brute force verifications, it takes this long, and to this day there has been no deterministic algorithm found to calculate the product of two matrices with $\Theta(n^2)$ complexity. ### 2.2. Randomised Setup We now take a vector $\mathbf{v}$ of size $n \times 1$: $ \mathbf{v} = \begin{bmatrix} v_{1} \\ v_{2} \\ \vdots \\ v_{n} \end{bmatrix}, $ where each $i_j$ is taken from $\{0, 1\}$. for $j \in \{1, 2, \cdots, n\}$. We now want to verify that: $ (AB)\mathbf{v} = C\mathbf{v}. $ If $AB = C$, then this clearly holds. Essentially, we are testing: $ (AB-C)\mathbf{v} = \mathbf{0}. $ Now, let $M := AB-C$, we are essentially considering $M\mathbf{v}=\mathbf{0}$. Now, let us assume that $M \neq AB$.