Solution: 2017 Fall Final - 12

Author: Michiel Smid

Question

A bitstring $b_1b_2{\dots}b_n$ of length $n$ is called a palindrome if $$ b_1b_2{\dots}b_{n-1}b_n = b_nb_{n-1}{\dots}b_2b_1, $$ i.e., reading the string from left to right gives the same result as reading the string from right to left.
Let $n \geq 2$ be an even integer. You are given a uniformly random bitstring of length $n$. What is the probability that this bitstring is a palindrome?

(a)

$(1/2)^{2n}$

(b)

$1/2$

(c)

$(1/2)^{n}$

(d)

$(1/2)^{n/2}$

Solution

Well, let’s break it down

Let A be the event that a string of length n is a palindrome
The leftmost bit can be 1 or 0: 2 possibilities
The rightmost bit must be the same as the leftmost bit: 1 possibility
The second leftmost bit can be 1 or 0: 2 possibilities
The second rightmost bit must be the same as the second leftmost bit: 1 possibility
...
The innermost leftmost bit can be 1 or 0: 2 possibilities
The innermost rightmost bit must be the same as the innermost leftmost bit: 1 possibility
$ |A| = 2 \cdot 1 \cdot 2 \cdot 1 \cdot ... \cdot 2 \cdot 1 = 2^{n/2} $
Let S be the set of all bitstrings of length n
$ |S| = 2^n $

$ Pr(A) = \frac{|A|}{|S|} $

$ Pr(A) = {\left( \frac{1}{2} \right)}^{n/2} $