Main question:
$\lim_{s\to\infty}\frac{E[X]}{3s}$
where $X$ is a discrete random variable with probability mass function:
$P(X=x) = \sum_{n=0}^{3s-x}{{s+1+n}\choose{n}}{{s-n}\choose{x-2s}} (\frac{1}{2})^{2s-1} $
for $x=2s, 2s+1,... 3s$
*For the edge case of $x=2s$, the final term of the sum ${{2s-1}\choose{s-1}}{{0}\choose{0}}$ is excluded.
Background:
Out of curiosity, I tried to figure out how much time one could save while walking through a grid if they were willing to turn at stoplights instead of waiting for them to turn green.
For the sake of simplicity, it's assumed that walking a block takes one minute and that getting stopped by a red light also takes one minute.
If you refuse to turn, the probability mass distribution for an 8 x 8 grid is:
$P_{dumb}(X=x) = {{16}\choose{x-16}} (\frac{1}{2})^{16} $
For durations from 16 minutes (no delays) to 32 minutes (delay at every intersection). You'll notice that it's simply a binomial distribution with $p=1/2$, shifted to the right sixteen units (to account for necessary walking time).
But if you're willing to turn, PMF is:
$P_{smart}(X=x) = \sum_{n=0}^{24-x}{{7+n}\choose{n}}{{8-n}\choose{x-16}} (\frac{1}{2})^{15} $
For values of x between 16 and 24, inclusive. It should be noted that the edge case of $x=16$, the final term of the sum, ${{15}\choose{8}}{{0}\choose{0}}$, is excluded.
I wanted to generalize this idea and see if the efficiency approaches a limit. The general form of the PMFs for squares with side length $s$ is:
no turn:
$P_{dumb}(X=x) = {{2s}\choose{x-2s}} (\frac{1}{2})^{2s} $
for $x=2s, 2s+1,... 4s$
turn:
$P_{smart}(X=x) = \sum_{n=0}^{3s-x}{{s+1+n}\choose{n}}{{s-n}\choose{x-2s}} (\frac{1}{2})^{2s-1} $
for $x=2s, 2s+1,... 3s$ with the carryover stipulation that the last term of the sum for the case $x=2s$ is omitted.
I ran simulations for larger and larger grids, and it turns out that if we define efficiency as duration cut off from the dumb walk by the smart walk, it hits a limit at $\frac{1}{3}$:
$\lim_{s\to\infty}[100\%-\frac{E[smart]}{E[dumb]}] = \frac{1}{3} $
or, equivalently:
$\lim_{s\to\infty}\frac{E[smart]}{E[dumb]} = \frac{2}{3} $
The thing is that no matter how big the grid gets, the dumb walk in the denominator will always be a binomial distribution of $2s$ trials shifted over $2s$, so the expectation will always be $3s$:
$\lim_{s\to\infty}\frac{E[smart]}{3s} = \frac{2}{3} $
So really I'm trying to prove that the numerator converges to $2s$ plus a negligbly small amount. So all this boils down to: how to determine the limit of the expectation of random variable with PMF $P_{smart}(X=x) = \sum_{n=0}^{3s-x}{{s+1+n}\choose{n}}{{s-n}\choose{x-2s}} (\frac{1}{2})^{2s-1} $ as $s$ gets infinitely large, with the anticipation that it will converge to $2s$.
This is super long and perhaps poorly explained, so please let me know if you'd like more information or you think I screwed something up along the way...