Return to Answer

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with [Perron eigenvector][1] associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define for $0 \le t \lt r,$ $$S_t(n)=\sum_{k \ge 0}\binom{m}{rk+t}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

IThat is the correct bound. for $r=2$ there is no error and $c=0$. For $r=3$ $c=1$ and the error is at worst $\frac{\pm 1}{3}.$ For $r=4$ $c=\sqrt 2$ and for $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt{2}^{n-1}.$ In general it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ Incidentally, the probability to be at position $t$ is $\frac{S_t(n)}{2^n}$ where, as before $$S_t(n)=\sum_{k\ge 0} \binom{n}{rk+t} =\frac{1}{r}\sum_{j=0}^{r-1}\omega^{jt}(1+w^j)^n$$ [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with Perron eigenvector associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define for $0 \le t \lt r,$ $$S_t(n)=\sum_{k \ge 0}\binom{m}{rk+t}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

IThat is the correct bound. for $r=2$ there is no error and $c=0$. For $r=3$ $c=1$ and the error is at worst $\frac{\pm 1}{3}.$ For $r=4$ $c=\sqrt 2$ and for $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt{2}^{n-1}.$ In general it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ Incidentally, the probability to be at position $t$ is $\frac{S_t(n)}{2^n}$ where, as before $$S_t(n)=\sum_{k\ge 0} \binom{n}{rk+t} =\frac{1}{r}\sum_{j=0}^{r-1}\omega^{jt}(1+w^j)^n$$

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with [Perron eigenvector][1] associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define for $0 \le t \lt r,$ $$S_t(n)=\sum_{k \ge 0}\binom{m}{rk+t}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

Is a better bound possible? Yes for a few special small values, for $r=2$ there is no error. For $r=3$ the error is at worst $\frac{\pm 1}{3}.$ But for $r=4$ it pretty spot on. For $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt{2}^{n-1}.$ In general it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ Incidentally, the probability to be at position $t$ is $\frac{S_t(n)}{2^n}$ where, as before $$S_t(n)=\sum_{k\ge 0} \binom{n}{rk+t} =\frac{1}{r}\sum_{j=0}^{r-1}\omega^{jt}(1+w^j)^n$$ [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with [Perron eigenvector][1] associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define for $0 \le t \lt r,$ $$S_t(n)=\sum_{k \ge 0}\binom{m}{rk+t}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

IThat is the correct bound. for $r=2$ there is no error and $c=0$. For $r=3$ $c=1$ and the error is at worst $\frac{\pm 1}{3}.$ For $r=4$ $c=\sqrt 2$ and for $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt{2}^{n-1}.$ In general it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ Incidentally, the probability to be at position $t$ is $\frac{S_t(n)}{2^n}$ where, as before $$S_t(n)=\sum_{k\ge 0} \binom{n}{rk+t} =\frac{1}{r}\sum_{j=0}^{r-1}\omega^{jt}(1+w^j)^n$$ [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with [Perron eigenvector][1] associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}/r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

Is a better bound possible? Yes for a few special small values, for $r=2$ there is no error. For $r=3$ the error is at worst $\frac{\pm 1}{3}.$ But for $r=4$ it is spot on. For $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt(2)^{n-1}.$ In genera it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.

Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$

If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$

If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$

It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$

The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with [Perron eigenvector][1] associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.

LATER Since you asked (twice) let me say something more, though not exactly what you ask. The question is not specific enough. For $r=13$ and $0 \le n \le 12$ we have $ \sum_{k\ge 0} \binom{n}{rk} =1$ but the approximations range from $\frac{1}{13}$ up to $\frac{4096}{13}.$

For fixed $r$ and large $n$ the approximation is good in some sense. I'll take $\omega=\cos(\frac{2\pi}r)+i\sin(\frac{2\pi}{r}).$ Also define for $0 \le t \lt r,$ $$S_t(n)=\sum_{k \ge 0}\binom{m}{rk+t}.$$

Then $$\lim_{n\rightarrow \infty} \frac{S_0(n)}{2^n/r}=1.$$ That might qualify as "good." On the other hand we can say that there is a positive $c<2$ with $$-c^n \lt S_0(n)-\frac{2^n}{r} \lt c^n$$ Specifically $c=|1+\omega|.$ So for $r=13$ one has $c \approx 1.94.$ That might not seem so good, though

• Dividing through by $\frac{2^n}r$ gives the first estimate and
• We can rewrite it as $S_0(n)=(1+o(n))\frac{2^n}r.$

This is because, from the formula you give, $S_0(n)$ is a sum of $r$ terms and $r-1$ of them are of magnitude $|\frac{(1+\omega^j)^n}r| \le c^n/r.$ We could improve the bound to $\frac{r-1}rc^n$ or even $(\frac2r+o(n))c^n.$ Though that is not a big help.

Is a better bound possible? Yes for a few special small values, for $r=2$ there is no error. For $r=3$ the error is at worst $\frac{\pm 1}{3}.$ But for $r=4$ it pretty spot on. For $n$ even the error is $0$ and for $n=2m-1$ it is $\pm 2^m=\sqrt{2}^{n-1}.$ In general it can be that bad sometimes but the errors do fluctuate around that central value.

Those kind of "largest eigenvalue dominates" considerations are behind the proofs of limiting distribution for random walks on certain graphs.

My coment was that it is also pretty intuitive that a random walk clockwise on a regular $r$-gon (flipping a coin for stay or move) is as likely to leave you on one corner as another at move $n.$ Incidentally, the probability to be at position $t$ is $\frac{S_t(n)}{2^n}$ where, as before $$S_t(n)=\sum_{k\ge 0} \binom{n}{rk+t} =\frac{1}{r}\sum_{j=0}^{r-1}\omega^{jt}(1+w^j)^n$$ [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory