Given a knight on an infinite chess board that moves randomly, what's the expected number of distinct squares it reaches in 50 moves? I was asked this in an interview and wasn't sure how to frame the answer. Basically as in the question you have a knight on an infinite chess board and it chooses one of its valid 8 moves uniformly at each move. After 50 moves, the question was to give (as tight as possible) a lower and upper bound on the expected number of distinct squares it reached.
I got as far as realizing that the knight must live in a 200x200 square, and that it can only reach half of the squares (since it must end at the same colour as it started). However this doesn't really address the randomness aspect of the question. 

My experiments in Mathematica give $40.06$ as the average number of distinct cells (I've done several tries for $100'000$ trials).
I'm counting the initial square though, because it makes the program more simple.
I wouldn't know how to approach this problem theoretically, but it's simple enough to do tests. Knight's moves shift it $2$ cells in one direction and $1$ cell in the other direction. Which gives us $8$ options on an infinite board.
Here's the code I used and a sample of the results:
Tm = 100000;
Ds = Table[1, {t, 1, Tm}];
Do[
  Nm = 50;
  P = Table[{0, 0}, {n, 1, Nm}];
  M = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 
     1}, {-2, -1}};
  Do[R = RandomInteger[{1, 8}];
   P[[n + 1]] = P[[n]] + M[[R]], {n, 1, Nm - 1}];
  Ds[[t]] = CountDistinct[P], {t, 1, Tm}];
Histogram[Ds]
N[Mean[Ds], 10]


Note that the distribution is asymmetrical.
Increasing the number of steps to $100$ I get around $77.36$. Which agrees well with the $4/5$ ratio.
Made $1'000'000$ tests with $100$ steps and got $77.38$, so the numbers don't change much for larger samples.
I wonder how we can get the $4/5$ estimate theoretically.

In general, this falls under the topic of random walks and their return probabilities.

Edit It would be better to set $N_m=51$ in my program, then it corresponds to $50$ moves and the resulting average $40.82$ fits well with the other answer.
