随机系统的耦合及相关理论

### 随机系统的耦合及相关理论 #### 1. 基本引理 - **引理 3**：对于集合 $A$ 上的两个分布 $X$ 和 $Y$ 以及任意全函数 $f: A \to B$，有 $\delta(X, Y) \geq \delta(f(X), f(Y))$。 - **引理 4**：设 $X$ 和 $Y$ 是同一集合上的概率分布。 1. 对于 $X$ 和 $Y$ 的任意联合分布，有 $\delta(X, Y) \leq Pr(X \neq Y)$。 2. 存在 $X$ 和 $Y$ 的联合分布，使得 $\delta(X, Y) = Pr(X \neq Y)$。 #### 2. 离散随机系统 ##### 2.1 确定性离散系统 - **定义**：确定性离散 $(X, Y)$ - 系统是一个输入字母表为 $X$，输出字母表为 $Y$ 的系统。第 $i$ 个输出 $y_i \in Y$ 是前 $i$ 个输入 $x_i \in X^i$ 的函数。一个确定性离散 $(X, Y)$ - 系统（或 $(X, Y)$ - DDS）是一个前缀封闭域的部分函数 $s: X^+ \to Y$。若 $X$ 有限且 $dom(s) \subseteq \cup_{i \leq n}X^i$（$n \in N$），则称该 $(X, Y)$ - DDS 是有限的。 - **示例**：如图 1 所示，有四个单查询 $(\{0, 1\}, \{0, 1\})$ - DDS： - $zero(x) := 0$ - $one(x) := 1$ - $id(x) := x$ - $flip(x) := 1 - x$ | 输入 | zero | one | id | flip | | ---- | ---- | ---- | ---- | ---- | | 0 | 0 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | - **环境**：环境是一个与系统 $s$ 交互的对象，它产生输入 $x_i$ 给系统 $s$ 并接收相应的输出 $y_i$。环境是自适应和有状态的，即产生的输入 $x_i$ 是所有先前输出 $y_{i - 1} = (y_1, \cdots, y_{i - 1})$ 的函数。一个确定性离散环境（或 $(Y, X)$ - DDE）是一个前缀封闭域的部分函数 $e: Y^* \to X$。 - **转录**：系统 $s$ 在环境 $e$ 中的转录 $tr(s, e)$ 是一系列对 $(x_1, y_1), (x_2, y_2), \cdots, (x_l, y_l)$，其中 $x_i = e(y_1, \cdots, y_{i - 1})$ 且 $y_i = s(x_1, \cdots, x_i)$。要求环境 $e$ 与系统 $s$ 兼容，即当 $x_i = e(y_1, \cdots, y_{i - 1})$ 有定义时，$y_i = s(x_1, \cdots, x_i)$ 也有定义。 ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(环境 e 产生输入 x1):::process B --> C(系统 s 产生输出 y1):::process C --> D{是否继续}:::decision D -- 是 --> E(环境 e 根据 y1 产生输入 x2):::process E --> F(系统 s 根据 x1,x2 产生输出 y2):::process F --> D D -- 否 --> G([结束]):::startend ``` ##### 2.2 概率离散系统 - **定义**：概率离散 $(X, Y)$ - 系统 $S$（或 $(X, Y)$ - PDS）是 $(X, Y)$ - DDS 上的一个分布，使得 $S$ 支持集中的所有 DDS 具有相同的域 $dom(S)$。概率离散环境（或 $(Y, X)$ - PDE）是 $(Y, X)$ - DDE 上的一个分布。 - **