typical distance on lattice Consider $V=\{1,\dotsc,k\}^d$ a $d$-dimensional lattice with $\{x,y\} \in E$ for $x,y \in V$ whenever $|x-y|_1=1$.
Now we consider the typical distance, i.e. the distance of two uniformly at random chosen vertices $U_1, U_2$. 
The claim is that the typical distance is proportional to $kd$. Can you tell me why? Let $n:=k^d$.
$$d(U_1,U_2)=1/n \sum_{u \in V}1/n  \sum_{v \in V} d(u,v)$$
but I have no idea how to move on. Have you some hints for me?
 A: Just a note on notation: when people say lattice they usually are referring to a set that is "additively closed" in some sense, whereas you're actually considering a hypercube inside a lattice (i.e. it is a subgraph of the lattice $\mathbb Z^d$).
Secondly, the quantity $d(U_1,U_2)$ is actually a random variable. You won't be able to write down a deterministic formula for it. The formula you've written down is the expectation of this random variable. I guess when someone says "the typical value is constant times $kd$", they mean that there are bounds $c_1kd$ and $c_2kd$ that the random variable lies between with high probability (i.e., tending to $1$ as $kd\to\infty$). Actually, when you say "proportional to" it is meaningless if $k$ and $d$ are fixed, so you should say which variable you are sending to infinity.
Lastly, note that the farthest two points can be is exactly $d(k-1)$, so we have an easy upper bound with $c_2=1$ (i.e., it holds with probability $1$). For the lower bound, you can argue that there are only a tiny proportion of points that are within, say, $kd/10$ of any given point.
