\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{algorithmicx,algorithm}
\usepackage{algpseudocode}
\usepackage{float}

\usepackage{etoolbox}
\usepackage{url}
\usepackage[most]{tcolorbox}
\usepackage{xcolor}
% 0.0in to center
\setlength{\topmargin}{-.53in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textheight}{9in}
%\setlength{\parskip}{\medskipamount}
\setlength{\marginparwidth}{1.2in}
%\renewcommand{\baselinestretch}{1.3}

\lstset{
  language=Python,
  showstringspaces=false,
  formfeed=newpage,
  tabsize=4,
  commentstyle=itshape,
  morekeywords={models, lambda, forms}
}

\newcommand{\eps}{\epsilon}
\newcommand{\E}{\textbf{E}}
\newtheorem{theorem}                {Theorem}
\newtheorem{lemma}      [theorem]   {Lemma}
\newtheorem{remark}     [theorem]   {Remark}
\newtheorem{fact}       [theorem]   {Fact}
\newtheorem{claim}      [theorem]   {Claim}
\newtheorem{corollary}      [theorem]   {Corollary}
\newtheorem{definition}     [theorem]   {Definition}
\newtheorem{prop}       [theorem]   {Proposition}
\newtheorem{warning}        [theorem]   {Warning}

\def\proof{\rm \trivlist \item[\hskip \labelsep{\bf Proof. }]}
\def\endproof{\hfill $\rule{1.3ex}{1.3ex}$ \endtrivlist}

\newcommand{\ip}[2]{
{\langle {#1} , {#2} \rangle}
}
\newcommand{\n}[1]{
{\| {#1} \|}
}
\newcommand{\ns}[1]{
{\| {#1} \|^2}
}

\providetoggle{solution}
\settoggle{solution}{false}

\def\prop{{\em Proposition: }}
\def\L{\mathcal{L}}
\def\N{\mathcal{N}}
\def\C{\mathcal{C}}
\def\Z{\mathcal{Z}}
\def\Q{\mathcal{Q}}
\def\R{\mathcal{R}}
\def\P{\mathcal{P}}
\def\M{\mathcal{M}}
\def\B{\mathcal{B}}
\def\TV{$T \in \mathcal{L}(V)$ }
\def\pf{\noindent {\bf Proof Sketch: }}
%\def\limsup{\overline{\lim}}
%\def\liminf{\underline{\lim}}
\def\sm{\setminus}
\newtheorem{Alg}{Algorithm}
\newcommand{\myalg}[3]{
\medskip
\begin{footnotesize}
\fbox{
\parbox{6.2in}{\begin{Alg}\label{#1}{\textsc{ #2}}\\
{\texttt{ #3}}\end{Alg}
}}
\medskip
\end{footnotesize}}


\newcommand{\bfx}{{\bf x}}
\newcommand{\bfy}{{\bf y}}

\begin{document}

\begin{center}
{\Large CS265/CME309, Problem Set 7}

\begin{tabular}{rl}
SUNet ID(s): & \\
Name(s): & \\
\end{tabular}
\end{center}

By turning in this assignment, I agree by the Stanford honor code and declare that all of the writing is the work of my partner and I (discussion in larger groups is permissible).


\begin{center}
{\large Due by 11:59 PM on \textbf{Tuesday}, November 12th.}
\end{center}


\begin{enumerate}
\item Consider the following schemes for shuffling a deck of 52 cards.  For each scheme, say whether the corresponding chain is irreducible and aperiodic?  If it is, describe its stationary distribution.  [Prove your answers, which shouldnt take more than 1 sentence each.]:
\begin{enumerate}
\item (2 points) At each timestep, select $i,j$ independently from the set $\{0,1,\ldots,51\}$, and take the $i$th card in the stack, and move it to the $j$th location.   Is the corresponding chain irreducible and aperiodic?  If so, what is its stationary distribution? 

\medskip

SOLUTION:  XXXX

\medskip

\item (2 points) At each timestep, select $i$ independently from the set $\{0,1,\ldots,51\}$, and flip a fair coin.  If the coin lands heads, take the $i$th card and move it to location $i+1 \mod 52$, otherwise take the $i$th card and move it to location $i-1 \mod 52$.  

\medskip

SOLUTION:  XXXX

\medskip

\item (2 points) At each timestep, select $i$ independently from the set $\{0,1,\ldots,51\}$, and flip two fair coins.  If the second coin lands heads, perform the scheme from the previous part, otherwise do nothing.
\end{enumerate}

\item (6 points) Consider flipping $n$ fair coins, and let $X_n$ denote the number of coins that land heads.  Prove that, for any integer $k$, as $n\rightarrow \infty$, $\Pr[X_n \mod k = 0] \rightarrow \frac{1}{k}.$  [Hint:  Define a Markov Chain and relate its stationary distribution to the desired probability.]

\item (Infinite Markov Chains) Some of you have asked about Markov chains with infinite state spaces.  Here we explore the analog of the fundamental theorem of Markov chains for such settings.  Given a Markov chain defined over a countably infinite state space, if the chain is irreducible and aperiodic, then either it has a unique stationary distribution $\pi$ s.t.  for all states $i$ and $j$, $\lim_{t \rightarrow \infty} \Pr[X_t=j | X_0 = i] = \pi_j > 0,$  or, for all $i,j$ $\lim_{t \rightarrow \infty} \Pr[X_t=j | X_0 = i] =0.$  In this part you will construct chains with each of these behaviors.
\begin{enumerate}
\item (4 points) Define an irreducible aperiodic Markov chain whose states are the positive integers, s.t. $\Pr[X_t = i | X_{t-1}=j]= 0$ unless $i \in [j-1,j,j+1],$ and where  for all $i,j$ $\lim_{t \rightarrow \infty} \Pr[X_t=j | X_0 = i] =0.$  Define the chain, and give one sentence of explanation--no need for a formal proof. [Make sure your chain is irreducible!]
\item (4 points) Define an irreducible aperiodic Markov chain whose states are the positive integers, s.t. $\Pr[X_t = i | X_{t-1}=j]= 0$ unless $i \in [j-1,j,j+1],$ where the stationary distribution $\pi$ satisfies $\pi_i=\frac{c}{i^2}$ for some constant $c=6/\pi^2 = 1/\sum_{i\ge 1}\frac{1}{i^2}.$   Prove that your chain has the desired stationary distribution.  [Hint: Recall the Metropolis algorithm for constructing chains with a desired stationary distribution.]
\end{enumerate}

\item In this problem we will consider two different models of wealth distribution.  Suppose we are in a world with $n$ people and $100n$ dollars.  At time $t=0$ there is some initial assignment, $X_0$, of dollars to people.

\medskip

\noindent \textbf{Model A:}   At each time $t=1,2,3,\ldots$, the allocation changes according to the following protocol: choose a person uniformly at random from the $n$ players, and call them player $i$; if $i$ has no money, then nothing changes during that time-step; if $i$ has at least one dollar, then select a player, $j$, with probability proportional to the amount of money they currently have, and transfer one dollar from $i$ to $j$ (note that it is possible that $i=j$).  For example, if at time $t$, all players have \$100 then at time $t+1$, with probability $1/n$, all players have \$100, and with probability $1-1/n$, one player has \$101 one has \$99 and the rest have \$100.
\medskip

\noindent \textbf{Model B:}   At each time $t=1,2,3,\ldots$, the allocation changes according to the following protocol: choose a person uniformly at random from the $n$ players, and call them player $i$; then select a player, $j$, with probability proportional to the amount of money they currently have, and transfer one dollar from $j$ to $i$ (it is possible that $i=j$).  [Note that in this model, $j$ pays $i$, whereas in Model A, $i$ pays $j$!!!!]  
\begin{enumerate}
\item (2 points) Note that each model describes a Markov Chain over the ``wealth allocation'' of players.  For each model, say whether the chain is periodic or aperiodic, and give one sentence of justification.
\item (2 points) For each model, say whether the chain is irreducible or not, and give one sentence of justification.
\item (2 points) For each model, say whether or not the fundamental theorem of Markov chains applies, and give a one sentence justification.
\item (4 points) What is the stationary distribution of the Markov Chain described by Model B?  (Prove your answer.) [Hint: Imagine that each of the dollars has a unique number, $1,\ldots,100n$, and think about the state of the system at time $t$ as being a list of which dollars each person has.  Consider the update protocol that  first picks a uniformly random dollar $d$, then picks a uniformly random person $j$, and takes that dollar from whoever has it and gives it to player $j$.  This update scheme is one way of implementing Model B, no?  Now, if you think of the states of this chain as nodes in a graph, the updates look kindof like a random walk on this graph....and you know all about the stationary distribution of random walks on a graph...]
\end{enumerate}
\end{enumerate}
\end{document}


