Probability that a randomly selected bit string of length 15 is a palindrome

Question

Question: what is the probability that a randomly selected bit string of length $15$ is a palindrome?

My partial solution is that I know the $15$ length is "$10001010100001$". That's all I know. Can someone help me find and understand the solution?

Answer 1

Well you know that you need the first 7 bits to match the last 7 bits for the string to be a palindrome.

First thing to think about is how many ways can we arrange 7 bits?

Answer: $$2\times2\times2\times2\times2\times2\times2=2^7$$

However, don't forget that the $8^{th}$ bit can be either a 1 or a 0. So if the $8^{th}$ bit is a 1 that cuts the number of combinations in half (i.e., $2^7/2$) and similarly if the $8^{th}$ bit is a 0.

Now, we want to know what the probability that a randomly selected bit string of length 15 is a palindrome. For convenience, define the event $E$ as the case that a string of length 15 is a palindrome. Well, we have the following:

\begin{align*} Pr(E) = Pr(&\text{First 7 bits} = \text{Last 7 bits and the } 8^{th} \text{ bit = 1}\text{ or }\\ &\text{First 7 bits} = \text{Last 7 bits and the } 8^{th} \text{ bit = 0})\\ =Pr(&\text{First 7 bits} = \text{Last 7 bits and the } 8^{th} \text{ bit = 1})+\\ &\text{First 7 bits} = \text{Last 7 bits and the } 8^{th} \text{ bit = 0})\\ =&\frac{1}{2^7/2}+\frac{1}{2^7/2}\\ =&\frac{1}{2^7} \end{align*}

Answer 2

A palindrome is a string that reads the same backwards as forwards.   Basically, that's symmetry.

So you want the probability that the last $7$ digits are exactly the same as the first $7$ digits, though in reverse order.

Answer 3

Hint:

You can calculate all ways of arrangement of $0$ and $1$ for the first $7$ places. The last $7$ places have to be ordered mirror imaged. Thus they have not be regarded. Then regard that at the 8th place of the string can be a $1$ or a $0$.

Answer 4

For every first 7 bits you need last 7 bits to match in a defined way.

First 7 bits can be arbitrary. So the answer is 1/(2^7)

In general answer is 1/(2^floor(stringlength/2))

Answer 5

For a string of length $n$, the probability of finding a palindromic string should simply be the number of possible palindromic combinations divided by the number of total possible combinations.

For both an even and odd string of length $n$, the total combinations is simply $2^n$. The number of palindrome combinations, however, depends on whether the string is even or odd.

For even, only the first $\frac{n}{2}$ elements of the string are free (the remainder are determined once the first $\frac{n}{2}$ are selected) and so the probability is

EVEN string: $\frac{1}{2^{n/2}}$

For odd, the first $\frac{n+1}{2}$ are free since the middle digit is along the line of symmetry. So, the probability in this case is,

ODD string: $\frac{1}{2^{(n-1)/2}}$

Note that the even case is equivalent to the odd case + 1.

So, your string of length 15 being a palindrome has the same probability of a string of length 14:

$\frac{1}{2^7}$