I need your help with following problem:
String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, that slides over that string. For the given parameters p,k and n one must must determine the mean and variance of the number of the moving windows without any error.
For n = 5 and k = 2 we have sliding windows that contain letters of sting on positions 12, 23, 34 and 45.
I was thinking that I may define discrete random variable that counts how many windows are there with out any error, but very soon it becomes quite difficult to count. I was also trying to define some sort of generating function, but i did not get far. Thank you in advance!
Hint: In order to compute the expectation, use linearity of expectation. In order to compute the variance, compute instead the second moment $\mathbb{E}[X^2]$, where $X=X_1+\cdots+X_{n-k+1}$, and $X_i$ is the event that the $i$th window is error free. The idea here is to use linearity of expectation again: $$\mathbb{E}[X^2] = \sum_i \mathbb{E}[X_i^2] + 2\sum_{i<j} \mathbb{E}[X_i X_j].$$ Since $X_i^2 = X_i$, the first sum is easy to compute. For the second sum, $\mathbb{E}[X_i X_j]$ depends on how much the corresponding windows overlap, which in turn depends on the distance between $i$ and $j$. The calculation becomes a bit messy, but you should be able to obtain a closed form solution after some work.