Assignment:
Some data link protocols for binary transmissions over serial lines, such as the high-level data link control (HDLC) protocol, the beginning and the end of a data frame are delimited by a predefined sequence of bits, called frame sync sequence (FSS). The bit sequence 01111110 containing six adjacent 1 bits is commonly used as FSS. To ensure that this pattern never appears in normal data, the transmitter adds a 0 bit after every five consecutive 1s. In this manner, the FSS can only appear at the beginning and end of the frame, but never in the data part. The extra bits, called stuffed bits, are removed by the receiver before passing the data to the upper layer. Note that, to avoid ambiguities at the receiver, the stuffed bit is added after every sequence of five 1s, even if the following data bit is 0, which could not be mistaken for a sync sequence.
In this way, the receiver can unambiguously distinguish stuffed bits from normal bits. This technique is called zero-bit insertion or, more generally, bit stuffing. Now, consider a binary message of infinite length that has to be transmitted over a serial line using the zero-bit insertion technique. Assuming that each bit of the message takes the value 0 with probability q and 1 with probability p = 1 - q, independently of the other bits, we wish to determine the asymptotic percentage of stuffed bits in the message transmitted over the line.