# Maximum distance between samples with equal value in a sequence of i.i.d. discrete samples

Let $$\left(X_i\right)_{i=1}^n$$ be a sequence of i.i.d. samples with discrete outcome space $$S=\{s_1,...,s_k\}, k<\infty$$, $$s_i \in \mathbb{R}$$ with respective probabilities $$p_1,...,p_k$$. Define the maximum distance between two samples with equal value as $$$$D_n = \max_{i=1,...,n}\{\min_{j>i}\{|i-j|:X_i=X_j\}\},$$$$ where we simply take $$n-i$$ if $$X_i$$ is the last sample in the sequence with its value. I want to show if it holds that $$$$\mathbb{P}(D_n \le \varepsilon n) \xrightarrow{n\to\infty}1, \forall \varepsilon >0.$$$$ My idea of why this holds is that as the number of samples till we see a sample with value $$s_i$$ is Geometrically distributed with parameter $$p_i$$. As all the $$X_i$$ are i.i.d. it follows that for $$n$$ large enough that the number of samples in the sequence with value $$s_i$$ is $$p_i n$$. We know that, given that we have $$p_i n$$ samples with value $$s_i$$, the maximum of a sequence of Geometrically distributed samples converges a.s. to $$\frac{\log(p_i n)}{\log(1/(1-p_i)}$$. If the maximum for every value was independent of the maximum of the other values it would follow that $$$$D_n \xrightarrow{a.s.}\max\{\frac{\log(p_i n)}{\log(1/(1-p_i)},i=1,...k\}.$$$$ As the order of growth for $$D_n$$ is $$\log(n)$$ it follows that for $$n$$ large enough that $$D_n < \varepsilon n, \forall \varepsilon > 0$$, such that $$$$\mathbb{P}(D_n \le \varepsilon n) \xrightarrow{n\to\infty}1, \forall \varepsilon >0.$$$$

The problem is that the maximum of the values are dependent of each other. I am having real trouble finding how to approach this problem and can't find anything on the internet. Any advice how to solve this or approach this will be greatly appreciated as this would complete the proof of a theorem I am working on.

• "the maximum of a sequence of Geometrically distributed samples converges..." Notice, however, that here the variables do not seem independent, no? BTW, you forgot to specify $s_i \in \mathbb{R}$ – leonbloy Oct 15 '19 at 12:20
• You're right! I've added the specification, but I have no idea how to approach this dependence.. – DeDeen Oct 15 '19 at 14:58

Let $$X_{j}$$ indicate the event that there does not exist $$k\in\left[j+1,\dots,j+\epsilon n\right]$$ such that $$s_{j}=s_{k}$$. We have:

$$p:=\Pr\left[X_{j}=1\right]= \sum_{i=1}^{k}p_i\left(1-p_{i}\right)^{\epsilon n}$$

Let $$X=\sum_{j=1}^{n}X_{j}$$, then $$\mathbb{E}\left[X\right]=np$$

which approaches zero whenever $$p = o(n)$$. To obtain a bound for $$p$$, you will need to make assumptions on your probabilities.

• I did not notice the probabilities were not uniform. My apologies. – mm8511 Oct 15 '19 at 17:05
• The expectation you have is correct (if you lost the first '1-'). In this case, you can still apply a union bound, and should be able to use the fact that (for any $i$), $E[Y_i]<=k* (1/2^{\epsilon n}$ (since each term is maximized for $p=1/2$)... Will edit now – mm8511 Oct 15 '19 at 17:10
• @DeDeen No worries, that was my fault. – mm8511 Oct 15 '19 at 17:10
• Okay, My bound is not actually correct. The expectation is maximized when $p_i=\frac{1}{\epsilon n}$, so you will have to make some assumptions here, e.g. maybe that the $p_i's$ do not depend on $n$. – mm8511 Oct 15 '19 at 17:37
• sounds great. No problem! – mm8511 Oct 15 '19 at 18:24