Question: 2017 Fall Final - 12
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?
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}$