Clearly, the value of f(X) for any X is bounded from above by one more than X's out degree in Gf. Summing this over all vertices, we get the number of edges in Gf plus the number of vertices in Gf, which is certainly no greater than the number of edges plus the number of vertices in G.
Thus, we have an upper bound for g(d,n) as one more than the number of edges in G divided by nd. This equals 1+d(n-1)nd-1/nd = d(1-1/n)+1.
g(d), the limit when n tends to infinity, therefore has d+1 as an upper bound.
We prove that this is also the lower bound by construction.
Let H(X) be the L1 distance from X to the boundary of [1,n]d.
Let F(X) be Σi=1...d i Xi mod (2d+1)+1, where Xi is the i'th coordinate of X.
Let f(X) be the minimum between H(X) and F(X). This function clearly satisfies the requirements.
For a large n, the effects of the boundary on the mean of f are negligible, so we can consider F instead, even though F does not satisfy the stipulated conditions at the boundaries.
The sum of F(Y) over any X and all its neighbors, except at the boundaries, is Σi=1...2d+1 i. Summing this over all X counts every Y (except at the boundaries) 2d+1 times. The mean is therefore Σi=1...2d+1 i/(2d+1)=d+1, which is the same as the upper bound, therefore proving that the bound is tight.
g(d)=d+1.