Examples of super- and sub- martingale, which is not a random walk, nor a function of such A martingale $X_n$ is defined by these conditions:
(i) That $E|X_n| <\infty$
(ii) That $X_n$ is adapted to $\mathcal{F}_n$ (filtration, i.e. sequence of sigma algebras)
(iii) That $E(X_{n+1} | \mathcal{F}_n) =X_n$ for all $n$
If "$\leq$" in (iii), $X_n$ is a supermartingale. If "$\geq$" in (iii), $X_n$ is a submartingale.
For details, see Richard Durrett, Probability: Theory and Examples p.198ff. (<-- This is a legal copy uploaded by the author himself.) For brevity I will not repeat here.
By now I seem to have poor understanding of this abstract thing, due to lack of examples...><
Indeed, it is straightforward to see, if $X_n$ is an iid sum of rvs, each with positive expectation, then $X_n$ is a submartingale. The same is true for "zero expectation" and "martingale". The same is true for "negative expectation" and "supermartingale".
For example, $X_n =\xi_1+\dotsb+\xi_n$, where $\xi_i$ all iid, observing Bernoulli, with value $\pm 1$, both probability 1/2. Then $X_n$ is a martingale. If $\xi_i =1$ for probability $>1/2$, $X_n$ is a supermartingale. If $<1/2$, $X_n$ is a submartingale.
And thm 5.2.3 of Durrett's book states that: If $X_n$ is a martingale and $\varphi$ is a convex function with $E|\varphi(X_n)| < \infty$ for all $n$, then $\varphi(X_n)$ is a submartingale w.r.t. the same filtration. The same is true for "concave function" (still increasing) and "supermartingale".
However, these conditions seem to portrait only a small subset of (super,sub)-martingales, and my imagination is limited. Are there examples of martingales, supermartingales, and submartingales, which are not random walk (iid sum of rvs), nor are function of a random walk (exploiting the fact of last paragraph)?

Example: Consider a bowl containing $N$ marbles numbered $1,2,\ldots,N$. Choose marbles from the bowl at random, without replacement, until all have been chosen. Let $X_k$ be the number on the $k$th marble selected, and let $\mathcal F_n:=\sigma\{X_k: k=1,2,\ldots,n\}$ for $n=1,2,\ldots,N$. Define the event $B:=\{X_N=1\}$ (This choice of  $B$ is more or less arbitrary.) The sequence of random variables $M_n:=\Bbb E[B\mid\mathcal F_n]$, $n=1,2,\ldots,N$, is a martingale.
Exercise: Show that $M_n=\prod_{k=1}^n 1_{\{X_k\not=1\}}\cdot(N-n)^{-1}$ for $n=1,2,\ldots,N-1$.
