# Logarithms

Suppose you want to solve $10^x = 100$. We can see that $10*10 = 10^2 = 100$, hence $x=2$. However, what if we wanted a general function that solves for $x$:

$$
a^x = b
$$

This is where we define the **logarithm** function, where $x = \log_a b$. The logarithm answers the question: How many times do I have to multiply $a$ by itself to get $b$?

From this definition, we can derive a few properties of the logarithm function

## $\log_a a = 1$

We can multiply $a$ by itself exactly 1 time to get a ($a^1 = a$). Hence $\log_a a = 1$

---

## $\log_a x + \log_a y = \log_a xy$

We can let $p = a^x, q = a^y$. $pq = a^x a^y = a^{x+y}$.

$$
\begin{aligned}
    p &= a^x \implies \log_a p = x \log_a a = x \\
    q &= a^y \implies \log_a q = y \\
    pq &= a^{x+y} \implies \log_a pq = x + y = \log_a p + \log_a q
\end{aligned}
$$

Similarly, $\log_a x - \log_a y = \log_a \frac{x}{y}$

---

## $\log_a x^y = y \log_a x$

Since $\log_a x + \log_a x = 2\log_a x = \log_a x^2$, we can generalise that $y \log_a x = \log_a x  + \cdots + \log_a x = \log_a (x\cdots x) = \log_a x^y$

---

## $\log_a b = \frac{\log_c b}{\log_c a}$

$$
\begin{aligned}
x &= \log_a b \\
a^x &= b \\
\log_c a^x &= \log_c b & \text{(Take $\log_c$ both sides)} \\
x \log_c a &= \log_c b & (\log_a x^y = y \log_a x) \\
x &= \frac{\log_c b}{\log_c a} \\
\log_a b &= \frac{\log_c b}{\log_c a}
\end{aligned}
$$


 Logarithms

# Longest Common Subsequence

The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences.

If S1 and S2 are the two given sequences then, Z is the common subsequence of S1 and S2 if Z is a subsequence of both S1 and S2. Furthermore, Z must be a strictly increasing sequence of the indices of both S1 and S2.

For example, the longest common subsequence between `ABCDE` and `AXBXCXBXA` is 3 (`ABC`)

Let's look at a few properties first before tackling the code.

1. The longest common subsequence between any string with an empty string is 0. "AAA" and "" have a longest common subsequence of 0
2. The longest common subsequence between any strings with the same last 2 characters is 1 + the longest common subsequence if both the strings did not have that character.

Between `ABC` and `BDC`, we know that `C` will be part of the subsequence, hence we can just compare `AB` and `BD`, and figure out the longest common subsequence between those 2 shortened strings. Afterwards, we can add 1 to that result.

3. Now between `ABCD` and `BDEF`, to find the longest common subsequence, we

- Remove 1 character from the first string, and compare the LCS for both strings (`lcs("ABC", "BDEF")`)
- Remove 1 character from the second string, and compare the LCS for both strings (`lcs("ABCD", "BDE")`)
- Take the maximum as the answer

With these information, we can write a recurrent function first

```python
def lcs(s1, s2):
    # If one of the strings is empty, the longest common subsequence is 0
    if len(s1) == 0 or len(s2) == 0:
        return 0

    # If the last characters are the same, we can add 1 to the score
    if s1[-1] == s2[-1]:
        return 1 + lcs(s1[:-1], s2[:-1])

    # Remove 1 character from the first string and compare, remove 1 character from the second string and compare
    return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
```

However, this algorithm has a very long runtime. We can reduce this by using dynamic programming instead. We will create a DP table, and build up our answers from there.

# Dynamic Programming

Dynamic Programming is an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.

Let us consider finding the LCS of "ABC" and "BCZA"

So, to represent our series of subproblems, we can use the following table

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  |     |     |     |
| B   |     |     |     |
| C   |     |     |     |
| Z   |     |     |     |
| A   |     |     |     |

Each cell in the table represents the LCS of the string up to that character. For example, `table[0][0]` is the LCS for 2 empty strings. `table[1][3]` is the LCS between "B" and "ABC". Our final result is in `table[4][3]`

To begin, we can realise that any comparison with an empty string is 0. Hence,

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   |     |     |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

Next. We look at `table[1][1]`. We are finding the longest common subsequence between "A" and "B", which is the maximum of

1. The LCS between "A" and ""
2. The LCS between "" and "B"

The answer to 1. is in `table[0][1]` and 2. in `table[1][0]`. Hence, `table[1][1] = 0`

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   |     |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

Now we consider `table[1][2]`. We are looking for the LCS between "AB" and "B". Since the last characters are the same, we can conclude that `lcs("B", "AB") = 1 + lcs("", "A")`. From the table, we can conclude that `lcs("B", "AB") = 1`.

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

In general, if at `table[m][n]`, the last characters of both strings are equal, then `table[m][n] = 1 + table[m-1][n-1]`.

Now we consider `table[1][3]`. We are trying to find the LCS of "ABC" and "B". The last character is not the same. Hence, we look at the 2 cases we mentioned.

1. `lcs("AB", "B")`, removing the last character of the first string. From the table, `lcs("AB", "B") = 1`
2. `lcs("ABC", "")`, removing the last character of the second string. From the table, `lcs("ABC", "") = 0`

With these 2 pieces of information, we can conclude that `lcs("ABC", "B") = max(1, 0) = 1`.

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   | 1   |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

We can continue filling up the entire table, and it will look like this

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   | 1   |
| C   | 0   | 0   | 1   | 2   |
| Z   | 0   | 0   | 1   | 2   |
| A   | 0   | 1   | 1   | 2   |

So, our final result is `lcs("ABC", "BCZA") = 2`

The code looks like this

```python
def lcs(s1, s2):
    # DP Table
    results = [[0]*(len(s1)+1) for i in range(len(s2)+1)]

    for columnIndex in range(1, len(results[0])):
        for rowIndex in range(1, len(results)):
            currentCharS1 = s1[columnIndex-1]
            currentCharS2 = s2[rowIndex-1]

            if currentCharS1 == currentCharS2:
                results[rowIndex][columnIndex] = 1 + results[rowIndex-1][columnIndex-1] # same as removing the last character of both strings
            else:
                results[rowIndex][columnIndex] = max(results[rowIndex-1][columnIndex], results[rowIndex][columnIndex-1])

    print(results)
    return results[-1][-1]
``
```


 Longest Common Subsequence

# N-Queens

Problem: Given an NxN sized chessboard, generate all possible configurations where N queens are placed on the board, and all of them do not attack each other

The N-queens problem will take very long to run, if we were to check all possible permutations of the chessboard. The total number of possible permutations are given by

$$
T(N) = {N^2 \choose N}
$$

For a standard chessboard $N = 8$, there are a total of 4,426,165,368 combinations, but only 92 solutions.

Instead of generating all possible permutations, we can constrain which permutations we generate. By constraining to have only 1 queen per row, we reduce the total possible permuations to

$$
T(N) = N^N
$$

For $N = 8$, we reduced the number of permutations to 16,777,216 (0.379% of the original). We can also further restrict that at most 1 queen can exist per diagonal, reducing it to $N!$ ($T(8) = 40320$).

We can use backtracking to solve the problem. The pseudocode is as follows:

1. Start from (0, 0)
2. For a specific row
   1. For all columns in the row
      1. Place the queen in that column
      2. If the board is still valid
         1. Recurse with the next row, starting again from the first column
      3. If all the queens are placed, and the board is valid
         1. Print the board
      4. Remove the queen from the space

```python
def n_queens(board, row, col):
    if row > len(board)-1 or col > len(board)-1:
        return

    for i in range(len(board)):
        # Try to add queen on the column
        board[row][i] = 1

        # If adding the queen is valid, recurse
        if isValidBoard(board):
            n_queens(board, row+1, col)

        # If all queens placed, and is valid
        if sum([sum(row) for row in board]) == n and isValidBoard(board):
            print('===')
            printBoard(board)

        # Remove the queen
        board[row][i] = 0

def printBoard(board):
    for i in range(len(board)):
        print(board[i])

def isValidBoard(board):
    # at most 1 queen per row
    for i in range(len(board)):
        if sum(board[i]) > 1:
            # print("Row is not valid")
            # printBoard(board)
            return 0

    # at most 1 queen per col
    for i in range(len(board)):
        if sum([row[i] for row in board]) > 1:
            # print("Column is not valid")
            # printBoard(board)
            return 0

    # Generating diagonals https://stackoverflow.com/questions/23069388/listing-elements-in-a-nested-lists-diagonally/23069625#23069625
    # at most 1 queen per diagonal
    h = len(board)
    w = len(board)
    for diagonal in [[board[h-1-q][p-q]
        for q in range(min(p, h-1), max(0, p-w+1)-1, -1)]
       for p in range(h+w-1)]:
          if sum(diagonal) > 1:
              return 0

    #  at most 1 queen per antidiagonal
    for antiDiagonal in [[board[p - q][q]
        for q in range(max(p-h+1,0), min(p+1, w))]
        for p in range(h + w - 1)]:
        if sum(antiDiagonal) > 1:
          return 0

    return 1

n = 12
board = [[0 for i in range(n)] for i in range(n)]
n_queens(board, 0, 0)
```

# Algorithm Analysis

Let $T(N)$ be the runtime for the n-queens algorithm of size $N$. From the code, we can express the runtime complexity recursively

$$
T(N) \approx N*(T(N-1) + O(N^2))
$$

At size $N$, we loop $N$ times, and we then call `n_queens` on the row afterwards, reducing the remaining number of rows to $N-1$. The last term $O(N^2)$ comes from the fact that `isValidBoard` runs in $O(N^2)$ time, checking all $N$ rows and $N$ columns.

Solving the recursive expression,

$$
T(N) = O(N!)
$$


 N-Queens

# Population vs Sample, and how to calculate statistics when combining datasets

It is important to distinguish **population** vs **sample**. A **population** is defined as **all members of a specified group**, while a **sample** is **part of a population**

> The **sample mean** is the average and is the sum of all observed outcomes from the sample divided by the total number of samples. The sample mean is denoted by $\bar{X}$

$$
\bar{X} = \frac{1}{n}\sum_{i=1}^{n} x_i
$$

The **population mean**, $\mu$ is the average of the entire population

> The **variance** is a statistical measurement of the spread between numbers in the dataset. The population variance, $\sigma^2$ and the sample variance $\hat{\sigma}^2$ are given by

$$
\sigma^2 = \frac{1}{N} \sum_{i=1}^{N}(x_i - \bar{X})^2 = \frac{1}{N} \left( \sum_{i=1}^{N}x_i^2 - \frac{\left(\sum_{i=1}^{N} x_i\right)^2}{N} \right)
$$

$$
\hat{\sigma}^2 = \frac{1}{N-1} \sum_{i=1}^{N}(x_i - \bar{X})^2 = \frac{1}{N-1} \left( \sum_{i=1}^{N}x_i^2 - \frac{\left(\sum_{i=1}^{N} x_i\right)^2}{N} \right)
$$

> The standard deviation is the square root of the variance

$$
\sigma = \sqrt{\frac{1}{N} \sum_{i=1}^{N}(x_i - \bar{X})^2}
$$

$$
\hat{\sigma} = \sqrt{\frac{1}{N-1} \sum_{i=1}^{N}(x_i - \bar{X})^2}
$$

# Effects of Transformations on the Mean and Variance

If a random variable $X$ has a mean $\mu$ and standard deviation $\sigma$, and we let $Y = AX + B$, then

$$
\begin{aligned}
\mu_Y &= A\mu + B \\
\sigma_Y &= A^2 \sigma^2
\end{aligned}
$$

# Deriving the Mean and Variance of the Sample Mean

Let $X_1, X_2, ..., X_n$ be $n$ independently drawn (with replacement) observations from a distribution with mean $\mu$ and variance $\sigma^2$. If they were not drawn with replacement, each observation would not be independent anymore.

$$
E(X_i) = \mu, Var(X_i) = \sigma^2
$$

Let $\bar{X}$ be the mean of the $n$ independent observations

$$
\bar{X} = \frac{1}{n}\sum_{i=1}^{n} X_i
$$

From here, the expected value of $\bar{X}$ is:

$$
\begin{aligned}
E(\bar{X}) &= E\left(\frac{1}{n}\sum_{i=1}^{n} X_i\right) \\
&= \left(\frac{1}{n}\right) E\left(\sum_{i=1}^{n} X_i\right) \\
&= \left(\frac{1}{n}\right) \sum_{i=1}^{n} E\left(X_i\right) \\
&=  \left(\frac{1}{n}\right) \sum_{i=1}^{n} \mu \\
&= \left(\frac{1}{n}\right) n \mu \\
&= \mu
\end{aligned}
$$

From this, we can conclude that the **expected mean of the sample is the population mean**

Similarly, the variance of $\bar{X}$,

$$
\begin{aligned}
Var(\bar{X}) &= Var\left(\frac{1}{n}\sum_{i=1}^{n} X_i \right) \\
&= \frac{1}{n^2} Var\left(\sum_{i=1}^{n} X_i \right) \\
&= \frac{1}{n^2} \sum_{i=1}^{n} Var\left(X_i \right) \\
&= \frac{1}{n^2} \sum_{i=1}^{n} \sigma^2 \\
&= \frac{1}{n^2} n\sigma^2 \\
&= \frac{\sigma^2}{n}
\end{aligned}
$$

In conclusion, the sampling distribution of $\bar{X}$ has

- Mean $\mu$
- Standard deviation $\frac{\sigma}{\sqrt{n}}$

# Why is the sample variance divided by $N-1$?

We will now prove that

$$
E(S^2) = E\left[\frac{1}{n-1}\sum_{i=1}^{n}(X_i - \bar{X})^2\right] = \sigma^2
$$

This will show why we divide the sample variance by $n-1$ and not $n$

Let $X_1, X_2, ..., X_n$ be $n$ independently drawn (with replacement) observations from a distribution with mean $\mu$ and variance $\sigma^2$. This means that $E(X) = \mu, Var(X) = \sigma^2$.

We know that

$$
\begin{aligned}
Var(X) &= E(X^2) - [E(X)]^2 \\
\sigma^2 &= E(X^2) - \mu^2 \\
E(X^2) &= \sigma^2 + \mu^2
\end{aligned}
$$

Similarly,

$$
E(\bar{X}^2) = \frac{\sigma^2}{n} + \mu
$$

As explained in the previous section, the sampling distribution of $\bar{X}$ has mean $\mu$ and variance $\frac{\sigma^2}{n}$

We will now compute $E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right]$

$$
\begin{aligned}
E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right] &= E\left[\sum_{i=1}^{n}(X_i^2 - 2X_i\bar{X} + \bar{X}^2)\right] & \text{Expand} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - \sum_{i=1}^{n} 2X_i\bar{X} + \sum_{i=1}^{n} \bar{X}^2\right] & \text{Split summations} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - 2\bar{X} \sum_{i=1}^{n} X_i + n \bar{X}^2\right] & \sum_{i=1}^{n} \bar{X}^2 = n \bar{X}^2 \\
&= E\left[\sum_{i=1}^{n}X_i^2 - 2\bar{X} n\bar{X} + n \bar{X}^2\right] & \frac{\sum_{i=1}^{n} X_i}{n} = \bar{X} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - n\bar{X}^2\right] \\
&= \sum_{i=1}^{n}E\left[X_i^2\right] - nE\left[\bar{X}^2\right] \\
&= \sum_{i=1}^{n} (\sigma^2 + \mu^2) - n(\frac{\sigma^2}{n} + \mu) & E\left[X_i^2\right] = \sigma^2 + \mu^2, E(\bar{X}^2) = \frac{\sigma^2}{n} + \mu  \\
&= n(\sigma^2 + \mu^2) - n(\frac{\sigma^2}{n} + \mu) \\
&= (n-1) \sigma^2
\end{aligned}
$$

Now,

$$
\begin{aligned}
E(S^2) &= E\left[\frac{1}{n-1} \sum_{i=1}^{n}(X_i - \bar{X})^2\right] \\
&= \frac{1}{n-1}  E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right] \\
&= \frac{1}{n-1} (n-1)\sigma^2 \\
&= \sigma^2
\end{aligned}
$$

Also, another way to look at this:

If we take a sample of size $n$ from $X$, then

$$
\sigma_X^2 = \frac{1}{n} \sum_{i=1}^{n} (X_i - \bar{X})^2
$$

According to the above, the random variable $X$ deviates from the sample mean $\bar{X}$ with variance $\sigma_X^2$. The sample mean $\bar{X}$ deviates from $\mu$ with a variance $\frac{\sigma^2}{n}$, explained above.

Therefore, $X$ should deviate from $\mu$ with variance $\sigma^2 = \sigma_X^2 + \frac{\sigma^2}{n}$. Hence $\sigma^2 = \frac{n}{n-1} \sigma_X^2$, and by replacing $\sigma_X^2$ with $\sigma^2$,

$$
\sigma^2 = \frac{1}{n-1} \sum_{i=1}^{n} (X_i - \bar{X})^2
$$

# Combining multiple datasets

Consider 2 independent, non-overlapping datasets:

1. $X = \{X_1, X_2, ..., X_m\}$ with mean $\mu_1$ and standard deviation $\sigma_1$
2. $Y = \{Y_1, Y_2, ..., Y_n\}$ with mean $\mu_2$ and standard deviation $\sigma_2$

If we combine the 2 datasets together,

$$
\begin{aligned}
\mu_3 &= \frac{\mu_1 m + \mu_2 n}{m + n} \\
\sigma_3 &= \sqrt{\frac{m \sigma_1^2 + n \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m + n}}
\end{aligned}
$$

Or, for sample instead of population standard deviation,

$$
\sigma_3 = \sqrt{\frac{(m-1) \sigma_1^2 + (n-1) \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m + n - 1}}
$$

### Derivation

The mean of the combination of the 2 datasets

$$
\begin{aligned}
\mu_3 &= \frac{\sum_{z_i \in X \cup Y} z_i}{|X| + |Y|} & \text{Definition of mean} \\
&= \frac{(X_1 + \cdots + X_m) + (Y_1 + \cdots + Y_n)}{m + n} \\
&= \frac{m \mu_1 + n \mu_2}{m + n} & \mu_1 = \frac{\sum_{i=1}^{m} X_i}{m}, \therefore \sum_{i=1}^{m} X_i = m \mu_1
\end{aligned}
$$

The variance of the combination of the 2 datasets

$$
\begin{aligned}
\sigma_3^2 &= \frac{\sum_{z_i \in X \cup Y} (z_i - \bar{z})^2}{|X| + |Y|} \\
&= \frac{\sum_{z_i \in X \cup Y} z_i^2 - 2\bar{z}\sum_{z_i \in X \cup Y} z_i + \sum_{z_i \in X \cup Y} \bar{z}^2}{m + n} \\
\end{aligned}
$$

$$
\begin{aligned}
\sigma_1^2 &= \frac{\sum X_i^2}{m} - \mu_1^2 \\
\therefore \sum X_i^2 &= m(\sigma_1^2 + \mu_1^2) \\
\\
\sum_{z_i \in X \cup Y} z_i^2 &= \sum_{X_i \in X} X_i^2 + \sum_{Y_i \in X} Y_i^2 \\
&= m(\sigma_1^2 + \mu_1^2) + n(\sigma_2^2 + \mu_2^2) \\
\\
2\bar{z}\sum_{z_i \in X \cup Y} z_i  &= 2\mu_3\left(\sum_{X_i \in X} X_i + \sum_{Y_i \in Y} Y_i\right) \\
&= 2\mu_3(m \mu_1 + n \mu_2) \\
\\
\sum_{z_i \in X \cup Y} \bar{z}^2 &= (m + n)\mu_3^2 \\
\\
\therefore \sigma_3^2 &= \frac{m(\sigma_1^2 + \mu_1^2) + n(\sigma_2^2 + \mu_2^2) - 2\mu_3(m \mu_1 + n \mu_2) + (m + n)\mu_3^2}{m + n} \\
&= \frac{m\sigma_1^2 + n\sigma_2^2 + (m\mu_1^2 - 2\mu_3 m \mu_1  + m \mu_3^2) + (n\mu_2^2  - 2\mu_3 n \mu_2 + n \mu_3^2)}{m + n} \\
&= \frac{m \sigma_1^2 + n \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m+n}
\end{aligned}
$$

### Sources

- [Deriving the Mean and Variance of the Sample Mean](https://www.youtube.com/watch?v=7mYDHbrLEQo)
- [Proof that the Sample Variance is an Unbiased Estimator of the Population Variance](https://www.youtube.com/watch?v=D1hgiAla3KI)
- https://stats.stackexchange.com/questions/55999/is-it-possible-to-find-the-combined-standard-deviation
- https://stats.stackexchange.com/questions/3931/intuitive-explanation-for-dividing-by-n-1-when-calculating-standard-deviation


Posts