COMP6991 FINAL EXAM 22T3

COMP6991 PRAC EXAM 22T3

COMP9020 – Foundations of Computer Science

FINAL Exam – Term 3 2022

From Question 5 to Question 10

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



# Question 5

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

## 5.1

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

G has an Eulerian path
:::

Here is the degree list for all of the vertices:

- vertex 0: 3
- vertex 1: 2
- vertex 2: 2
- vertex 3: 4
- vertex 4: 4
- vertex 5: 2
- vertex 6: 2
- vertex 7: 3

We could find that there are 2 vertices (0 and 7) whose degree is odd. This could prove that there is an Eulerian path in G.

For example:

0 → 2 → 3 → 1 → 0 → 4 → 5 → 7 → 6 → 4 → 3 → 7

## 5.2

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

G has a Hamiltonian cycle
:::

If it has a Hamiltonian cycle, it means that no matter which vertex I start, I could find a cycle. Because this cycle should get every vertex.

Divide these vertices into 2 subsets: {0, 1, 2, 3} and {4, 5, 6, 7}. Edges (0, 4), (3, 4) and (3, 7) are linking these 2 subsets.

Set start point at vertex 1, and we could go to vertex 0 or vertex 3.

If we go to vertex 0, we could go to vertex 2 or vertex 4 for next step.

If we go to vertex 2, we must go to vertex 3 for next step, but it means that we could not come back from {4, 5, 6, 7} because we should use vertex 0 or vertex 3 to go back and get vertex 1 at the last step.

So we should return, and go to vertex 4 when we are at vertex 0. However, after a trip in {4, 5, 6, 7}, we can only go back by vertex 3, and then we must choose to go to vertex 2 and get vertex 0. This is also a bad path.

So we return again, and go to vertex 3 when we are at vertex 1. However, it is same when we come back from {4, 5, 6, 7}. we could only choose vertex 0 to come back, but we have to go to vertex 2 and reach the vertex 3 in the end.

In conclusion, after the path finding, we could prove that this graph does not have a Hamiltonian cycle.

## 5.3

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

The chromatic number of G is equal to the clique number of G.  That is, χ(G) = κ(G).
:::

The clique number should be the vertex number of the smallest complete sub-graph in G. 

In graph G, we could only find 2-clique (an edge and 2 vertices at 2 sides). There is not any tri-angle (3-complete graph) in G. Therefore, $κ(G) = 2$.

Set vertex 0 in BLACK. And we could find that:

- vertex 0: BLACK
- vertex 1: WHITE
- vertex 2: WHITE
- vertex 3: BLACK
- vertex 4: WHITE
- vertex 5: BLACK
- vertex 6: BLACK
- vertex 7: WHITE

2 colors(black & white) could color graph G. Therefore, $χ(G) = 2$.

We could prove that:

$$
χ(G) = κ(G)
$$


# Question 6

Let Σ = {a,b,c}

Consider the function del:Σ* → Σ* which works as follows:

For w∈Σ*, del(w) is the word that results from removing all c's from w.

For example:

- del(aabbcc) = aabb
- del(ccbbaacc) = bbaa
- del(bacabc) = baba
- del(cccc) = λ
- del(bbbb) = bbbb

## 6.1

:::info{title="Question"}
Give a recursive definition of the function del:Σ* → Σ*
:::

- $del(\lambda) = \lambda$
- $del(cx) = del(x)$
- $del(mx) = m + del(x)$ if $m \in {a,b}$

``` Python
def del(w):
    if not w:
        return w
    if w[0] == 'c':
        return del(w[1:])
    else:
        return w[0] + del(w[1:])
```

## 6.2


:::info{title="Question"}
Let Σ={a,b,c}.

For w∈Σ*, let P(w) be the proposition that:

For all $v \in Σ^*$: $del(wv) = del(w)del(v)$

Prove, using your definition of del from part (a), that P(w) holds for all w∈Σ*.
:::


When $w = \lambda$, P(w) could be:

For all $v \in Σ^*$: $del(v) = del(v)$

It is true.


When $w = w_1w_2...w_k$,

Set: $Σ' = {a,b}$, and single element $w_i$ could be: $Σ'^*c^*Σ'^*$.

$del(wv) = del((Σ'^*c^*Σ'^*)^*v) = (Σ'^*Σ'^*)^*del(v)$

In addition, $del(w) = (Σ'^*Σ'^*)^*$

Therefore, we could prove that:

P(w) holds for all w∈Σ*.


# Question 7

Consider the following two pieces of code.

The first moves the minimum element of a list to its head

```
extractMin(L):	 
    if length(L) <= 1: return L
 	 
    x = L.head	 
    L2 = extractMin(L.next)	 
    if x < L2.head:	 
        return L	 
    else:	 
        L3 = (x, L2.next)	 
        return (L2.head, L3)
```

The second sorts a list by repeatedly extracting the minimum element using `extractMin`

```
mySort(L):	 
    i = 0	 
    L2 = empty
    L3 = L	 
 	 
    while i < length(L):	 
        L3 = extractMin(L3) 
        L2 = (L3.head, L2)	 
        L3 = L3.next	 
        i = i+1	 
 	 
    return L2
```

## 7.1


:::info{title="Question"}
Find an asymptotic upper bound for T(n): the running time of the worst-case of `extractMin(L)` where L is a list with n elements.

You may assume that creating a list is an elementary operation, as is checking the length of L.
:::

The worst case is that:

for every element in position `i`, it is the least element compared with all elements before. function should move `n-i` times to make it to the top of this list.

$$
T(n) = T(n-1) + O(n)
$$

And the sum is:

$$
T(n) = O(n) + O(n-1) + ... + O(1) = O(\frac{n(n+1)}{2}) \\
T(n) = O(n^2)
$$


## 7.2

:::info{title="Question"}
Find an asymptotic upper bound for R(n): the running time of the worst-case of `mySort(L)` where L is a list of n elements.

You may assume that creating a list is an elementary operation, as is checking the length of L.  You may assume the running time of `extractMin` on a list of length n is T(n) [if not previously calculated].
:::

We have proved that the worst-case of `extractMin(L)` is: $O(n^2)$.

And for `mySort(L)`, it use $O(n)$ time to execute `while` command, and every loop it executes `extractMin(L)` to calculate the least element.

Therefore, the worst upper bould for $R(n) = O(n^2 \times n) = O(n^3)$.


# Question 8

A spaceship is full of crewmates and imposters.  Crewmates always tell the truth, and imposters always lie.  Everyone is either a crewmate or an imposter.  Three members of the spaceship, Red, Green and Blue, make the following statements:

- Red: Blue is not an imposter
- Green: At least one of Blue or Green is a crewmate
- Blue: Green is an imposter

You would like to know if at least one of Red or Blue is an imposter.

## 8.1

:::info{title="Question"}

Explain how this problem can be modelled as a problem in Propositional Logic.  In particular, clearly define:

- The propositional variables you are using and what propositions they represent
- Any formulas that are appropriate, and what propositions they represent
- The Propositional Logic problem to be solved
:::

We could define that:

- $R$：Red is crewmate
- $G$: Green is crewmate
- $B$: Blue is crewmate

According to the statement of Red, if Red is crewmate, we could find that Blue is crewmate. If Red is not crewmate, Blue is not crewmate. That means:

$$
R \rightarrow B\\
\neg R \rightarrow \neg B \\
R \leftrightarrow B
$$

According to the statement of Green, there is at least one crewmate between Green and Blue.

$$
\neg B \vee \neg G

$$

According to the statement of Blue, if Green is a crewmate, Blue is an imposter; if Green is an imposter, we could find that this statement is true, and Blue is crewmate. That means:

$$
\neg G \rightarrow B \\
G \rightarrow \neg B \\
\neg G \leftrightarrow B
$$


## 8.2

:::info{title="Question"}
Using the Propositional Logic model of part (a), solve the given problem.
:::

We have that:

- $R \leftrightarrow B$
- $\neg G \leftrightarrow B$
- $\neg B \vee \neg G$

According to first two statement, we could find that:

- $R \leftrightarrow \neg G$

Assum: R is true. 

- According to $R \leftrightarrow B$, B is true.
- According to $R \leftrightarrow \neg G$, G is false.
- $\neg B \vee \neg G$ is true. However, it should be false because Green is imposter.

Assum: R is false.

- According to $R \leftrightarrow B$, B is false.
- According to $R \leftrightarrow \neg G$, G is true.
- $\neg B \vee \neg G$ is true.

Therefore, there is a solution for this spaceship:

- Red is imposter
- Green is crewmate
- Blue is imposter


# Question 9

## 9.1


:::info{title="Question"}

Suppose you have:

- x indistinguishable red balls
- y indistinguishable blue balls
- z indistinguishable green balls

Show that there are:

$$
\binom{x+y+z}{z}\binom{x+y}{y}
$$

ways of placing the balls into x+y+z distinguishable boxes with exactly one ball per box.
:::

We could use 3 steps to place all the balls:

1. select z empty boxes and place all of the green balls.
2. select y empty boxes and place all of the blue balls.
3. place all of the red balls into the rest boxes.

Because every ball is indistinguishable, we do not need to consider the order of placing between same color balls.

For the first step, we have $T_1$ ways:

$$
T_1 = C_{x+y+z}^{z} = \binom{x+y+z}{z}
$$

For the second step, we have $T_2$ ways:

$$
T_2 = C_{x+y}^{y} = \binom{x+y}{y}
$$

And the last step do not need any extra calcuation. Because after step 1 and step 2, there is just one option for step 3 to put balls.

In addition, the selection in step 1 could effect selection in step 2. Because every box is distinguishable. Therefore, every selection is unique.

So we could prove that the way of placing balls are:

$$
T_1 \times T_2 = \binom{x+y+z}{z}\binom{x+y}{y}
$$


## 9.2

:::info{title="Question"}
Show that for all x,y,z ∈ ℕ:

$$
\binom{x+y+z}{z}\binom{x+y}{y} = \binom{x+y+z}{x}\binom{y+z}{y}
$$
:::

If we have the same question in 9.1, we could change the steps in another way:

1. select x empty boxes and place all of the red balls.
2. select y empty boxes and place all of the blue balls.
3. place all of the green balls into the rest boxes.

Because every ball is indistinguishable, we do not need to consider the order of placing between same color balls.

For the first step, we have $T_3$ ways:

$$
T_3 = C_{x+y+z}^{x} = \binom{x+y+z}{x}
$$

For the second step, we have $T_4$ ways:

$$
T_4 = C_{y+z}^{y} = \binom{y+z}{y}
$$

And the last step do not need any extra calcuation. Because after step 1 and step 2, there is just one option for step 3 to put balls.

In addition, the selection in step 1 could effect selection in step 2. Because every box is distinguishable. Therefore, every selection is unique.

So we could prove that the way of placing balls are:

$$
T_3 \times T_4 = \binom{x+y+z}{x}\binom{y+z}{y}
$$

We use different ways to solve same question, and the result should be equal.

Therefore, it should be:

$$
T = T_1 \times T_2 = T_3 \times T_4
$$

It means that:

$$
\binom{x+y+z}{z}\binom{x+y}{y} = \binom{x+y+z}{x}\binom{y+z}{y}
$$


# Question 10


Let $Σ = \{a,b,c\}$

Let $p(k, n)$ be the probability that a word (over Σ) of length n, drawn uniformly at random from the set of all words of length n, contains exactly k c's.


## 10.1

:::info{title="Question"}
What is p(0,n)? 

Justify your answer
:::

For every character in a n-word, the possibility that it is not 'c' is $\frac{2}{3}$.

Therefore, $p(0,n) = (\frac{2}{3})^n$.

## 10.2

:::info{title="Question"}
What is p(n,n)? 

Justify your answer
:::

For every character in a n-word, the possibility that it is 'c' is $\frac{1}{3}$.

Therefore, $p(n,n) = (\frac{1}{3})^n$.

## 10.3

:::info{title="Question"}
Give, with justification, an expression for p(k,n), either:

- in terms of combinatorial functions, or
- recursively, in terms of p(k', n') where k'≤k and n'≤n
:::

We use combinatorial functions to solve this question.

For a n-word, we should select k characters to set 'c', and other characters are not 'c'.

Therefore, we could find that:

$$
p(k,n) = \binom{n}{k} \times (\frac{1}{3})^k \times 1 \times (\frac{2}{3})^{n-k}
$$

It is:

$$
p(k,n) = \binom{n}{k} \times \frac{2^{n-k}}{3^k}
$$


By the way, the recursive way is:

$$
p(k,n) = \frac{1}{3}p(k-1,n-1) + \frac{2}{3}p(k, n-1)
$$

## 10.4


:::info{title="Question"}
What is the expected number of c's in a word of length n, drawn uniformly at random from the set of all words (over Σ) of length n?
:::

For every character, $c_i$, in n-word, the possibility of 'c', $p_i$, is $\frac{1}{3}$.

The expected number of c is:

$$
\sum_{i=1}^n p_i \times length(w_i) = \frac{1}{3} \times 1 + \frac{1}{3} \times 1 ... + \frac{1}{3} \times 1 = \frac{n}{3}
$$

COMP9020 Sample Exam 2022 T3 Part 2

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$