Random Binary Strings, Time until All Differ

Question

Let $\{X_i\}_1, \{X_i\}_2, \ldots, \{X_i\}_n$ be random binary strings where for all strings $j$ and all positions $i$, independently of all other bits on all strings, $X_{i, j} \sim Ber(1/2)$. Assume that we generate the strings by sequentially drawing the $i$-th bit independently for all strings. In this setting, let $T$ denote the first instance in time at which no two strings are equal. I wish to argue that

\begin{equation} P[T \geq 2\log_2{n} + 1] \leq 1/4. \end{equation}

In particular I am interested if Markov's inequality will do the job. To obtain a handle on $E[T]$, let $Y_i$ count the equal strings pairs at time $i$. Clearly we have reached $T$ iff $Y_T = 0$. We define all empty strings at $t = 0$ (i.e. before the first bits are drawn) to be equal, hence we start with $Y_0 = {{n}\choose{2}}$ equal string pairs.

Exploiting linearity of expectation, it is easily shown that $E[Y_{i + 1} | Y_i = k] = k/2$ and hence $E[T] \leq \log_2{Y_0}$. Since $Y_0 \approx n^2$ this allows however only for

\begin{equation} P[T \geq 2\log_2{n} + 1] \leq \frac{E[T]}{2\log_2{n} + 1} \leq \frac{2\log_2{n}}{2\log_2{n} + 1}, \end{equation}

which is not very helpful.

How can the preceding analysis be improved? Or is Markov's inequality too weak for the task at hand?

Answer 1

You can, indeed, prove the claim using Markov's inequality, but you should apply it to the probability $P[Y_k\ge 1]$ instead, for the appropriate $k$. As you are doing this as an exercise, I will not supply any further details.

Answer 2

(Not an answer, but a comment with an image.)

Here are some empirical results that may help motivate someone to attempt the requested proof of $P[T_n \geq 2\log_2{n} + 1]\leq 1/4.$ The following picture shows the results of simulating the distribution of $T_n$ for $n\in\{2^1,2^2,...,2^{10}\}$, with $10^5$ trials in each simulation. Estimates of $P[T_n \geq 2\log_2{n} + 1]$ are plotted vs. $\log_2(n)$. The dark blue is the estimated probability and the light blue is a $95\%$ confidence interval. (NB: These results are just at the ten values $n\in\{2^1,2^2,...,2^{10}\}$, the line being an interpolation at the intermediate integers.)