Let $G$ be a graph on $n$ vertices. Is it possible to calculate the expected number of distinct vertices seen in a simple random walk of length, say, $k < n$? Moreover, how is this affected when $G$ is drawn from the Erdos-Renyi model, $G(n,p)$?
My approach to this so far has been to define an indicator variable $X_i$ which is one if and only if the vertex, say $x_i$, at step $i$ in the random walk has not been seen before. Then by linearity of expectation do something along the lines of (if $x = \sum X_i$ ):
$$ E(X) = E(\sum_{i=1}^k X_i) = \sum_{i=1}^k P(X_i = 1) $$
The problem with this is that the $P(X_i = 1)$ vary quite dramatically so are difficult to control.
My intention is to use the number of distinct vertices seen in a $k$-length random walk in order to distinguish between an Erdos-Renyi random graph and a planted partition random graph.
The idea is indeed to have a variable $A_i$ that counts the number of active vertices at each step. If $D$ is the degree distribution of the graph $G$, the expected number of active vertices at the next step is obtained taking $d \sim D$. Since we remove the vertices from the pool, that changes $D$ to a new distribution $D'$. If there are many vertices, this change is going to be small, and we can approximate the random walk by reusing $D$. So you can take this simpler process, and use a coupling to give bounds on random walks.
In the case of the Erdos-Renyi model, $G(n,c/n)$, the simpler process above is a Galton-Watson process with distribution $\mathrm{Poi}[c]$. Combining couplings from above and from below with extinction properties of the Galton-Watson process allows you to deduce the expected number of distinct vertices.
For more complex models, you need to have a more complex branching models, but the idea is the same. It is, however, far from trivial.
An introduction to random walks can be found in Durrett's books, "Probability: theory and examples", and "random graph dynamics". In particular in the latter he delves into random walks on more elaborate random models (like the preferential attachment graphs and graphs over a fixed degree distribution).