Mamy dwa losowe ciągi \(\displaystyle{ x, y}\) o tej samej długości \(\displaystyle{ n}\)
\(\displaystyle{ P(x=y) = p}\) dla każdego \(\displaystyle{ i}\)
Ustalamy parametr \(\displaystyle{ m\in N, m\leqslant n}\)
Definiujemy zdarzenie
\(\displaystyle{ A_{i,j} \equiv A_{i,j}(m) \equiv \{x[i+k] = y[j+k] \ dla \ k = 1 \ do \ m\}}\)
oraz defniujemy zmienną losową
\(\displaystyle{ T \equiv T(n,m) \equiv \sum_{0\leqslant i,j \leqslant n-m} 1(A_{i,j})}\) tzn ilośc powtarzających się bloków o dlugości \(\displaystyle{ m}\) w ciągach
Łatwo pokazać, że \(\displaystyle{ ET = (n-m+1)^2 p^m}\) oraz \(\displaystyle{ P(T>0)\leqslant ET}\)
Nieco trudniej, że \(\displaystyle{ var(T) < \frac {1+p}{1-p}ET}\)
To wszystko wiadomo i jest dla mnie zrozumiałe
Natomiast nie umiem pojąć skąd
\(\displaystyle{ P(T=0)\leqslant \frac{var(T)}{(ET)^2}}\)
Proszę o wyjaśnienie
Dodam, że całość rozumowania pochodziz artykułu
... utenyi.pdf
a niezrozumiana przeze mnie nierówność znajduje się na 17(5) stronie u góry