Random walk on a circle of 10 state. What is the expectation of times it hits its starting state after 100 steps. Let's say it move to left state with probability 0.25 and right state 0.25 and stays where it is with probability 0.5. One approach of would be brute-force: enumerate through all its possible paths with 100 steps. But that is not general and does not work for larger total steps. What are some of the standard approaches to this problem?
Edit: it is interesting to see bounds if expectation is hard to get. I thought one way is to bound return times, which is somewhat like gambler ruin problem. 
 A: EDIT: This answered a different question than what the OP asked.
The generating function for the net number of rightward steps minus leftward steps, weighted by their probabilities, is $(0.5+0.25x+0.25x^{-1})^{100}$. You want the sum of the coefficients of $\dots, x^{-20}, x^{-10}, x^0, x^{10}, x^{20}, \dots$, which can be just expanded out or even calculated more quickly using $10$th roots of unity.
A: Let $p$ be the move probability and $1-2p$ be the stay probability so $2p+1-p=1$. At time $n$, the probability of hitting state $i$ is $P_i(n)=P_{i-1}(n-1)q+P_i(n-1)p+P_{i+1}(n-1)p$, where the indices are modulo the size of the circle $N$. This gives you a circulent-matrix of equations to solve. You can find a full solution here. It relies on diagonalizing $P=U\Lambda U^*$, and then showing the eigenvalues are $\lambda_m = p\exp(-{2\pi i m/N})+(1-2p)+p\exp(-{2(N-1)\pi i m/N})$. The eigenvectors are less pretty.
This will allow you to find $P_0(n)$, by looking at $[P^n]_{00}$, which I'm not sure if it has a nice explicit form. 
Now that you know $P_0(n)$ for all $n$, by linearity of expectation, the expectation of the total number of hits is $\sum_{t=1}^{100}P_0(k)$. 
A: Building off of Greg Martin's answer...
The probability of landing on the start state after $n$ steps is the sum of the coefficients of $x^{10m}$ in the probability generating function $P(x)^n=(\frac12+\frac14x+\frac14x^{-1})^n$, over all $m\in \mathbb Z$. This can be calculated as $\frac1{10}\sum_{k=0}^9 P(\zeta^k)^n$, where $\zeta$ is a primitive tenth root of unity. The expected number of landings on the start is the sum of these probabilities, so
$$
E[\text{# times land on start}]=\sum_{n=1}^{100}\frac1{10}\sum_{k=0}^9 P(\zeta^k)^n=\frac1{10}\sum_{k=0}^9\frac{P(\zeta^k)-P(\zeta^k)^{101}}{1-P(\zeta^k)}
$$
