Random Binary Strings, Time until All Differ

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

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

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

$$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},$$

which is not very helpful.

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

• What is the definition of $y_0$? Dec 4, 2017 at 1:19
• I have updated the question. Dec 4, 2017 at 9:21

2 Answers

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.

• This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review Jan 25, 2018 at 14:25
• Edited to clarify what I meant. Jan 25, 2018 at 17:41

(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.)

• Thank you for this verification. Unfortunately I already know the statement to be true, I am just pondering over the right method to prove it. In particular I expect a rather short argument. In regard to my attempt note that if one could find a Markov chain on a smaller state space than the pairs of strings, in particular a state space of size $\leq \sqrt{n}$, Markov's inequality would conclude. Dec 4, 2017 at 9:26
• @user480881 - How do you "already know the statement to be true"? Dec 4, 2017 at 14:33
• I am doing self studies on the subject of Markov chains and found this in an exercise. Dec 4, 2017 at 15:19
• @user480881 - This is an interesting question, and I would like to brush up on MCs. Would you mind citing the source of the exercise, so I might look into it myself? Dec 5, 2017 at 15:11