Expectation

Series: Stochastic Approximation from First Principles · Part 9 of 22 Suppose the statistical properties of $\eta_k$ are known, while the behavior of $w_k$ is what we want to determine. We can use the former to compare two update mechanisms: $\alpha=1$ and $0<\alpha<1$. The goal is a traveler whose position is centered on the true riverbank $w^*$ and whose individual journeys do not fluctuate excessively. The Memoryless Update With $\alpha=1$: $$ w_{k+1}=w^*+\eta_k. $$Therefore: ...

Series: Stochastic Approximation from First Principles · Part 17 of 22 The energy proof controls entire sample paths. A more direct route expands $\Delta_k$ and studies: $$ \mathbb{E}[\Delta_k] \quad\text{and}\quad \operatorname{Var}(\Delta_k). $$If both approach zero, the distribution of $\Delta_k$ concentrates near zero. This route is intuitive, but it usually proves convergence in probability rather than the almost-sure convergence in Dvoretzky’s theorem. The Simplified Setting Begin with: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$For this route, treat $\alpha_k$ and $\beta_k$ as given coefficients and use ordinary assumptions such as zero-mean, bounded-variance, independent or uncorrelated disturbances. ...

Series: Stochastic Approximation from First Principles · Part 19 of 22 The explicit error formula is: $$ \Delta_k = \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0 + \sum_{j=0}^{k-1} \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j\eta_j. $$For this simplified calculation, treat $\alpha_i$ and $\beta_j$ as given coefficients and assume ordinary zero-mean noise. The full theorem replaces ordinary zero mean with conditional zero mean given the history. Take the Expectation If: $$ \mathbb{E}[\eta_j]=0, $$then: $$ \begin{aligned} \mathbb{E}[\Delta_k] &= \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0\\ &\quad+ \sum_{j=0}^{k-1} \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j \underbrace{\mathbb{E}[\eta_j]}_{0}. \end{aligned} $$Therefore: ...