Problem: Let $S_n$ denote the position of a simple random walk after $n$ steps, that is, $S_n=X_1+\cdots+X_n$ with $X_i$ i.i.d. and $P(X_i=1)=P(X_i=-1)=1/2.$
For which polynomials $g(x)$ will $g(S_n)$ be a martingale? (Here the coefficients of $g$ cannot depend on $n$.)
My Thoughts: I have the following. Let $g(x)=a_mx^m+a_{m-1}x^{m-1}+\cdots+a_0$ be a generic polynomial. Then $g(S_n)$ is a martingale if and only if $$E[g(S_{n+1})\mid\mathcal F_n]=g(S_n)\quad\text{for all }n\geq1.$$ Hence if and only if $$E\left[a_mS_{n+1}^m+a_{m-1}S_{n+1}^{m-1}+\cdots+a_0\mid\mathcal F_n\right]=a_mS_n^m+a_{m-1}S_n^{m-1}+\cdots+a_0.$$ So we need to compute the conditional expectation on the left. By linearity, we have $$E\left[g(S_{n+1})\mid\mathcal F_n\right]=a_mE\left[S_{n+1}^m\mid\mathcal F_n\right]+a_{m-1}E\left[S_{n+1}^{m-1}\mid\mathcal F_n\right]+\cdots+a_0.$$ Now we look at each term separately. Using the binomial theorem and the fact that $X_{n+1}$ is independent of $\mathcal F_n$ we get \begin{align*} a_mE\left[S_{n+1}^m\mid\mathcal F_n\right] &=a_mE\left[(S_n+X_{n+1})^m\mid\mathcal F_n\right]\\ &=a_mE\left[\sum_{k=0}^m\binom{m}{k}S_n^kX_{n+1}^{m-k}\mid\mathcal F_n\right]\\ &=a_m\sum_{k=0}^m\binom{m}{k}S_n^{k}E\left[X_{n+1}^{m-k}\mid\mathcal F_n\right]\\ &=a_m\sum_{k=0}^m\binom{m}{k}S_n^kE\left[X_{n+1}^{m-k}\right]. \end{align*} From the calculation above we see that in order for the martingale property to be satisfied, the coefficients will have to depend on $n$, since so do the higher moments of $X_{n+1}$. Therefore, the only polynomials that satisfy the martingale property are $g(x)=x+a$ for constant $a$.
Do you agree with my reasoning above?
Thank you for your feedback.
Actually, $X_{n+1}^{m-k}$ has the same distribution as $X_{1}^{m-k}$ hence the expectation of this term does not depend on $n$. We get that $E\left[X_{n+1}^{m-k}\right]=0$ if $m-k$ is odd and $E\left[X_{n+1}^{m-k}\right]=1$ if $m-k$ is even.
One finds that $2E\left[g(S_{n+1})\mid\mathcal F_n\right]=g(S_n-1)+g(S_n+1)$ hence $g(S_n)$ is a martingale if and only if $$ 2g(S_n)=g(S_n-1)+g(S_n+1)\mbox{ a.s.}. $$ As $S_n$ takes the values $2k-n$, $0\leqslant k\leqslant n$, with positive probability, we get in particular that $2g(n)=g(n-1)+g(n+1)$ for each $n$. Letting $P\colon x\mapsto 2g(x)-g(x-1)-g(x+1)$, we can see that $P$ is a polynomial having infinitely many roots hence $2g(x)=g(x-1)+g(x+1)$ for each real number $x$. Now, defining $Q(x)=P(x)-P(x+1)$, we can see that $Q(x+1)=Q(x)$ hence $Q$ is constant and this implies that $P$ is a polynomial of degree one.