What is the exact relationship between the efficient-market and random-walk hypotheses? The efficient-market and random-walk hypotheses are often discussed together as formalizations of the idea that "you can't consistently beat the stock market". But in my experience, they're often used interchangeably, and I've never seen anyone carefully explain the difference. (For example, Wikipedia says that A Random Walk Down Wall Street "argues that asset prices typically exhibit signs of random walk and that one cannot consistently outperform market averages. The book is frequently cited by those in favor of the efficient-market hypothesis." The Wikipedia article on the EMH says "there is a very close link between EMH and the random walk hypothesis" and the one on the RWH says that it "is consistent with the efficient-market hypothesis", but neither spells out a precise relationship.)

What is the exact distinction? Is either hypothesis a special case of the other? Put another way, could one imagine a stock market in which either hypothesis holds but the other does not? The EMH page says "Samuelson published a proof showing that if the market is efficient prices will show random-walk behavior", which seems to imply that the EMH is a special case of the RWH - so that one could imagine a stock market in which RWH holds but not EMH, but not the opposite. Is this correct?
They don't have anything to do with each other.  

Use the superscript $e$ to denote "anticipated value" in whatever way it is formed. Then the Efficient Market Hypothesis states

$$X^e_{t+1,market} = E(X_{t+1}\mid I_t)$$

In words, the value anticipated "by the market" equals the true expected value conditional on all information available at time $t$. So first and foremost, the EMH is about what is the predictor that reflects the anticipation of "the market", and it asserts that it is the conditional expected value based on all information available (to state the obvious, there are many other predictors of future values. We can use the median, the mode, etc etc etc).  

By the properties of the conditional expectation we have that

$$X_{t+1} = E(X_{t+1}\mid I_t) + u_{t+1},\;\;\; E(u_{t+1}\mid I_t)=0$$

Therefore the EMH claims that the value anticipated by the market, is off-target only by something ($u_{t+1}$) that cannot be predicted as anything other than zero, given the information available. But that is what it means to "use the information efficiently": to extract from it everything that it can possibly tell you.

The "cannot beat the market" assertion is reflected in the part of the EMH that "the market" forms an expectation as though it was a single mind having available, again, all information. This implies that while "inside", "private" information may matter for what individual agents do and accomplish, if we somehow "average/combine" over those individuals each having a different information set, we will obtain the conditional expected value we would have obtained if we have collected all information in one Information set. 

Nowhere in the above do we mention, or need to mention, what is the Data Generating Mechanism for $X$. It can be anything.