Sampling multidimensional Wiener processes

给出了多维维纳过程下event-triggered的采样策略是optimal的，finite/infinite horizon，以及具体的采样策略

“For one-dimensional Brownian motion, the original problem is converted to an optimal multiple stopping problem, and the optimal sampling strategy is obtained iteratively.”(finite horizon) (Nar和Basar, 2014, p. 3426)

x_{t} = [\begin{matrix} x_{1} (t) \\ ⋮ \\ x_{m} (t) \end{matrix}], d x_{t} = \sum_{i = 1}^{m} e_{i} d w_{i}

其中 $w_{i} (t)$ 为独立的标准维纳过程。
优化目标：找到适应于过程 $x_{t}$ 的最优 sampling rule $δ_{t}$

\begin{array}{r} (1) & lim_{T \to \infty} E [\frac{1}{T} \int_{0}^{T} ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} d t | δ] \\ s . t . lim_{T \to \infty} E [\frac{1}{T} \sum_{t \in [0, T]} δ_{t}] = \frac{1}{c} \end{array}

其中

δ_{t} = {\begin{cases} 1 & if x_{t} is sampled at time t \\ 0 & otherwise . \end{cases}

通过假设演绎+动态规划逐步递推采样时间。

\begin{array}{r} (3) & min E [\frac{1}{T} \int_{0}^{T} ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} d t | δ] \\ s . t . \sum_{t \in [0, T]} δ_{t} = N \end{array}

\begin{aligned} E [\int_{0}^{T} ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} d t] & = E [\int_{0}^{T} ∥ x_{t} ∥_{2}^{2} d t] \\ = E [\int_{0}^{T} \sum_{i = 1}^{m} x_{i}^{2} (t) d t] \\ = m \frac{T^{2}}{2} \end{aligned}

inf_{δ^{n - 1}} E [\int_{t_{1}}^{t_{2}} ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} d t ∣ δ^{n - 1}] = \frac{θ_{n - 1}}{2} {(t_{2} - t_{1})}^{2}

“taking only (n − 1) samples is assumed to be proportional to the square of the length of the interval” (Nar和Basar, 2014, p. 3427)

利用 DP 原理，假设 $δ^{n *}$ 为 n 次最优采样策略， $τ_{1}^{*}$ 为其中第一次采样时刻，那么在 $τ_{1}^{*} \sim T$ 的最优采样 $δ^{(n - 1) *}$ 应与 $δ^{n *}$ 一致
那么 $n$ 个样本中第一个采样时刻最优即最小化

J (τ) = E [\int_{0}^{τ} ∥ x_{t} ∥_{2}^{2} d t + \frac{θ_{n - 1}}{2} {(T - τ)}^{2}] = E [\int_{0}^{τ} \sum_{i = 1}^{m} x_{i}^{2} (t) d t + \frac{θ_{n - 1}}{2} {(T - τ)}^{2}]

min J (τ) ⟺ min E [2 (T - τ) \sum_{i} x_{i}^{2} (τ) + (m - θ_{n - 1}) (T - τ)^{2}]

\begin{aligned} U (t, x) & = β_{n} [m (T - t)^{2} + 2 (T - t) ∥ x ∥_{2}^{2} + \frac{∥ x ∥_{2}^{4}}{m + 2}] \\ , β_{n} & = \frac{4 + m + θ_{n - 1} - \sqrt{θ_{n - 1}^{2} + (8 + 2 m) θ_{n - 1} + m^{2}}}{4} \end{aligned}

\begin{matrix} (12) & \begin{aligned} inf_{τ} J (τ) & = m \frac{T^{2}}{2} - \frac{1}{2} U (0, x_{0}) = m \frac{T^{2}}{2} - \frac{1}{2} m β_{n} T^{2} \\ = m (1 - β_{n}) \frac{T^{2}}{2} \\ =: θ_{n} \frac{T^{2}}{2} \end{aligned} \end{matrix}

从 n-1 次最优采样推出上式 n 次最优采样的 MSE，与 4 中采样间隔平方成正比的假设一致，因此假设成立。
8. optimal stopping time

inf_{t \geq 0} {t | 2 (T - t) ∥ x_{t} ∥_{2}^{2} + (m - θ_{n - 1}) (T - t)^{2} \geq U (t, x_{t})} = inf_{t \geq 0} {t | ∥ x_{t} ∥_{2}^{2} \geq \sqrt{\frac{(m + 2) (θ_{n - 1} - θ_{n})}{1 - \frac{θ_{n}}{m}}} (T - t)}

那么以此类推 the optimal time $τ_{N - k}^{*}$ to take the $(N - k)^{t h}$ sample is

\begin{matrix} (14) & inf_{t \geq τ_{N - k - 1}^{*}} {t | ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} \geq \sqrt{\frac{(m + 2) (θ_{k} - θ_{k + 1})}{1 - \frac{θ_{k + 1}}{m}}} (T - t)} \end{matrix}

其中 $θ_{n} = \frac{m}{4} (- m - θ_{n - 1} + \sqrt{θ_{n - 1}^{2} + (8 + 2 m) θ_{n - 1} + m^{2}}), θ_{0} = m, τ_{0}^{*} = 0$

通过扩展 finite horizon 的结论得到在 infinite horizon 的性质。固定 $N / T = c$ 表示采样的平均频率，可以得到最优采样策略即如下的 event-triggered 策略

Theorem

The optimal sampling policy that minimizes (1) subject to (2) is the following constant threshold rule:

\begin{matrix} (20) & δ_{t}^{*} = {\begin{cases} 1 & if {‖ x_{t} - {\hat{x}}_{t} ‖}_{2}^{2} \geq m c \\ 0 & otherwise. \end{cases} \end{matrix}

通过 (12) 式带入可得到 MSE：

\begin{aligned} lim_{T \to \infty} E [\frac{1}{T} \int_{0}^{T} ∥ x_{t} - {\hat{x}}_{t} ∥_{2}^{2} d t | δ^{*}] & = lim_{n \to \infty} \frac{1}{c n} θ_{n} \frac{(c n)^{2}}{2} = \frac{\overset{―}{α} c}{2} = \frac{m^{2}}{2 (m + 2)} c \end{aligned}

Proof

首先由于 $T \to \infty$ 直观上采样次数区域无穷，每次采样的策略应该是独立且等价的。根据 (14) 式可知当前目标即关注停时的 threshold在 $n \to \infty$ 时的有什么性质（最好极限存在且为常数）

\begin{matrix} (16) & lim_{n \to \infty} \frac{(m + 2) (θ_{n - 1} - θ_{n})}{1 - \frac{θ_{n}}{m}} (c n - t)^{2} \end{matrix}

lim_{n \to \infty} n^{2} \frac{(m + 2) (θ_{n - 1} - θ_{n})}{1 - \frac{θ_{n}}{m}} = \frac{(m + 2)^{2}}{m^{2}} {(lim_{n \to \infty} n θ_{n})}^{2}

lim_{n \to \infty} \frac{(m + 2) (θ_{n - 1} - θ_{n})}{1 - \frac{θ_{n}}{m}} (c n - t)^{2} = m^{2} c^{2}