Distribution of a random variable waiting for a consecutive sequence of bits?

Suppose we're trying to transmit a message comprised of $n$ bits. Assume each bit has a probability $p$ of being correct. Success means we succeed at consecutively transmitting all $n$ bits. As soon as an incorrect bit is sent, the transmitter restarts and tries to send the message again from scratch. Let $X$ be the random variable which gives the number of total bits transmitted until the moment of success.

What is the distribution of $X$? It doesn't seem like this is a standard geometric random variable because the "trials" are not Bernoulli - a "success" is a bunch of dependent Bernoulli trials..

I'm not probabilist so I may be missing something simple, but I'm fairly stuck here.

• Your last n bits must be correct. What is the probability of generating n correct bits out of n? Your first m-n bits do not have a correct string of n bits in it. What is the probability of n correct bits out of n in m-n bits and the probability of it not happening?
– Paul
Jan 26, 2016 at 15:23
• @Paul I am afraid that things are more complicated here. For instance if $X>n$ then the $n$ successes at the end must be preceded by a non-succes. I am eager to see an answer to this question. Jan 26, 2016 at 15:38
• "total bits transmitted until the moment of success" It's not clear for me if the trasmitter knows if there were an error (feedback) and if so he retries the transmision. If so, does he knows if after the $n$ block was trasmitted? Jan 26, 2016 at 17:34
• @leonbloy If I understand correctly, you're asking whether, after having sent an incorrect bit, the machine restarts from the beginning or continues to try and transmit the successful bits. You may assume it receives feedback and starts from the very first bit upon having sent the wrong bit. Jan 26, 2016 at 18:14

1 Answer

The problem is not clear, I assume that the trasmitter receives feedback (error or not) after each bit, and that in case of error it resets, ie., it retries the full block trasmision from the start (this makes little practical sense, but...)

Let $T_i \in \{1\cdots n\}$ be the length of the $i$-th block with errors.

Then $T_i$ are iid truncated geometric variables, with $p_j=P(T_i=j)= \alpha p (1-p)^{j-1}$. I leave up to you to compute the normalization factor $\alpha$ and the mean $\mu_T=E[T_i]$.

Let $Y$ be the total number of sent blocks (including the good one). That is itself a geometric variable, with probability of success $p_B=p^n$. Then $E(Y)=1/p_B=p^{-n}$

Now let $X$, the total number of sent bits. Then $X=T_1 + T_2 + \cdots +T_{Y-1}+n$

This means that

$$E[X|Y]=(Y-1) \mu_T+n$$

Hence

$$E[X]=E[E[X|Y]]=(p^{-n}-1) \mu_T+n$$

Update: I missed that you wanted the distribution, not merely the expectation. Well, let $Z=X-n$ be the bits in excess:

$$P_Z(z)=\sum_y P_{Z,Y}(z,y)=\sum_y P_{Z\mid Y}(z,y)P_Y(y)=\\ =\sum_{y=1}^\infty G(z;p,y-1) (1-p^{n})^{y-1}p^{n} =\sum_{k=0}^\infty G(z;p,k) (1-p^{n})^{k}p^{n}$$ where $G(z;p,k)$ is the probability function of a sum $k$ geometric variables with parameter $p$, truncated to $[1\cdots n]$. (Good luck with simplifying that). Of course, $P(X=x)=P_Z(x-n)$

BTW: A more familiar way of presenting this problem is: we throw coins with probability of head $p$. How many coins must we throw till we get a run of $n$ consecutive heads? See eg here http://www.cs.cornell.edu/~ginsparg/physics/info295/mh.pdf

• Thank you for your answer! I am looking for the distribution of $X$, not just its expectation. Do you see a method of calculating $P(X=k)$? Jan 26, 2016 at 23:26