John Cochrane a pretty good article titled "New Facts in Finance" in 1999 which summed up some of the developments in finance over the past 15 years back then. One of which deals with EMH and random walks.
Random walks = returns are not predictable. Therefore, the expectation of return at time t+1 at time t is simply the return at time t. The problem with random walks are 2 fold. The assumptions for RW is that it requires rational investors, which means that there should be no unexploitable profit opportunities. If that is the case then investors should not waste money on fundamental analysis. Also the RW model is too restrictive. There is evidence of volatility clustering using real data and residuals are not iid.
However, the new view (then in 1999) is that over long-horizon returns are predictable and it builds with horizon. Daily returns or month-to-month returns are unpredictable, annual returns may be slightly predictable but 5-10 year returns are quite predictable. This brings us to the martingale model proposed by Paul Samuelson, which is the foundation of market efficiency and resolves problems associated with the RW. Specifically, EMH as implied by the martingale requires the specification of information set for which the expectation of return is conditional on. This is why there are 3 forms of EMH: weak, semi-strong and strong.
So to answer your question regarding the distinction between RW and EMH:
- RW model restricts all conditional moments of r_t+1 but a martingale model only restricts the first moment (i.e. conditional expected returns).
- Martinagle model is consistent with bull and bear market but not the RW model.
- Martingale model is equivalent with the Present Value Model, the RW model is not.
Predictor variables
You are right that book/market or dividend yields have been used to predict. Schiller (1981) and LeRoy and Porter (1981) used dividend yield as example. There is proof that return predictability using persistent variables build with horizon.
Returns are autocorrelated.
For your last question, there are various experiments done to test for autocorrelation. Suppose we find autocorrelation, is that a problem for the martingale model (and the EMH for which it is implied)? If returns are autocorrelated, then as long as past returns are in the information set, then conditional expected returns are no longer constant. Therefore, finding autocorrelation in past returns is a problem for martingale model. Zero autocorrelation does not mean there is a martingale but a non-zero autocorrelation means that there is definitely no martingale. But you are right in the sense that it speaks against EMH. But remember, since we are using the martingale model for the EMH, we suffer a joint hypothesis problem that cannot be solved. We are not sure if our null hypothesis is correctly specified. We are also not sure if the martingale's information set is correctly specified. This will bring us to the variance bound test by Robert Shiller (1981), which attempts to solve the problem.
In conclusion, reality lies somewhere in between. Data and predictor variables showed that the martingale model only provides a framework. RW is too restrictive and is disproved.