PaperlayerView exact revision on arXiv

Source-linked AI summary

Remote Estimation of the Wiener Process over a Channel with Random Delay

Yin Sun, Yury Polyanskiy, Elif Uysal-Biyikoglu

arXiv:1701.06734v9cs.ITmath.IT

TL;DR

The paper studies how to minimize mean-square estimation error when a Wiener process is sampled and sent to a remote estimator through a random-delay channel. It derives an optimal threshold policy and finds that it outperforms age-optimal, zero-wait, and uniform sampling; even without a sampling-frequency constraint, zero-wait is not optimal.

  • Problem

    The paper investigates how to minimize mean-square estimation error when sampling a Wiener process for remote estimation over a channel with random delay.

    Source: §VI · p. 7

  • Method

    The authors solve the constrained sampling problem and prove that the optimal policy is a threshold whose value depends on the sampling-frequency constraint and signal variation during channel delay.

    Source: §I · p. 1

  • Results

    The optimal policy's MMSE is much smaller than those of age-optimal sampling, zero-wait sampling, and classic uniform sampling.

    Source: §I · p. 2

  • Takeaways & Limitations

    Even with an unbounded sampling frequency, it is optimal to wait a positive amount after delivery rather than sample immediately.

    Source: §I · pp. 1–2

Abstract

from arXiv · show

In this paper, we consider a problem of sampling a Wiener process, with samples forwarded to a remote estimator via a channel that consists of a queue with random delay. The estimator reconstructs a real-time estimate of the signal from causally received samples. Motivated by recent research on age-of-information, we study the optimal sampling strategy that minimizes the mean square estimation error subject to a sampling frequency constraint. We prove that the optimal sampling strategy is a threshold policy, and find the optimal threshold. This threshold is determined by the sampling frequency constraint and how much the Wiener process varies during the channel delay. An interesting consequence is that even in the absence of the sampling frequency constraint, the optimal strategy is not zero-wait sampling in which a new sample is taken once the previous sample is delivered; rather, it is optimal to wait for a non-zero amount of time after the previous sample is delivered, and then take the next sample. Further, if the sampling times are independent of the observed Wiener process, the optimal sampling problem reduces to an age-of-information optimization problem that has been recently solved. Our comparisons show that the estimation error of the optimal sampling policy is much smaller than those of age-optimal sampling, zero-wait sampling, and classic uniform sampling.

I. INTRODUCTION

The paper studies MMSE-optimal sampling of a Wiener process whose time-stamped samples travel through a queue with random delay. It establishes a threshold policy whose threshold depends on the sampling-frequency constraint and signal variation during channel delay, and finds that zero-wait sampling is not generally optimal.

I. INTRODUCTION

  • The system sends time-stamped Wiener-process samples from an observer through a FIFO queue with random i.i.d. delay to an estimator that forms causal estimates.The objective is to minimize mean square estimation error subject to a maximum sampling frequency.Source: §I · p. 1

III. MAIN RESULT

  • The MMSE-optimal policy is a threshold rule whose threshold depends on the sampling-frequency constraint and signal variation during channel delay, and is disabled while a sample is in transmission.The threshold is reactivated after delivery; queued samples become stale while waiting for transmission.Source: §I · p. 1, §III · p. 3

I. INTRODUCTION

  • Even without a sampling-frequency constraint, the optimal policy waits a positive time after delivery rather than sampling immediately as in zero-wait sampling.For an unbounded frequency constraint, zero-wait achieves maximum throughput and minimum queueing delay but almost never minimizes MMSE.Source: §I · pp. 1–2
  • When sampling times are independent of the Wiener process, the optimal sampling problem reduces to an age-of-information optimization problem solved in, [12].Source: §I · p. 2

II. RELATED WORK

  • The work connects age-of-information research focused on queueing and delay without a signal model to remote estimation research by adding a queueing model.The paper identifies as the closest prior study and describes it as a special case without queueing or channel delay.Source: §II · p. 2

A. Signal-Independent Sampling and the Age-of-Information

When sampling times are independent of the Wiener process, MMSE optimization reduces to an age-of-information optimization problem. The paper relates this restricted problem to an age-optimal policy and contrasts it with the harder signal-dependent problem.

A. Signal-Independent Sampling and the Age-of-Information

  • Signal-independent policies are policies independent of the Wiener process; the broader causal problem can use the observed signal history.The broader problem is more challenging because sampling decisions must account for the signal's evolution.Source: A. Signal-Independent Sampling and the… · p. 3
  • Restricting policies to those independent of the Wiener process reduces MMSE optimization to an age-of-information optimization problem.The age is the time since generation of the freshest received sample.Source: A. Signal-Independent Sampling and the… · p. 3
  • The age-optimal policy has a threshold β≥0 determined by solving the stated optimization condition.The optimal value of the age objective is then given by the paper's corresponding expression.Source: A. Signal-Independent Sampling and the… · p. 3
  • The paper studies asymptotics of MMSE-optimal and age-optimal policies at low and high channel delays or sampling frequencies.Source: A. Signal-Independent Sampling and the… · p. 3

B. Low Channel Delay or Low Sampling Frequency

The low-delay or low-frequency limit relates age-optimal sampling to uniform sampling. In the high-delay or unbounded-frequency limit, the optimal thresholds are characterized separately, and zero-wait sampling is MMSE-optimal only when delay is almost surely zero.

B. Low Channel Delay or Low Sampling Frequency

C. High Channel Delay or Unbounded Sampling Frequency

  • For high channel delay or unbounded sampling frequency, the MMSE-optimal and age-optimal policies each use a threshold determined by their respective stated conditions; the ratio of their optimal MMSE values depends on the delay distribution.Source: C. High Channel Delay or Unbounded… · p. 4
  • With unbounded sampling frequency, zero-wait sampling is MMSE-optimal if and only if channel delay is zero with probability one.Zero-wait sampling achieves maximum throughput and minimum queueing delay, but those properties do not make it MMSE-optimal for nonzero random delay.Source: C. High Channel Delay or Unbounded… · p. 4

IV. PROOF OF THE MAIN RESULT

The proof simplifies the constrained sampling problem and solves it through a Lagrangian decomposition into per-sample control problems. The simplification rules out sampling before delivery, then uses the resulting waiting-time representation to connect the original objective to a Markov decision problem.

IV. PROOF OF THE MAIN RESULT

  • The proof uses the Wiener process's strong Markov property, Lagrangian duality, continuous-time Markov decision problems, and optimal stopping to establish the main result.It concludes by showing that the Lagrangian duality gap is zero.Source: §IV · p. 4

A. Problem Simplification

  • It is suboptimal to sample before the prior sample is delivered, so the proof restricts attention to policies that generate each sample after delivery.A sample waiting in the queue becomes stale; the argument relies on the Wiener process's strong Markov property, which may not hold for other signal processes.Source: A. Problem Simplification · p. 4
  • Under this restriction, the queue is kept empty, and each inter-sample interval is represented by the prior sample's channel delay plus a nonnegative post-delivery wait.The post-delivery wait is Zi=Si+1−Di.Source: A. Problem Simplification · pp. 4–5
  • The reformulated problem is a Markov decision problem; a parameterized objective p(c) is used to find its optimum, with p(c)=0 linking the parameterized and original solutions.The regenerative sampling-time structure supports the reformulation.Source: A. Problem Simplification · p. 5

B. Lagrangian Dual Problem of (29)

The section applies Lagrangian duality to (29), establishes a zero duality gap at copt, and treats the per-sample problem as an optimal-stopping problem.

B. Lagrangian Dual Problem of (29)

C. Per-Sample Optimal Stopping Solution to (36)

D. Zero Duality Gap between (29) and (33) at c = copt

V. NUMERICAL RESULTS

The numerical comparisons favor MMSE-optimal sampling over age-optimal, zero-wait, and uniform sampling, with performance depending on the channel-delay setting. The conclusion presents the work as extending age-of-information optimization to Wiener-process estimation over a queued channel with random delay.

V. NUMERICAL RESULTS

  • The numerical evaluation compares uniform, zero-wait, age-optimal, and MMSE-optimal sampling policies.Zero-wait sampling is feasible in the stated comparison when fmax ≥ E[Yi].Source: §V · p. 7
  • MMSE-optimal sampling has no larger MMSE than age-optimal or uniform sampling, and when fmax ≥ E[Yi], no larger MMSE than zero-wait sampling.The stated order is mmseopt ≤ mmseage-opt ≤ mmseuniform and, when fmax ≥ E[Yi], mmseopt ≤ mmseage-opt ≤ mmsezero-wait.Source: §V · p. 7
  • For exponential delay, uniform-sampling MMSE diverges as fmax approaches 1, while mmseopt/mmseage-opt tends to 1/3 as fmax → 0.At low fmax, age-optimal and uniform sampling have similar MMSE; zero-wait MMSE exceeds the optimal policies when fmax ≥ 1.Source: §V · p. 7
  • For log-normal delay, uniform-sampling MMSE grows faster than mmseopt and mmseage-opt as σ rises when fmax = 0.8; at fmax = 1.5, zero-wait MMSE grows quickly and is much larger than both.The gap between mmseopt and mmseage-opt increases with σ; uniform sampling has infinite MMSE at fmax = 1.5.Source: §V · p. 7, Figure 6 · p. 7

VI. CONCLUSION

  • The conclusion frames the results as extending age-of-information research with a signal model and remote-estimation research with a queued channel having random delay.Source: §VI · p. 7

APPENDIX A PROOF OF (10)

These appendices establish proof steps for the paper’s formulas and threshold results, including asymptotic cases and a condition under which the zero-wait threshold is zero.

APPENDIX A PROOF OF (10)

  • When sampling decisions are independent of the Wiener process, the proof of (10) uses independence, the law of iterated expectations, Fubini’s theorem, Wald’s identity, and the strong Markov property.Source: Appendix A · p. 8

APPENDIX B PROOFS OF (17) AND (19)

  • The proofs establish (17) and (19) in the limits fmax → 0 and d → 0.The d → 0 case uses Y → 0 and WY → 0 with probability one.Source: Appendix B · pp. 8–9

APPENDIX C PROOF OF (21)

  • When d → ∞, the proof scales β and the displayed delay-dependent terms to obtain the solution in (21).Source: Appendix C · p. 9

APPENDIX D PROOFS OF THEOREMS 3 AND 4

  • The proof shows that β = 0 if and only if Y = 0 with probability one.It derives E[W_Y^4] = 3E[Y^2] before applying (21).Source: Appendix D · p. 9

APPENDIX E PROOF OF LEMMA 1

The appendix compares policies by postponing sample generation to channel submission and proves an equivalence between two optimization formulations.

APPENDIX E PROOF OF LEMMA 1

  • Postponing sample i’s generation from Si to Gi leaves delivery times unchanged and yields a policy with smaller MMSE.The construction applies when Si < Gi, meaning the sample was generated while the channel was busy.Source: Appendix E · pp. 9–10
  • Repeating the postponement for samples generated before their channel submission produces a policy with lower MMSE than the original policy.Source: Appendix E · p. 10

APPENDIX F PROOF OF LEMMA 2

  • The proof shows that each optimal solution to (27) is optimal for (29), and conversely.Source: Appendix F · p. 10

APPENDIX G PROOF OF LEMMA 3

The appendix identifies information sufficient for control decisions and develops a stopping-time argument for a separate lemma.

APPENDIX G PROOF OF LEMMA 3

  • An optimal Zi can be chosen using only Ii = (Yi, (WSi+t − WSi, t ≥ 0)), which is independent of the Wiener process up to Si.The proof identifies Ii as a sufficient statistic for determining Zi.Source: Appendix G · p. 10

APPENDIX H PROOF OF LEMMA 4

  • The cited passage states that two processes associated with the Wiener process are martingales, and separately states that another process of the Wiener process is also a martingale.Source: Appendix H · p. 10
  • For each t, t ∧ τ is a bounded stopping time; convergence arguments then establish (59).The proof invokes Fatou’s lemma, Doob’s maximal inequality, dominated convergence, and monotone convergence.Source: Appendix H · pp. 10–11

APPENDIX I PROOF OF (35)

These appendices establish an expectation identity, reduce the sampling control to per-sample decisions, and complete a two-case lemma proof. The derivations invoke independence and Wiener-process properties, including the strong Markov property and Wald’s identity.

APPENDIX I PROOF OF (35)

  • The proof of (35) uses stopping times of a time-shifted Wiener process, independence, the strong Markov property, and Wald’s identity.It then combines the preceding steps to obtain (35).Source: Appendix I · pp. 11–12

APPENDIX J PROOF OF THEOREM 5

  • The proof of Theorem 5 identifies I′_i as sufficient for choosing Z_i, decomposes the control into per-sample problems, and obtains i.i.d. waiting times.The associated Wiener-process increments are also i.i.d. under this policy.Source: Appendix J · p. 12

APPENDIX K PROOF OF LEMMA 5

  • For b² < β, the Lemma 5 proof has τ* > 0 and (b + W_τ*)² = β, then combines the two cases to complete the proof.Source: Appendix K · p. 12

APPENDIX L PROOF OF LEMMA 6

The proof applies the Itô–Tanaka–Meyer formula and properties of Wiener-process local time to establish an expectation inequality for u.

APPENDIX L PROOF OF LEMMA 6

  • The function u(s, b) is continuously differentiable in (s, b).Source: Appendix L · p. 12
  • The proof uses the Itô–Tanaka–Meyer formula and Wiener-process local-time properties in its argument.The passage defines L^a(t) as the time the Wiener process spends at level a.Source: Appendix L · p. 12
  • E_x[u(X_t)] ≤ u(x) for all x ∈ R² and t ≥ 0, completing the proof.Source: Appendix L · p. 13

APPENDIX M PROOF OF THEOREM 7

The proof establishes zero duality gap and identifies a common optimal policy for the constrained formulations. It then relates the optimal mean square error to the policy’s threshold and derives moment identities used in the argument.

APPENDIX M PROOF OF THEOREM 7

  • The proof establishes that π⋆ is optimal for the primal problem and that the duality gap between (29) and (33) is zero.It identifies λ⋆ as a geometric multiplier for (29).Source: Appendix M · p. 13
  • A common optimal solution to (6), (27), and (29) at c = copt is policy (4), with β ≥ 0 determined by the stated condition.The policy uses β = 3(copt + λ⋆ − E[Y]).Source: Appendix M · p. 13
  • The proof concludes that mmseopt = copt and obtains it by substituting policy π⋆ and (35) into (27).Source: Appendix M · p. 13
  • The policy’s fourth moment is E[(W_{S_i+Y_i+Z_i} − W_{S_i})^4] = E[max(β², (W_{S_i+Y_i} − W_{S_i})^4)].The proof also invokes Wald’s identity for E[(W_{S_i+Y_i} − W_{S_i})²] = E[Y_i].Source: Appendix M · pp. 13–14
Loading 1701.06734v9…