Examples of discrete time martingales In probability, a martingale is given by a sequence of integrable 
  random variables $(S_n)$ and an increasing sequence of 
  $\sigma$-algebras ${\cal F}_n$ such that
  $S_n$ is ${\cal F}_n$-measurable and 
  $E(S_{n+1} \mid {\cal F}_n) = S_{n}$.
This is an important notion because there are many results concerning
  convergence of martingales sequences, e.g. if it is bounded in $L^2$
  then it converges in $L^2$ norm and $a.e.$
If $X_i$ is a sequence of i.i.d. random variables and 
  ${\cal F}_n = \sigma(X_i, i\leq n)$, then the following sequences 
  are martingales:


*

*$S_n - E(S_n)$, 

*$ \exp(S_n)/E(\exp(S_n))$, 

*$(S_n)^2-E(S_n^2)$, 
These are used in the theory of random walks to compute e.g. the mean time before reaching a given state.
Are there any other interesting examples of discrete time martingales?
 A: $\newcommand{\bN}{\mathbb{N}}$ $\newcommand{\eF}{\mathscr{F}}$ $\newcommand{\si}{\sigma}$
Branching processes Set $\bN_0=\{0,1,2,\dotsc\}$. Fix a probability measure $\mu$ on $\bN_0$ such that
$$
m:=\sum_{k\in\bN_0}k\mu\bigl(\,\{k\}\,\bigr)<\infty
$$
and $\mu(\{k_0\})>0$ for some $k_0>1$. Consider next a sequence $(X_{n,j})_{j,n\in\bN_0}$ of i.i.d. $\bN_0$-valued random variables   with common probability distribution $\mu$. Fix $\ell\in \bN_0$, $\ell>0$,  set $Z_0=\ell$. For  $n\in\bN_0$ define
$$
Z_{n+1}=\sum_{j=1}^{Z_n} X_{n,j},\;\;\eF_n=\si\bigl(\, X_{k,j};\, k\in\bN_0, k<n\,\bigr).
$$
The random variable $Z_n$  can be interpreted as the population of the $n$-th generation of a species that had $\ell$ individuals at $n=0$ and such that  the number of offsprings of a given individuals is a random variable with distribution $\mu$.  
Then $Y_n=m^{-n}Z_n$ is a martingale.
Polya's urn scheme  An urn contains $r>0$ red  balls and $g>0$ green balls. Fix an integer $c\geq 0$.  Every unit of  time, we draw a ball, and we replace it by $c+1$ balls of the same color as the one drawn. Denote by $R_n$  and $G_n$ the number of red and respectively green balls in the urn after the $n$-th draw, and set 
$$
X_n:=\frac{R_n}{R_n+G_n},\;\;\eF_n=\si(R_0,G_0,\dotsc , R_n, G_n).
$$
Then $(X_\bullet)$ is an $\eF_\bullet$-martingale.
Markov chains Suppose that $(X_n)_{n\in\bN_0}$ is a Markov chain with  countable state space $E$ and  transition matrix $P=\big(P(i,j)\big)_{i,j\in E}$ $\newcommand{\bP}{\mathbb{P}}$ $\newcommand{\bR}{\mathbb{R}}$
$$
P(i,j)=\bP(X_{n+1}=j|X_n=i).
$$
For any function $f: E\to \bR$ we define $Pf:E\to\bR$
$$ Pf(i)=\sum_jP(i,j)f(j). $$
Then the sequence $$Y_n= f(X_n)-\sum_{k=0}^{n-1}\Big( Pf(X_k)-f(X_k)\;\Big) $$
is a martingale.
Doob martingale  Suppose that  $f:[0,1]\to\bR$ is an integrable   function. Denote by $\eF_n$ the sigma algebra generated by  the intervals $I_{k,n}:=\big(\;(k-1)/2^n, k/2^n\;\big)$, $k=1,\dotsc ,2^n$. 
Define $f_n:[0,1]\to\bR$
$$
f_n(x)= 2^n\int_{I_{k,n}} f(t) dt ,\;\;x\in I_{k,n}. 
$$
Then the sequence $(f_n)$  is an $\eF_n$-martingale.
A: *

*If $X$ is an integrable random variable and $\left(\mathcal F_n\right)_{n\geqslant 1}$ is a filtration, then $X_n:=\mathbb E\left[X\mid\mathcal F_n\right]$ is a martingale. It is worth mentioning that the sequence $\left(X_n\right)_{n\geqslant 1}$ converges in $\mathbb L^1$ and almost surely to $\mathbb E\left[X\mid\mathcal F\right]$, where $\mathcal F$ is the $\sigma$-algebra generated by $\bigcup_{n\geqslant 1}\mathcal F_n$ (this is known as the martingale convergence theorem).     

*Martingale with stationary increments have been intensively studied. The setting is the following. We have a probability space $\left(\Omega, \mathcal F,\mu\right)$ and an invertible map $T\colon\Omega\to\Omega$ which is bi-measurable and measure preserving. For any function $f\colon\Omega\to\mathbb R$, the sequence $\left(f\circ T^j\right)_{j\geqslant 0}$ is strictly stationary and each strictly stationary sequence can be represented in this way. Now, let $\mathcal F_0$ be a sub-$\sigma$-algebra of $\mathcal F$ such that $\mathcal F_0\subset T^{-1}\mathcal F_0$. In this way, $\left(T^{-i}\mathcal F_0\right)_{i\geqslant 0}$ is a filtration. If $m$ is an $\mathcal F_0$-measurable function such that $\mathbb E \left[m  \mid T\mathcal F_0 \right]=0$, then the sequence $\left(\sum_{i=0}^{n-1}m\circ T^i\right)_{n\geqslant 1}$ is a martingale. The partial sums satisfy good deviation and moment inequalities. Moreover, in this setting, the sums of conditional variances is of the form $ \sum_{i=0}^{n-1}f\circ T^i$ where $f=\mathbb E\left[m^2\mid T\mathcal F_0\right]$ hence can be handled with the maximal ergodic theorem.            
A: Change of probability
An old remembrance, and I don't daily practice maths for a long time, so please correct me if I'm wrong. Let ${(\mathcal{F}_n)}_{n \geq 0}$ be a filtration on $(\Omega, \mathcal{A}, \mathbb{P})$. Introduce a new probability $\mathbb{Q} = D.\mathbb{P}$ (i.e. $D=\frac{d\mathbb{Q}}{d\mathbb{P}}$). Then $\mathbb{Q}_{|\mathcal{F}_n} = D_n . \mathbb{P}_{|\mathcal{F}_n}$ and $(D_n)$ is a martingale.
A: If you're interested in a somewhat off-beat example of a discrete martingale, you could look at 
Rafe Jones, Iterated Galois towers, their associated martingales, and
the $p$-adic Mandelbrot set, Compos. Math. 143 (2007), 1108-1126.
This is really a result in discrete dynamics over finite fields, and Jones uses tools from number theory (Galois theory, chebotarev density theorem) to show that a certain system constructed by iterating polynomials over finite fields is a martingale, and he then uses the convergence of martingales to deduce his final result.
(For those who don't have access to Compositio, there's a pre-print version on Jones's website: http://www.people.carleton.edu/~rfjones/Preprints/Jones_Iterated_Towers_Homepage.pdf)
