<a href="https://colab.research.google.com/github/Jun-629/20MA573/blob/master/src/Hw10_SA.ipynb" target="_parent"></a>

Let $D = \{ X_i:i \in \mathbb N \}$ be a data set of i.i.d. sequence from a random generator of distribution $\mathcal{N}(b, \sigma ^2)$ for some unknown parameters $b$ and $\sigma$. Our goal is to estimate $b$ using so called stochastic approximation ($\mathrm{SA}$) with a given learning rate $\alpha \in (0,1)$.

1. Write pseudocode for $\mathrm{SA}$.

The pseudocode for $\mathrm{SA}$ is shown as follows:

[pseudocode](https://github.com/Jun-629/20MA573/blob/master/src/Hw10_pseudocode.pdf)

2. Generate a data set $D = \{ x_i:1 \leq i \leq 10000 \}$ with $\mathcal{N}(1,4)$.


```
import numpy as np
import matplotlib.pyplot as plt

sampleNo = 10000
mu = 1
sigma = 4
#np.random.seed(0)
D = np.random.normal(mu, sigma, sampleNo)
#plt.plot(range(sampleNo), D)
```

3. Write a code to implement $\mathrm {SA}$ on $D$, and demonstrate $b_n \to b$ as $n \to \infty$.


```
def SA(b0,alpha,N=10000):                       # N is the number of the sequence of random variable Xi
  b = [b0]
  for k in range(N):
    b_k = b[k] + alpha * (D[k] - b[k])
    b.append(b_k)
  return b[N-1]
SA(2,0.01)
```




    1.0483728903289875



4. Prove that $\lim_n \mathbb E b_n = b$.

__Pf:__

Due to the fact in the lecture, we know that
$$\mu_k = \frac{1}{k} \sum_{i=1}^k x_i$$
is equivalent to
$$\mu_k = \mu_{k-1} + \frac{1}{k}(x_k - \mu_{k-1}).$$
Here, we already have that
$$b_{k+1} = b_k + \alpha(x_k - \mu_k), k \in [0,9999], k \in \mathbb N,$$
Thus, we deduce that
$$b_n = \frac{1}{n} \sum_{i=1}^n x_i, x_i \sim \mathcal{N}(b,\sigma^2).$$
Therefore, by LCT, we have
$$\lim_n \mathbb E b_n = \lim_n \mathbb E [\frac{1}{n} \sum_{i=1}^n x_i] = \lim_n \frac{1}{n}  \mathbb E [\sum_{i=1}^n x_i] = b.$$


5. Can you prove or disprove that $b_n \to b$ in $L^2$?

__Pf:__

If $b_n \to b$ in $L^2$, then we need to show that
$$\lim_n \mathbb E[|b_n - b|^2] = 0$$

\begin{equation}
\begin{aligned}
L.H.S &= \lim_n \mathbb E [b_n^2 - 2\cdot b\cdot b_n + b^2] \\
&= \lim_n \left( \mathbb E [ (\frac{1}{n} \sum_{i=1}^n x_i)^2 ] - 2b \mathbb E [b_n]\right) + b^2 \\
&= \lim_n \frac{1}{n^2} \left( \sum_{i=1}^n \mathbb E [x_i^2] + \sum_{i \neq j} \mathbb E [x_i] \cdot \mathbb E[x_j] \right) - b^2 \\
&= \lim_n \frac{1}{n^2} \left[ n(b^2 + \sigma^2) + (n^2 - n) b^2 \right] - b^2 \\
&= \lim_n \frac{\sigma^2}{n} = 0.\\
\end{aligned}
\end{equation}

Therefore, $b_n \to b$ in $L^2$.

45f92bd3cb9cbb001a9a1acfcac4c0b2eff09691
ipynb
Jupyter Notebook
src/Hw10_SA.ipynb
Jun-629/20MA573
addad663d2dede0422ae690e49b230815aea4c70
MIT
src/Hw10_SA.ipynb
Jun-629/20MA573
addad663d2dede0422ae690e49b230815aea4c70
MIT
src/Hw10_SA.ipynb
Jun-629/20MA573
addad663d2dede0422ae690e49b230815aea4c70
MIT
2020-02-05T21:42:08.000Z
2020-02-05T21:42:08.000Z
Qwen/Qwen-72B
1. YES
2. YES