\documentclass[12pt,a4paper]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{enumitem}
\usepackage{parskip}
\usepackage{titlesec}
\titleformat{\section}{\large\bfseries}{}{0em}{}

\begin{document}

\begin{center}
    {\Large \textbf{The Problem of $n$ Liars and Markov Chains}}
\end{center}

\vspace{1cm}

\begin{center}
    \textbf{Name:} \underline{\hspace{6cm}} \hfill \textbf{Date:} \underline{\hspace{3cm}}
\end{center}

\vspace{1em}

\section*{Question 1}
In Feller’s version of the liar problem, each statement either repeats or negates the previous one, leading naturally to a two–state Markov chain.

Explain why some generalisations of this problem may require an $N$–state Markov chain instead of two.  
You may describe or propose a variant of the liar problem where $N>2$ states are essential for a full probabilistic description.

\newpage
\section*{Question 2}
Let $(X_i)_{i\ge1}$ be independent Bernoulli random variables taking values $0,1$ with $\Pr(X_i=1)=p$.  
Define addition modulo $2$, so that $1+1=0 \pmod{2}$, $0+1=1=1+0 \pmod{2}$, and $0+0=0\pmod{2}$.  
Let
\[
S_n = X_1 + X_2 + \dots + X_n \pmod{2}.
\]
Note that $S_n$ can only take values $1$ or $0$. Explain how this process $(S_n)$ is related to the liar problem.  
What quantity in the liar chain corresponds to $S_n$, and how does its parity determine whether the final statement is true or false?
[Hint: First argue that $S_n = 1 \mod 2$ iff there are odd number of 1s in the sum.]
\vspace{10cm}

\end{document}
