Monte Carlo Integration in Probability I am studying for an exam and I came across this problem and I hope someone can help me solve it
Assume given a continuous function u on [0, 1] such that 0 ≤ u(x) ≤ 1. We use u to create an array of {0, 1}-valued random variables as follows: let {$X_{n,k}$ : 1 ≤ k ≤ n, n $\in$ N} be independent random variables with marginal distributions
$$P(X_{n,k}=0)= 1-u(k/n) \quad and \quad P(X_{n,k}=1)=u(k/n) $$
Let $S_n=X_{n,1}+X_{n,2} +...+X_{n,n}$ be sum of row n of the array. How to show that $S_n/n$ converges to some constant almost surely. 
 A: First look at the expectation:
$$
\mu_n:=E\left(\frac{S_n}n\right) = \frac1n\sum_{k=1}^nE(X_{n,k})=\frac1n\sum_{k=1}^nu(k/n)\tag1
$$
Notice that $\mu_n$ is a Riemann sum converging to
$$
\mu:=\int_0^1u(x)dx\,.\tag2
$$
You can show that $\frac{S_n}n-\mu_n$ converges in probability to zero (and therefore $\frac{S_n}n$ converges in prob to $\mu$)
by applying Markov's inequality to 
$\left|\frac{S_n}n-\mu_n\right|^2$:
$$
P\left(\left|\frac{S_n}n-\mu_n\right|>\varepsilon\right)\le
\frac1{\varepsilon^2} E \left|\frac{S_n}n-\mu_n\right|^2\to0, \tag3
$$
remembering that
$$
\frac Sn-\mu_n = \frac1n\sum_{k=1}^nY_{n,k}\tag4
$$
where the $Y_{n,k}$ are independent with mean $0$, and $E(Y_{n,k})^2$ is uniformly bounded over all $n,k$.
But the bound in (3) isn't sharp enough to prove convergence almost surely. To show a.s. convergence you can prove the stronger result
$$
\sum_n P\left(\left|\frac{S_n}n-\mu_n\right|>\varepsilon\right)<\infty\tag5
$$
by applying Markov's inequality to
$\left|\frac{S_n}n-\mu_n\right|^4$, then apply the Borel-Cantelli lemma. To show the sum  in (5) converges, you'll exploit the fact that $E(Y_{n,k})^4$ is uniformly bounded over all $n,k$.
