IS CS-2016S1-01

题目来源：Problem 1 日期：2024-08-11 题目主题：CS-算法-概率与矩阵计算

解题思路

本题探讨的是关于随机 0-1 向量和矩阵的性质。通过概率论的基本概念和矩阵运算，我们需要解决以下问题：

1. 计算给定矩阵乘以随机 0-1 向量后结果为 0 向量的概率。
2. 证明一个矩阵乘以随机 0-1 向量后结果为 0 向量的概率上限。
3. 证明矩阵乘积与另一个矩阵的乘积不相等的概率上限。
4. 设计一个算法来验证矩阵乘积是否满足特定条件。

问题 1 和问题 2 涉及基本的模 2 运算和线性代数的知识。问题 3 则基于之前的问题并扩展至矩阵乘法的情况。问题 4 则要求我们设计一个高效的算法，并分析其正确性和复杂度。

Solution

Question 1

Given $\mathbf{x}\in \{0,1{\}}^3$ as a random 0-1 vector, we want to calculate the probability that:

$$\mathbf{Mx}\stackrel{.}{=}\mathbf{o}$$

where $\mathbf{M}$ is given by

$$\mathbf{M}=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right).$$

Let $\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)$, where each $x_i\in \{0,1\}$ is chosen independently with equal probability $1/2$. We need to find the probability that:

$$\mathbf{Mx}\equiv \mathbf{o}(\text{mod}2).$$

This translates to:

$$\mathbf{Mx}=\left(\begin{array}{c}{x}_2+x_3\\ x_1+x_3\\ x_1+x_2\end{array}\right)\equiv \left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)(\text{mod}2).$$

Thus, we need to find the probability that:

$$\begin{array}{rl}{x}_2+x_3& \equiv 0(\text{mod}2),\\ x_1+x_3& \equiv 0(\text{mod}2),\\ x_1+x_2& \equiv 0(\text{mod}2).\end{array}$$

This system of equations implies that $x_1=x_2=x_3$. Since each $x_i$ is independently chosen from $\{0,1\}$ with probability $1/2$, the probability that $x_1=x_2=x_3$ is $1/4$. Therefore, the probability is:

$$\mathbb{P}\left(\mathbf{Mx}\equiv \mathbf{o}(\text{mod}2)\right)=\frac{1}{4}.$$

Question 2

Given $\mathbf{A}$ as an $n\times n$ integer matrix that does not satisfy $\mathbf{A}\stackrel{.}{=}\mathbf{O}$, and $\mathbf{x}\in \{0,1{\}}^n$ as a random 0-1 vector, we need to prove that:

$$\mathbb{P}(\mathbf{Ax}\stackrel{.}{=}\mathbf{o})\le \frac{1}{2}.$$

Since $\mathbf{A}\ne \mathbf{O}(\text{mod}2)$, at least one row ${\mathbf{a}}_i$ of $\mathbf{A}$ is not equivalent to the zero vector $\mathbf{o}$ modulo 2. This implies that there exists some $i$ for which ${\mathbf{a}}_i\mathbf{x}\equiv 1(\text{mod}2)$ for at least one value of $\mathbf{x}$.

For a fixed ${\mathbf{a}}_i$, ${\mathbf{a}}_i\mathbf{x}\equiv 0(\text{mod}2)$ happens with probability $1/2$. Since the rows of $\mathbf{A}$ are independent, the probability that all ${\mathbf{a}}_i\mathbf{x}\equiv 0(\text{mod}2)$ for $i\in [1,n]$ is at most $1/2$. Thus,

$$\mathbb{P}(\mathbf{Ax}\stackrel{.}{=}\mathbf{o})\le \frac{1}{2}.$$

Question 3

Let $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{C}$ be $n\times n$ matrices that do not satisfy $\mathbf{AB}\stackrel{.}{=}\mathbf{C}$, and $\mathbf{x}\in \{0,1{\}}^n$ be a random 0-1 vector. We want to prove that:

$$\mathbb{P}\left(\mathbf{ABx}\stackrel{.}{=}\mathbf{Cx}\right)\le \frac{1}{2}.$$

Consider the matrix $\mathbf{D}=\mathbf{AB}-\mathbf{C}$. The problem now reduces to showing that:

$$\mathbb{P}(\mathbf{Dx}\stackrel{.}{=}\mathbf{o})\le \frac{1}{2}.$$

Since $\mathbf{AB}\not\equiv \mathbf{C}(\text{mod}2)$, it follows that $\mathbf{D}\not\equiv \mathbf{O}(\text{mod}2)$. From Question 2, the probability that $\mathbf{Dx}\equiv \mathbf{o}(\text{mod}2)$ is no greater than $1/2$.

Thus,

$$\mathbb{P}\left(\mathbf{ABx}\stackrel{.}{=}\mathbf{Cx}\right)\le \frac{1}{2}.$$

Question 4

To design an $O(n^2)$ algorithm that checks whether $\mathbf{AB}\stackrel{.}{=}\mathbf{C}$ with high probability, we can proceed as follows:

1. Choose a random vector $\mathbf{x}\in \{0,1{\}}^n$.
2. Compute ${\mathbf{y}}_1=\mathbf{ABx}(\text{mod}2)$ and ${\mathbf{y}}_2=\mathbf{Cx}(\text{mod}2)$.
3. If ${\mathbf{y}}_1\ne {\mathbf{y}}_2$, return “NOT SATISFIED”.
4. Repeat steps 1-3 independently $k$ times for some $k$.
5. If ${\mathbf{y}}_1={\mathbf{y}}_2$ in all $k$ trials, return “SATISFIED”. Otherwise, return “NOT SATISFIED”.

By choosing $k$ sufficiently large, say $k=10\log n$, we can ensure that the probability of falsely returning “SATISFIED” when $\mathbf{AB}\not\equiv \mathbf{C}$ is less than $1/10$.

This algorithm runs in $O(n^2)$ time since each matrix-vector multiplication takes $O(n^2)$ time, and we perform it a constant number of times.

知识点

模运算线性代数概率

解题技巧和信息

• 在处理模 2 运算时，特别是在随机 0-1 向量的情况下，独立性和等概率性是关键。
• 对于不等式概率证明，考虑行独立性和矩阵之间的模 2 差异是有帮助的。
• 在算法设计中，重复独立测试可以显著降低错误概率。

重点词汇

• Modulo operation (模运算)
• Random 0-1 vector (随机 0-1 向量)
• Matrix multiplication (矩阵乘法)

参考资料

1. Introduction to Algorithms, 3rd Edition - Cormen, Chapter 28.
2. Linear Algebra and Its Applications - Gilbert Strang, Chapter 6.