<jupyter_start><jupyter_text>Probability Theory  Week 1**Topics:** Random sampling, permutations, combinations.**Problems:** 3.1, 3.3, 3.4, 3.5, 3.6, additional problem set 1.  Random samplingTaking a random sample can be done in different ways:||With replacement|Without replacement||---|---|---||**With order**|$n^k$|$n!, \quad k \leq n$||**Without order**|$\begin{pmatrix}n+k-1\\k\end{pmatrix}$|$\begin{pmatrix}n\\k\end{pmatrix}$|This leads to four different cases which will be addressed seperately.  Permutations The general formula for permutations is:$$ _nP_k = \dfrac{n!}{(n-k)!}$$  With replacement  Without replacement  Combinations The general formula for combinations is (which can also be written as the binomial coefficient):$$ _nC_k=\dfrac{n!}{k!(n-k)!} = \begin{pmatrix}n\\k\end{pmatrix}$$  With replacement  Without replacement  Week 2**Topics**: Probability definitions, probability rules, grid chart.**Problems:** 3.7, 3.8, 3.10, additional problem set 2.  Probability definitions  Probability experimentThere are different examples of probability experiments:1. One throw with a dice2. Two throws with a dice3. One throw with a coin4. Pulling two cards from a deck of cards  Sample spaceThe sample space $\Omega$ are all the possible outcomes for a probability experiment. For the above given examples this gives:1. $\Omega=\{1,2,3,4,5,6\}$2. $\Omega=\{(a,b):a,b \in \{1,2,3,4,5,6\}\}$3. $\Omega=\{H,T\}$4. $\Omega=\{(a,b):a,b \in \{1,\ldots,52\}\}$  EventAn event is a subset of $\Omega$.1. Throwing an even number, $A=\{2,4,6\}$2. Throwing the same dices, $A=\{(1,1),(2,2),\ldots,(6,6)\}$3. Throwing heads, $A=\{H\}$4. Picking a heart A ($HA$) and club 2 ($C2$), $A=\{(HA,C2),(C2,HA)\}$  Elementary eventAn elementary event $\omega$ (also called atomic event) is exactly one element from $\Omega$.For example (1) all the elementary events are: $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{5\}$, $\{6\}$.  Probability (axiomatic definition)For the probability function $P$ the following three axioms hold:1. $P(S)=1$2. $0\leq P(A) \leq 1$3. $P(A \cap B) = P(A)+P(B)-P(A \cap B)$, where $P(A \cap B) = 0$ if and only if $A \cap B = \emptyset$.  Probability spaceA probability space consists of the following:1. A sample space $\Omega$ which are all the possible outcomes for the experiment.2. A set of events, where each event is a set containing zero or more outcomes.3. The assigment of probabilities to the events; that is, a function $P$ from events to probabilities.With this we can determine the probability for an event $A$:$$P(A) = \dfrac{n_a}{n_\Omega}$$Where $n_a$ are the favorable outcomes and $n_\Omega$ are all the possible outcomes.  Probability rules Now we establish a few rules for probabilites. Later on when we cover conditional probilities we will add a few more rules to the list. Sum rule$P(A \cup B) = P(A)+P(B)-P(A \cap B)$ where $P(A \cap B) = 0$ if and only if $A \cap B = \emptyset$. Complement ruleWe can define this as $P(A) + P(\bar{A}) = P(S) = 1$. We use this to infer that $P(A) = 1-P(\bar{A})$. This is particularly useful because most of the times it is a lot easier to figure out what $P(\bar{A})$ is, and then use the complement rule to determine the probability of $P(A)$.  Grid chartA grid chart is useful to visualize conditions.For example, suppose we want to throw $2$ dices, and we multiply the outcome. What is the probability that the result is greater than $20$?![Grid chart](grid-example.png)Using the grid chart it is easy to see that:$$P(x>20) = \frac{6}{6^2} = \frac{1}{6}$$  Week 3**Topics:** Conditional probability, independence, product rule, sampling with replacement, sampling without replacement, probability tree.**Problems:** 3.2, 3.12, 3.13, 3.14, 3.15, 3.16, additional problem set 3.  Conditional probability A conditional probability gives more information about the possible outcome space, which is defined as:$$P(A|B) = \dfrac{P(A \cap B)}{P(B)} ,\quad P(B)>0$$  Indepence If $P(A|B)=P(A)$ then the events $A$ and $B$ are independent.  Product rule The general product rule is:$$ P(A \cap B) = P(A|B) \cdot P(B) = P(B|A) \cdot P(A) $$In the case that $A$ and $B$ are independent, we use:$$ P(A \cap B) = P(A) \cdot P(B)$$  Probability rules With the addition of above rules, we now have the following rules for probabilities:1. $P(\Omega)=1$, sample space has a probability of 1.2. $P(\emptyset)=0$, an empty set has a probability of 0.3. $P(A)=1-P(\bar{A})$, complement rule.4. $P(A\cup B)=P(A)+P(B)-P(A\cap B)$, sum rule.5. $P(A\cup B)=P(A)+P(B)$, if and only if $A\cap B=\emptyset$.6. $P(A\cap B)=P(A|B)\cdot P(B)$, product rule.7. $P(A\cap B)=P(A)\cdot P(B)$, if and only if $A$ and $B$ are independent.  Sampling with replacement  Sampling without replacement  Probability tree  Week 4**Topics:** Bayes' rule.**Problems:** 3.9, 3.11, 3.17 till 3.31.  Bayes' rule  InferenceWhen we have a cause and effect model where $A_i\xrightarrow[P(B|A_i)]{\text{cause-effect}}B$ is known, we can use Bayes' rule to infer $B\xleftarrow[P(A_i|B)]{\text{inference}}A_i$. **General case**The general use case for Bayes rule is:$$ P(A|B) = \dfrac{P(A) \cdot P(B|A)}{P(A)\cdot P(B|A) + P(\bar{A})\cdot P(B|\bar{A})} $$We can use this to infer $P(A|B)$ if only $P(B|A)$ is known.**Definition**Bayes' rule is defined as:$$ P(A_i|B) = \dfrac{P(A_i)\cdot P(B|A_i)}{\sum\left[P(A_j)\cdot P(B|A_j)\right]}$$such that the following holds:1. $A_i \cap A_j = \emptyset $, the intersection must be disjunct.2. $\cup A_i = \Omega$, the union of $A$ is $\Omega$.  Week 5**Topics:** Discrete stochastic variable, discrete probability function, cumulative distribution function, expected value, variance for a discrete stochastic variable.**Problems:** 4.1, 4.3, 4.4, 4.5, 4.6, 4.7, 4.8  Stochastic variables **Definition**Given a sample space $\Omega$ and a function $\underline{k}$ such that $\underline{k}:\Omega\rightarrow\mathbb{R}$. Where the range is $\underline{R}_k \subset \mathbb{R}$. In this context $\underline{k}$ is the stochastic variable (or probability variable). With the following two rules:1. $f(k) \geq 0$ for $\forall k$2. $\sum f(k) = 1, \quad \left(\sum\limits_{k\in\underline{k}}(\underline{k}=k)=1\right)$**Example**Given a probability experiment: throwing with a dice.We define $\underline{k}$ as the squared outcome of the throw. The mapping of the function $\underline{k}$ is defined as:$$\Omega=\underbrace{\{1,2,3,4,5,6\}}_{\text{domain}} \xrightarrow{\underline{k}} \underbrace{\{1,4,9,16,25,36\}}_{\text{range}} = \underline{R}_k \subset \mathbb{R}$$  Discrete probability distributionThe probability distribution is defined as $f(k)=P(\underline{k}=k)$ such that $k\in\underline{R}_k$. For the above given example this yields:$$ f(1)=P(\underline{k}=1)=\dfrac{1}{6} \\ f(4)=P(\underline{k}=4)=\dfrac{1}{6} \\ \vdots \\ f(36)=P(\underline{k}=36)=\dfrac{1}{6}$$ **Code**<jupyter_code>def f(k):
    r = [1,4,9,16,25,36]
    if k in r: return 1/len(r)
    return 0<jupyter_output><empty_output><jupyter_text>Plotting this function gives a pin bar graph with a vertical line at the value when there is a probability defined. All the other values are not defined because this is a discrete function.<jupyter_code>points = np.arange(0,37,0.01)
plot(points, [f(x) for x in points], c='b', lw=2);<jupyter_output><empty_output><jupyter_text>Cumulative distribution functionThe cumulative distribution function $F(k)=P(\underline{k}\leq k)$ for the example above yields:$$ F(1)=P(\underline{k}\leq1)=\dfrac{1}{6} \\ F(2)=P(\underline{k}\leq2)=\dfrac{1}{6} \\ F(4)=P(\underline{k}\leq4)=\dfrac{2}{6} \\ \vdots \\ F(36)=P(\underline{k}\leq36)=\dfrac{6}{6}=1$$ **Code**<jupyter_code>def F(k):
    x = 0
    r = [1,4,9,16,25,36]
    for i in r: 
        if i <= k: x = i
    try: return (r.index(x)+1)/len(r)
    except: return 0<jupyter_output><empty_output><jupyter_text>Plotting this function gives a staircase graph.<jupyter_code>points = np.arange(-10,50,0.01)
plot(points, [F(x) for x in points], c='b', lw=2);<jupyter_output><empty_output><jupyter_text>Expected value of a discrete stochastic variableThe expected value $E(\underline{k})$ is the weighted arithmetic mean from descriptive statistics but altered for a stochastic variable.**Definition**The formula for the expected value is:$$ E(\underline{k})=\sum\limits_{k\in\underline{k}} k\cdot P(\underline{k}=k) $$Notice that we do not divide by the sum of values since that sum would equal 1, hence it's omitted.**Example**The expected value for the example with a dice is:$$E(\underline{k})=1 \cdot \dfrac{1}{6} + 4 \cdot \dfrac{1}{6} + 9 \cdot \dfrac{1}{6} + 16  \cdot \dfrac{1}{6} + 25 \cdot \dfrac{1}{6} + 36 \cdot \dfrac{1}{6} = \dfrac{91}{6} = 15 \dfrac{1}{6}$$ **Code**<jupyter_code>def E(r): 
    return sum([x * 1/len(r) for x in r])<jupyter_output><empty_output><jupyter_text>We can use this to easily determine the expected value for any range of $\underline{k}$ when there is a uniform distribution.<jupyter_code>expected = E([1,4,9,16,25,36])
expected<jupyter_output><empty_output><jupyter_text>Plotting $f(k)$, $F(k)$, and $E(\underline{k})$ yields:<jupyter_code>points = np.arange(0,50,0.01)
plot(points, [f(x) for x in points], c='lightblue', lw=2);
plot(points, [F(x) for x in points], c='b', lw=2);
scatter(expected, F(expected), c='r', lw=4);<jupyter_output><empty_output><jupyter_text>Variance of a discrete stochastic variable The variance $\text{Var}(\underline{k})$ is the variance from descriptive statistics but is altered for a discrete stochastic variable.**Definition**The formula for the variance of a discrete stochastic variable is defined as:$$ \text{Var}(\underline{k}) = \sum\limits_{k\in\underline{k}}\left(k-E(\underline{k})\right)^2\cdot P(\underline{k}=k_i) $$Notice that we do not divide by the sum of probabilities since that sum would equal 1, hence it's omitted.**Example**An example for throwing a dice gives:$$\text{Var}(\underline{k})= \left(1-\dfrac{91}{6}\right)^2 + \left(4-\dfrac{91}{6}\right)^2 + \ldots + \left(36-\dfrac{91}{6}\right)^2 = 149.14$$**Standard deviation**With the example given above, it is easy to determine the standard deviation, which is:$$\sigma_{\underline{k}} = \sqrt{149.14} = 12.21$$**Alternative method**An alternative (preferred) method to calculate the variance of a discrete stochastic variable is:$$\text{Var}(\underline{k})= E(\underline{k}^2)-\left[E(\underline{k})\right]^2$$Proof:We start with the definition:$$\begin{align} &\sum\limits_{k\in\underline{k}}\left(k-E(\underline{k})\right)^2 \cdot P(\underline{k}=k) \\ = &\sum\limits_{k\in\underline{k}}\left(k^2 - 2k\cdot E(\underline{k})+\left[E(\underline{k})\right]^2 \right) \cdot P(\underline{k}=k) \\ = & \underbrace{\sum\limits_{k\in\underline{k}}k^2\cdot P(\underline{k}=k)}_{\text{def.}\ E(\underline{k}^2)}-2\sum\limits_{k\in\underline{k}}k\cdot E(\underline{k})\cdot P(\underline{k}=k)+\sum\limits_{k\in\underline{k}}\left[E(\underline{k})\right]^2\cdot P(\underline{k}=k) \\ = &E(\underline{k}^2) - 2\cdot E(\underline{k}) \cdot \underbrace{\sum\limits_{k\in\underline{k}} k \cdot P(\underline{k}=k)}_{\text{def.}\ E(\underline{k})} + \left[E(\underline{k})\right]^2 \cdot \underbrace{\sum\limits_{k\in\underline{k}} P(\underline{k}=k)}_{1} \\ = &E(\underline{k}^2)-2\cdot E(\underline{k})\cdot E(\underline{k})+\left[E(\underline{k})\right]^2 \\ = & E(\underline{k}^2) - \left[E(\underline{k})\right]^2 \end{align}$$Which proves our formula. **Code**<jupyter_code>def var(r):
    expected = E(r)
    return sum([(x-expected)**2*f(x) for x in r])
var([1,4,9,16,25,36])
def var2(r):
    return E([x**2 for x in r]-E(r)**2)
var2([1,4,9,16,25,36])
def stdev(r):
    return math.sqrt(var2(r))
stdev([1,4,9,16,25,36])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18577277379733878, 'fraction_numerical': 0.03207096554077107, 'mean_word_length': 5.0344827586206895, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '85745', 'license': 'Unlicense', 'n_tokens_mistral': 4241, 'n_tokens_neox': 3945, 'n_words': 1261, 'path': 'Applied Math/Y1S2/.ipynb_checkpoints/Probability Theory-checkpoint.ipynb', 'repo_name': 'darkeclipz/jupyter-notebooks', 'size': '11724'}