COMP9020 – Foundations of Computer Science

FINAL Exam – Term 3 2022

From Question 1 to Question 4

**With my own solution (might be incorrect)**



# Part 1

It seems that I can't prove this question perfectly.

It is confusing.

## 1.1

:::info{title="Question"}
Prove that for all $m,n,p ∈ ℕ$ :

If $lcm(m,p) = lcm(n,p)$, then $lcm(m+n,p) \le lcm(n,p)$.
:::

I can't prove it because I think it is incorrect. $lcm(m+n,p)$ should greater or equal $lcm(n,p)$.

The counter example is in Part 1.2



## 1.2

:::info{title="Question"}

Find a counter example to show that it is not the case that for all $m,n,p ∈ ℕ$ :

If $lcm(m,p) = lcm(n,p)$, then $lcm(m+n,p) = lcm(n,p)$.
:::

Assum:
- $m = 1$
- $n = 4$
- $p = 8$

Then:
- $lcm(m,p) = 8$
- $lcm(n,p) = 8$
- $lcm(m+n,p) = 40$

Therefore:

$lcm(m+n, p) \ne lcm(n,p)$


## 1.3

:::info{title="Question"}

Prove that for all $m,n,p ∈ ℕ$ :

If $lcm(m,p) = lcm(n,p)$, then $lcm(m+n,p) | lcm(n,p)$.
:::

# Part 2

## 2.1

:::info{title="Question"}

Prove, or find a counter example to disprove, for all sets A, B, C:

$A \cap (B \backslash C)^C=(A \cap C) \cap (A \cap B^C)$
:::

Definition of \\: $A\backslash B = A∩Bᶜ$:

$$
A \cap (B \backslash C)^C = A \cap (B \cap C^C)^C
$$

De Morgan's, C over ∩: $(A∩B)^C = A^C \cap B^C$:

$$
A \cap (B \cap C^C)^C = A \cap (B^C \cup C)
$$

Distributivity of ∩ over ∪: $A∩(B∪C) = (A∩B)∪(A∩C)$:

$$
A \cap (B^C \cup C) = (A \cap B^C) \cup (A \cap C)
$$

Therefore, it is incorrect.


## 2.2

:::info{title="Question"}
Let Σ = {0,1}.

Prove, or find a counter example to disprove that for all X,Y ⊆ Σ*:

$(X^*Y)^* \subseteq (X \cup Y)^*$
:::

Assum:

$(X^*Y)^* = w_1w_2...w_i$

Every element $w_i = x_{i1}x_{i2}...x_{ik}y_i$

and it could also be that:

$x_{i1}x_{i2}...x_{ik}y_i = (x_i \cup \empty)^* \cup (\empty \cup y_i) \subseteq (X \cup Y)^*$

Therefore, we could find that every element $w_i$ in string $(X^*Y)^*$ could be restructed by $(X \cup Y)^*$. 

Proved:

$$
(X^*Y)^* \subseteq (X \cup Y)^*
$$

# Part 3

Let F denote the set of all well-formed formulas.  Define the relation $R ⊆ F×F$ as follows:

$$
(\varphi, \psi) \in \mathbb{R} \text{ if and only if } (\varphi \rightarrow \psi) \text{ is satisfiable}
$$

## 3.1

:::info{title="Question"}
Prove that for all $\varphi, \psi \in F$,

If $\varphi \models \psi$ then $(\varphi, \psi) \in R$.
:::

Because $\varphi \models \psi$, when $\varphi$ is true, the $\psi$ is true. 

$$
\varphi \rightarrow \psi = \neg \varphi \lor \psi
$$

When $\varphi = true$, $\neg \varphi \lor \psi = true$.

When $\varphi = false$, $\neg \varphi \lor \psi = true$.

Because $\varphi \rightarrow \psi$ could be $true$, it means that $\varphi \rightarrow \psi$ is satisfiable.

Therefore, $(\varphi, \psi) \in R$.


## 3.2
:::info{title="Question"}
Prove or disprove:

R is reflexive

You may use the result of part (a) [without proof] if it helps
:::

If we want to prove that R is reflexive, we should prove that for every element $\varphi \in F$, $(\varphi, \varphi) \in R$.

It is easy to find that:

When $\varphi$ is $true$, $\varphi$ is $true$.

It means that:

$$
\varphi \models \varphi
$$

According to the result of part (a), if $\varphi \models \varphi$ then $(\varphi, \varphi) \in R$.

Therefore, we could prove that R is reflexive.

## 3.3

:::info{title="Question"}
Prove or disprove:

R is transitive

You may use the result of part (a) [without proof] if it helps
:::

Assum:

- $X \models Y$
- $Y \models Z$

According to the result of part (a), we could find that:

$$
(X,Y) \in R \\
(Y,Z) \in R
$$

Because $X \models Y$, $Y models Z$, when $X = true$, we could find that $Y = true$ and $Z = true$.

Therefore, we could find that $X \models Z$.

According to the result of part (a), we could find that:

$$
(X,Z) \in R
$$

Because:

$$
(X,Y) \in R \\
(Y,Z) \in R \\
(X,Z) \in R
$$

We could prove that R is transitive.


# Part 4

## 4.1

:::info{title="Question"}
Arrange the following functions in increasing order of asymptotic complexity (i.e. if f ∈ O(g) then f appears before g in the list

(For recursively defined functions, assume T(0) = T(1) = 1).

- $T(n) = T(n/2) + log(n)$
- $T(n) = 4T(n/4) + 4n$
- $T(n) = T(n - 2) + 2n$
- $T(n) = T(n/3) + \sqrt{3n}$
- $\sqrt[3]{n^2+2n-1}$
- $\frac{100}{n}+\frac{n}{100}$
:::

- $T(n) = T(n/2) + log(n)$

    Use Main Theorem, we could find that:
    $$
    a = 1 \\
    b = 2 \\
    f(n) = log(n) \\
    n^{log_ba} = n^{log_21} = n^0 = 1
    $$
    
    Because $f(n) = O(log(n)) = O(n^{log_21}log^1(n))$, we could prove that:
    
    $T(n) = O(n^{log_21}log^{1+1}(n)) = O(log^2(n))$.
    
- $T(n) = 4T(n/4) + 4n$

    Use Main Theorem, we could find that:
    $$
    a = 4 \\
    b = 4 \\
    f(n) = 4n \\
    n^{log_ba} = n^{log_44} = n^1 = n
    $$

    Because $f(n) = 4n = O(n) = O(n^{log_ba}log^0(n))$, we could prove that:
    
    $T(n) = O(n^{log_ba}log^{0+1}(n)) = O(nlog(n))$.
    
- $T(n) = T(n - 2) + 2n$

    Every time the $n$ decrease by 2. Therefore, the recursion time is $n/2$.
    
    Every recursion we have to execute $2n$ times.
    
    Therefore, $T(n) = \frac{n}{2} \times 2n = O(n^2)$.

- $T(n) = T(n/3) + \sqrt{3n}$

    Use Main Theorem, we could find that:
    
    $$
    a = 1 \\
    b = 3 \\
    f(n) = \sqrt{3n} \\
    n^{log_ba} = n^{log_31} = n^0 = 1
    $$
    
    Use Main Theorem Case 3, we could prove that:
    
    $T(n) = O(n^{0.5})$.

- $\sqrt[3]{n^2+2n-1}$

    We could find that:$\sqrt[3]{n^2+2n-1} = O(n^{2/3})$

- $\frac{100}{n}+\frac{n}{100}$

    We could find that: $\frac{100}{n}+\frac{n}{100}= O(n + 1/n) = O(n)$ 


This is the list of functions:

1. $O(log^2(n))$: $T(n) = T(n/2) + log(n)$
2. $O(n^{1/2})$: $T(n) = T(n/3) + \sqrt{3n}$
3. $O(n^{2/3})$: $\sqrt[3]{n^2+2n-1}$
4. $O(n)$: $\frac{100}{n}+\frac{n}{100}$
5. $O(nlogn)$: $T(n) = 4T(n/4) + 4n$
6. $O(n^2)$: $T(n) = T(n - 2) + 2n$

## 4.2


:::info{title="Question"}

Consider the function f:ℕ→ℕ defined as:

$$
f(n) = 3n + 2 \text{   (if n is even)} \\
f(n) = n^2 \text{   (if n is odd)}
$$

Which of the following properties does f satisfy?

Select all that apply:

- f∘f (n) = (f(n))² for all n
- f(n) ∈ O(n²)
- f is injective
- f(n) ≤ f(n+2) for all n
- f is surjective
- f(n) ≤ f(n+1) for all n
- f(n) ∈ O(n)
:::

Correct:

- f(n) ∈ O(n²)
- f is injective
- f(n) ≤ f(n+2) for all n

COMP9020 Sample Exam 2022 T3 Part 1

Test started Apr 17, 2024 6:00 PMtoApr 24, 2024 6:00 PM




## 1.1

### Question


A quiz consists of 10 multiple choice questions, each question has 4 options.  You score +1 for each correct answer, and -0.5 for each incorrect answer.

Suppose you choose an answer uniformly at random for each question.  What is your expected score?

Enter your answer to 2 d.p. (answers within ±0.01 will be marked correct)

### Answer

对于每一道题，有0.25的概率答对，0.75的概率答错，因此每一道题的期望得分是：

$$
E(X) = 0.25 \times 1 + 0.75 \times (-0.5) = -0.125
$$

对于每一道题，它的期望都是一致的。因此，十道题的得分期望是：

$$
E(X_1+...+X_10) = E(10 \times X_1) = 10\times E(X_1) = -1.25
$$

## 1.2

### Question

Suppose A, B, C, D are events with A⊥B, B⊥C and C⊥D.

True or false: It must be the case that D⊥A.

### Answer

当事件 A, B, C, D 之间存在相互独立的关系时，如 A⊥B, B⊥C, C⊥D，这只意味着某些特定事件之间独立。独立性不具有传递性，即如果事件 A 独立于事件 B，并且事件 B 独立于事件 C，这并不意味着事件 A 必然独立于事件 C。

同理，尽管 B 独立于 C，且 C 独立于 D，我们不能推断出 A 必然独立于 D，除非有额外的信息表明这种独立性成立。这种独立关系不是通过中介事件自动传递的。因此，没有具体证据表明 A 和 D 独立，我们不能假设它们独立。

FALSE

## 1.3

### Question

Suppose we have three urns with black and white balls distributed as follows:

- Urn A has 10 black balls and 20 white balls
- Urn B has 10 black balls and 10 white balls
- Urn C has 10 black balls and 1 white ball.

Suppose we choose an urn (uniformly at random) and draw a ball (uniformly at random) from that urn. What is the probability that the ball is white?

### Answer

分别计算。

1. 抽中A中的白球：

$$
\frac{1}{3} \times \frac{20}{30} = \frac{2}{9}
$$

2. 抽中B中的白球：

$$
\frac{1}{3} \times \frac{10}{20} = \frac{1}{6}
$$

3. 抽中C中的白球：

$$
\frac{1}{3} \times \frac{1}{11} = \frac{1}{33}
$$

总概率即：

$$
\frac{2}{9} + \frac{1}{6} + \frac{1}{33} = \frac{83}{198}
$$

## 1.4

### Question

Let P be a probability distribution, and A and B events such that P(A) ,P(B), P(A|B) and P(B|A) are all non-zero.

True or false: $P(A) = P(B)$ if and only if $P(A|B) = P(B|A)$

### Answer

我们可以来进行一下推理。


$$
P(A|B) = \frac{P(A \cap B)}{P(B)}
$$

$$
P(B|A) = \frac{P(B \cap A)}{P(A)}
$$

由于 所有变量均不为0，因此充分性和必要性都得以证明。

TRUE

## 2.1

### Question

True or false:

For any random variable X, the probability that X>E(X) is 1/2

### Answer

X可以是非对称分布。

FALSE

## 2.2

### Question

One way to simulate a die roll with a fair coin is as follows. Toss the coin three times:

- If the coin shows HHH: Output 1
- If the coin shows HHT: Output 2
- If the coin shows HTH: Output 3
- If the coin shows HTT: Output 4
- If the coin shows THH: Output 5
- If the coin shows THT: Output 6
- If the coin shows TTH or TTT: Repeat the process.

It was shown in lectures that each of the six outputs is equally likely, with probability 1/6.

A trial consists of three coin tosses. Note that if the coin shows TTH or TTT there will be more than one trial.

What is the expected number of trials before an output is produced?
Enter your answer to 3 d.p.s. An answer within ±0.001 will be correct.

### Answer

我们先对这个期望进行计算。

$$
E(X_n) = \sum_{i=1}^{∞} i \times \frac{6}{8} \times (\frac{2}{8})^{i-1} \\
=\sum_{i=1}^{∞} i \times \frac{3}{4} \times (\frac{1}{4})^{i-1} \\
=\sum_{i=1}^{∞} \frac{3i}{4^i} \\
=\sum_{i=1}^{∞} \frac{3(i-1) + 3}{4^{i-1} \times 4} \\
=\sum_{i=1}^{∞} \frac{1}{4} \times [\frac{3(i-1)}{4^{i-1}}+\frac{3}{4^{i-1}}] \\
=\frac{1}{4}\sum_{i=1}^{∞}\frac{3(i-1)}{4^{i-1}} + \frac{1}{4}\sum_{i=1}^{∞} \frac{3}{4^{i-1}} \\
=\frac{1}{4}E(X_n)+3 \times \sum_{i=1}^{∞}\frac{1}{4^i}
$$

这个几何级数 $\sum_{i=1}^{∞}\frac{1}{4^i}$ 收敛于 $\frac{1}{3}$。因此，原式可表达为：

$$
E(X_n) = \frac{1}{4}E(X_n) + 3 \times \frac{1}{3}
$$

计算得到：

$$
E(X_n) = \frac{4}{3}
$$

另外，GPT给出了一种更简单的证明思路：

![image.png](/static/img/c902fc38f4b6f4763c7282bdc645f683.image.webp)

因此，答案为：

1.333

## 2.3

### Question

Suppose two normal, six-sided dice are rolled, a red die and a black die.

Let:

- A be the event that both dice show 4 or higher;
- B be the event that the red die shows 4 or lower; and
- C be the event that the black die shows 4.

True or false: A and (B∩C) are independent events.

### Answer

判断是否为独立事件，最简单的方法就是判断它们同时发生的概率是否等于它们各自发生的概率的乘积，即：

$$
P(A \cap (B \cap C)) = P(A) \times P(B \cap C)
$$

首先我们可以意识到，B和C确实是独立事件，它们是不同的骰子，因此互不影响。

$$
P(A) = \frac{3}{6} \times \frac{3}{6}= \frac{1}{4}
$$

$$
P(B) = \frac{4}{6} = \frac{2}{3}
$$

$$
P(C) = \frac{1}{6}
$$

因此，我们可以得到：

$$
P(B \cap C) = \frac{2}{3} \times \frac{1}{6} = \frac{1}{9}
$$

同时，我们可以注意到，A、B、C同时发生时，需要两个骰子都显示4。

则：

$$
P(A \cap (B \cap C)) = \frac{1}{6} \times \frac{1}{6} = \frac{1}{36} = P(A) \times P(B \cap C)
$$

因此，答案为：

TRUE

## 2.4

### Question


You are in a maze with 4 rooms. To navigate the maze you decide to wander randomly with the following strategy:

- In room A you will exit with probability 1/3, move to room B with probability 1/3, and move to room C with probability 1/3.
- In room B you will move to room D with probability 1/3, and room A with probability 2/3.
- In room C you will move to room D with probability 2/3, and room A with probability 1/3.
- In room D you will exit with probability 1/3, move to room B with probability 1/3, and move to room C with probability 1/3.

Starting from Room A, what is the probability that you will exit the maze from Room D?

Enter your answer to 3 d.p.s. An answer within ±0.001 will be correct.

### Answer

我们设置：$P_X$ 为从房间 $X$ 开始逃脱的概率。

我们直接将从A离开的可能性置为0（因为它没有去任何其他的房间），从D离开的可能性置为1（我们要找的）。

那么：

$$
P_A = \frac{1}{3} \times 0 + \frac{1}{3} P_B + \frac{1}{3} P_C
$$

$$
P_B = \frac{2}{3} P_A + \frac{1}{3} P_D
$$

$$
P_C = \frac{1}{3} P_A + \frac{2}{3} P_D
$$

$$
P_D = \frac{1}{3} \times 1 + \frac{1}{3} \times P_B + \frac{1}{3} \times P_C
$$

联立方程代入解得 $P_A = \frac{1}{3} = 0.333$

COMP9020 Quiz 9

- Random Variables and Expectations
- Linearity of Expectation
- Expected Time to Success
-  Standard Deviation and Variance



# 随机变量与期望 Random Variables and Expectatiions

## 随机变量

整数随机变量X是一个从 $ Ω $ 到 $ ℤ $ 的函数。换句话说，它将每一个结果都与一个数值关联起来。

- 随机变量通常用 X, Y, Z 等字母表示。
- 我们以自然的方式将算术运算扩展到随机变量上。

给定随机变量 $X: Ω → ℤ$ 和随机变量 $Y: Ω → ℤ$ 以及整数 $k$，我们可以将 X、Y 和 k 组合起来，得到以下在所有 $ω ∈ Ω$ 上的函数：

- 变量加法：$X + Y ：ω ↦ X(ω) + Y(ω)$
- 变量乘法：$X · Y ：ω ↦ X(ω) · Y(ω)$
- 标量加法：$X - k ：ω ↦ X(ω) - k$
- 标量乘法：$kX ：ω ↦ k · X(ω)$

![image.png](/static/img/f57e86fa1a3c2b75211e040e50f29945.image.webp)

## 期望

随机变量 X 的期望值（通常称为“期望”或“平均值”）是通过下面的公式计算的：

$$
E(X) = \sum_{k \in Z}P(X=k) \times k
$$

期望是一个真正普遍的概念；它是所有决策、估计盈亏、在风险下行动的基础。在概率论概念出现之前，期望值这一基本概念就已经存在了。


# 期望值的线性 Linearity of expectation

对于任意随机变量 X 和 Y，以及整数 k，有：

- $E(X+Y) = E(X) + E(Y)$
- $E(k \times X) = k \times E(X)$

![image.png](/static/img/3261f8215dfd47b23f4531ecdd927941.image.webp)

## 观察可得 Observations

如果 $X_1$，$X_2$，...，$X_n$ 是独立同分布的随机变量，那么：

$$
E(X_1+X_2+...+X_n) = E(nX_1) = nE(X_1)
$$

当随机变量独立同分布时，它们和的期望值等于任意一个随机变量期望值的n倍。

尽管 $X_1+X_2+...+X_n$ 与 $nX_1$ 期望值相同，但这两个表达式代表的随机变量本身是非常不同的。

![image.png](/static/img/576a4c257fe0aa75721be06467249c64.image.webp)


# 成功的期望时间 Expected Time to Success

几何级数 & 递归

![image.png](/static/img/d67fa39d432e275dafd6cc8e0e62dbf7.image.webp)

一个更简单但同样有效的论证是，你预期在一次抛掷中得到“一半”的正面，所以你应该期望在两次抛掷中得到一个“完整”的正面。

## 成功与期望值

问题：高成功概率是否导致高期望值？

一般来说，不是这样。例如：

- 购买更多的彩票可以增加中奖的机会，但是中奖的期望却降低了。

## 赌徒陷阱 Gambler's ruin

很多所谓的“获胜系统”声称提供一个获胜策略，实际上它们提供了一个频繁获得适度胜利的方案，但代价是偶尔会有非常大的损失。

事实上，有一个正式的定理表明，没有任何系统可以将一个“不公平”的游戏转变为一个“公平”的游戏。在决策理论中，“不公平”指的是那些每个个别投注都有负期望值的游戏。

很容易验证，无论是在轮盘赌上的个别投注，购买彩票，或者任何商业提供的游戏上的投注，都具有负的期望值。


# 标准差与方差

对于随机变量X，其期望值为 $μ = E(X)$，标准差为：

$$
\sigma = \sqrt{E((X-μ)^2)}
$$

方差为：

$$
\sigma^2
$$

标准差和方差度量了随机变量的值分散程度。方差越小，我们越能确信对于随机选择的 $ω$，有：

$$
X(ω) = E(X)
$$

并且，方差可以计算为：

$$
E((X-μ)^2) = E(X^2) - μ^2
$$

![image.png](/static/img/877297034b87be3d2de1850da18bef9a.image.webp)

COMP9020 10.1 Statistics

quiz8



## 1.1

### Question

In a class of 200:

- 80 are funny
- 130 are clever
- 42 are neither funny nor clever
How many are both funny and clever?

### Answer


$$
|F \cup C| = |F| + |C| - |F \cap C|
$$

因此，答案为：52

## 1.2

### Question

How many integers are there between 1 and 1000 which are divisible by 6 or 15 but not both?

### Answer
$$
|A \cup B| = |A| + |B| - |A \cap B|
$$

- 集合A的大小，即1到1000之间可以被6整除的数的数量。（199）
- 集合B的大小，即1到1000之间可以被15整除的数的数量。（66）
- 集合A和B的交集的大小，即1到1000之间可以被30整除的数的数量。（33）


因此，答案为：166（因为33被计算了两次，所以199+66-33*2）

## 1.3

### Question

Let S be a set of size n, and fix a constant k>1 (i.e k does not depend on n). Which of the following gives the best asymptotic upper bound for the number of subsets of S of size k?

### Answer

集合不考虑顺序，因此只需要在n里选出k个元素，即 $(^n_k)$。

$$
(^n_k)=\frac{(n-k)!}{k!}
$$

同时，由于k是常数，所以直接忽略。且：$(n-k)! \rightarrow O(n^k)$

因此，答案为：$O(n^k)$。

## 1.4

### Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability they are both blue?

### Answer

第一个球是蓝球的概率是4/9，满足第一次的情况下出现第二个蓝球的概率是4-1/9-1=3/8

因此，答案为：1/6

## 2.1

### Question

How many ways are there of choosing an ordered sequence of three letters (with no replacements) from 'SYDNEY'?

### Answer

计算三个字母的有序序列的总数，我们需要分四种情况来考虑：

- 序列中没有"Y"。
- 序列中有一个"Y"。
- 序列中有两个"Y"。

第一种情况，我们要从"SDNE"中选择三个，并组成有序序列，共有：$C_4^3 \times A^3_3 = 4 \times 6 = 24$。

第二种情况，我们要从"SDNE"中选择两个，并和另一个Y组成有序序列，共有：$C_4^2 \times A_3^3 = 6 \times 6 = 36$。

第三种情况，我们要从"SDNE"中选择一个，和另外两个"Y"组成有序序列。两个Y构成插槽，因此实际上该字母能选择位置只有3个，共有：$C_4^1 \times 3 = 12$。


因此，答案为：72


## 2.2

### Question

How many sequences of 2n coin flips have exactly n heads and n tails?

### Answer

我们只需要考虑，在这2n个硬币中，选择n个正面朝上即可，我们不需要考虑它的顺序或者别的东西。

因此，答案为：$(^{2n}_n)$

## 2.3

### Question

How many ways are there of placing 6 indistinguishable balls into 3 distinguishable boxes so that each box contains at least 1 ball?

### Answer

六个球是等价的，三个盒子不等价。我们可以先在每个盒子中都放一个球，把问题转化为：

现在有3个球，放入三个不同的盒子中，有几种放法？

有三种情况：

1. 三个球在一个盒子里（3种）
2. 有一个盒子是空的，另外两个盒子2&1分布（3*2）
3. 三个球在三个盒子里（1种）

因此，答案为：10

## 2.4

### Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability that the second ball is blue, given that the first ball is blue?

### Answer

感觉跟前面那题没区别，答案为3/8

COMP9020 Quiz 8

- Elementary Discrete Probability
- Independence
- Infinite Sample Spaces
- Recursive Probability Computations
- Conditional Probability
- Independence, revisited



# 初等离散概率 ELementary Discrete Probability

## 初等概率 Elementary Probability

### 概念定义

1. 样本空间（Sample Space）：包含所有可能结果的集合，每一个元素代表一个可能的结果。
$$
Ω = \{ω₁, ..., ωₙ\}
$$
2. 事件（Event）：是结果的集合，是样本空间的子集。
3. 概率分布（Probability Distribution）：是一个函数 $P: Pow(Ω)→ ℝ$，满足：

$$
P(Ω)=1 \\
\text{如果事件E和F不相交（互斥），那么} P(E ∪ F) = P(E) + P(F)
$$

### 基本事实

- $P(∅) = 0$，意味着一个不可能事件的概率是0。
- $P(Eᶜ) = 1 - P(E)$，其中 $Eᶜ$ 是 $E$ 的补事件，这表示事件 $E$ 不发生的概率。

![image.png](/static/img/fbac1f83a1a492c9cb725933ceba167a.image.webp)

## 均匀分布 Uniform Distribution

在均匀概率分布中，样本空间Ω中的每个结果ωᵢ都是等可能的。具体地，对于样本空间Ω中的每个结果ω₁, ω₂, ..., ωₙ，它们发生的概率相同，用概率论的术语表示为：

$$
P(ω₁)=P(ω₂)= ... = P(ωₙ) = \frac{1}{n}
$$

这称为样本空间Ω上的均匀概率分布。在这种分布下，每个单独事件发生的概率是相等的，这是一个在理想化的公平游戏或者是理想情况下的随机实验中常见的分布。

## 通过计数计算概率 Computing Probabilities by Counting

![image.png](/static/img/afed460539e8b039297147367b77f955.image.webp)

在没有其他资料的情况下，"随机选择"这个表述通常意味着"根据均匀分布"进行选择。这意味着每个可能的结果都有相同的概率发生。

大多数计数规则可以直接转换为关于均匀分布的概率。这是因为在均匀分布下，概率直接与样本空间中特定事件的数量相关联。

## 组合事件 Combining Events

通过组合简单事件来构造复杂事件：

- 事件A和事件B同时发生：使用交集符号表示，即 $A \cap B$。
- 事件A或事件B发生（至少一个发生）：使用并集符号表示，即 $A \cup B$。
- 事件A不发生：使用补集符号表示，即 $ \Omega \backslash A$。
- 事件A发生后事件B发生：这通常涉及条件概率或序列事件，可能用其他概率规则来描述。

前三种构造涉及到来自同一样本空间的事件，而最后一种可能涉及来自不同样本空间的事件（例如先掷骰子再抛硬币）。

![image.png](/static/img/d207d6131dfedb240ea707b150fca3f6.image.webp)


# 独立事件 Independence

## 统一不同集合的结果 Unifying sets of outcomes

- 抛硬币的样本空间可以表示为 $\Omega_1 = \{heads, tails\}$
- 掷骰子的样本空间可以表示为 $\Omega_2 = \{1, 2, 3, 4, 5, 6\}$


这两个活动可以结合起来创建一个新的样本空间 $\Omega = \Omega_1 \times \Omega_2$，包括所有可能的组合。

这种方法也可以用来建模结果序列。这意味着它不仅仅用于单次事件，还可以用于表示一系列连续事件的所有可能结果。这种方法在多阶段实验中非常有用，其中每个阶段都可能有不同的结果集。

## 乘积分布 Product Distribution

$$
P(E_1 \times E_2 \times ... \times E_n) = P_1(E_1) \times P_2(E_2) \times ... \times P_n(E_n)
$$

表示在一个维度上的事件的概率不会受到其他维度上结果的影响。这个性质是独立性的体现，它是说在乘积空间中的事件发生的概率是各自独立事件概率的乘积。

## 独立性 Independence

### 非正式定义

事件被认为是独立的，如果一个事件的结果不影响另一个事件的结果。

### 正式定义

如果两个事件，事件A和事件B，同时发生的概率等于各自发生概率的乘积，那么它们被称为（随机）独立的（记作 $A⊥B$ ）。

$$
P(A \cap B) = P(A)P(B)
$$

除非另有说明，当我们在统一事件时（在适当的情况下），我们假设事件是独立的。这个假设是为了简化问题分析，因为在实际应用中，事件的独立性往往需要明确指出或由问题的背景决定。

### 全独立性与成对独立性

- 全独立性 Full Independence：所有事件之间都相互独立，它们同时发生的概率等于它们各自发生概率的乘积。
- 成对独立性 Pairwise Independence：相对更弱，它只要求每对事件之间相互独立，而不是要求所有事件之间。

例如，考虑两次抛硬币的实验：

1. 事件A：第一次抛硬币得到正面（H）
2. 事件B：第二次抛硬币得到正面（H）
3. 事件C：两次抛硬币中恰好一次得到正面（H）

虽然A和B是独立的，A和C是独立的，B和C也是独立的（即所有的成对事件独立，$P(A) = P(B) = P(C) = \frac{1}{2}$， 且 $P(A∩B) = P(A∩C) = P(B∩C) = \frac{1}{4}$），但事件A、B和C并不是全独立的，因为 $P(A∩B∩C) = 0 \ne P(A)·P(B)·P(C)$。

这个例子说明了成对独立性并不总是蕴含全独立性。而且还可以构造一组n个事件，其中任意k个是独立的，但任意k+1个就不是独立的（$k < n$）。

## 二项分布 Binomial Distribution

在一系列的n个独立试验中，每次试验成功的概率为p，那么恰好有k次成功的概率可以用下面的公式来表示：

$$
P = (_k^n)p^kq^{n-k} \\
q = 1 - p
$$

这种概率分布模式被称为二项分布。二项分布是离散概率分布的一个重要例子，常用于描述固定数量独立试验中成功次数的概率。这里的“成功”可以指任何感兴趣的二分结果，例如抛硬币得到正面或者负面，测试结果为阳性或阴性等。


# 无穷样本空间 Infinite Sample Spaces

在连续空间中（例如实数 ℝ）：

- 概率分布被视为度量（measures）。
- 求和操作通过积分来完成。
- 非零概率适用于范围而不是单点。
- 单个事件的概率是0，但这并不意味着该事件是不可能的，因为在连续空间中，有无限多个可能的结果。

在离散空间中（例如自然数 ℕ）：

- 概率为0确实意味着某个事件是不可能的。
- 不存在均匀分布，因为不能给无限个事件赋予相同的非零概率，使它们的总和为1。
- 非均匀分布是存在的。例如，可以有一个分布，其中 $P(0) = 1$ 而所有 $P(n) = 0（n > 0）$，或者分布 $P(0) = 0, P(n) = \frac{1}{2^n} (n > 0)$。
- 在某些情况下，如果合理的话，可以考虑极限概率。


# 递归概率计算 Recursive Probability Computations

- H: Head，正面。
- T: Tail，反面。

![image.png](/static/img/807f5a65fe1d4d6e75ba1ff02faa5549.image.webp)


![image.png](/static/img/f5199593a97da6813e5d4370f999205c.image.webp)


![image.png](/static/img/894be6546a9ec589b228382a85973393.image.webp)

大多数概率和统计问题没有简洁优雅的解决方案。因此，使用计算机进行精确计算或近似模拟变得必不可少。然而，递归的使用简化了这样的计算，或者很多时候，使这样的计算成为可能。递归是指自己调用自己的函数，这在处理复杂的概率计算时特别有用，尤其是在可以将问题分解成更小、更简单的子问题时。


# 条件概率 Conditional Probability

事件E在事件S已经发生的条件下发生的概率，记为 $P(E|S)$，定义为：

$$
P(E|S) = \frac{P(E \cap S)}{P(S)}
$$

条件概率只有在 $P(S) \ne 0$ 时才有定义。


:::note{title="注"}
通常， $P(A|B)$ 和 $P(B|A)$ 之间可以说完全没有关系，知道一个并不能告诉我们关于另一个的任何信息。
:::

## 基本事实

- $A \subseteq B \rightarrow P(A|B) \le P(A)$：在事件B发生的条件下事件A发生的概率至少和A无条件发生的概率一样大。
- $A \subseteq B \rightarrow P(B|A) =1$：如果事件A发生了，那么事件B肯定发生。
- $P(A \cap B | B) = P(A | B)$
- $A \ne \empty \rightarrow P(\empty | A) = 0$：对于非空事件A，在事件A发生的条件下，不可能事件发生的概率是0。
- $P(A|\Omega) = P(A)$：在整个样本空间发生的条件下事件A发生的概率就是事件A本身的概率。
- $P(A^C|B) = 1-P(A|B)$：事件A在B发生的条件下不发生的概率等于1减去A在B发生的条件下发生的概率。

:::note{title="注"}
$P(A|B)$ 和 $P(A|B^C)$ 之间通常不相关。知道了在B发生的条件下A的概率，并不能告诉我们在B不发生的条件下A的概率。
:::

### 独立性与条件概率

假设事件A和事件B时随即独立的，即：

$$
P(A \cap B) = P(A)P(B)
$$

如果 $P(A) \ne 0, P(B) \ne 0$，那么下列陈述完全等价：

- $P(A \cap B) = P(A)P(B)$
- $P(A|B) = P(A)$
- $P(B|A) = P(B)$
- $P(A^C|B) = P(A^C)$
- $P(A|B^C) = P(A)$
- $P(A^C|B^C) = P(A^C)$

如果A和B独立，则A的补集和B独立，A和B的补集独立，A的补集和B的补集也独立。即：如果两个事件A和B独立，它们的补集之间的关系也是独立的。