Recurrent random walks with bounded local time at each vertex

Question

Let $c_{n,k}$ be the number of simple random walk trajectories of $n$ steps in $\mathbb{Z}$ starting from the origin such that each vertex is visited at most $k \in \mathbb{N}$ times and define $\mu_k := \lim\limits_{n \rightarrow \infty} ( c_{n,k} )^{\frac{1}{n}}$. When $k=1$, $c_{n,k}$ is the number of self-avoiding walk trajectories of length $n$. When $k= \infty$, it is clear that $ c_{n, \infty} = 2^n, $ and that $ \mu_\infty = 2. $ I am interested determining whether, $$ \lim\limits_{k \rightarrow \infty} \mu_k = 2, $$ is true. Already the easier question whether $\mu_{k+1} > \mu_{k}$ seems to be hard. This is a deep question and I am not able to get an intuition.

Answer 1

Fix some large $k$, and let $j=\left\lfloor\frac{\sqrt k}2-1\right\rfloor$ be a positive integer such that $(2j+1)(2j+2)\leq k$. Consider the set $S$ of sequences in $\{L,R\}^{2j+1}$ (where $L$ denotes a left move and $R$ denotes a right move) with at least $j+1$ copies of $R$; there are exactly $2^{2j}$ of these. Let $n=m(2j+1)+t$ so that $0\leq t<2j+1$, and consider the sequences in $$S^mR^t,$$ i.e. those sequences formed by concatenating $m$ sequences in $S$ with $t$ right moves; there are $2^{2jm}$ such sequences. We claim that each such sequence of moves visits each vertex at most $(2j+1)(2j+2)\leq k$ times. Indeed, say it visits some number $i$ first at time $t$. After this time, it may move at most $j$ steps leftwards before it first encounters the end of some element of $S$ (and thus it will be at at least $i-j$), and then after $(2j+1)$ elements of $S$ it will have moved right at least $2j+1$ steps (since each element of $S$ indicates a net move rightward) and be at step at least $i+j+1$. At this point, since no element of $S$ can ever result in moving more than $j$ cells leftward, the walk will never reach farther left than $i+1$. So, the last time the walk reaches $i$ is less than $(2j+1)(2j+2)\leq k$, and so it can spend at most that many turns at $i$.

This shows that $$c_{n,k}\geq 2^{2jm}=2^{2j\left\lfloor\frac n{2j+1}\right\rfloor}\geq 2^{-2j}\left(2^{1-\frac1{2j+1}}\right)^n,$$ and so $$\mu_k\geq 2^{1-\frac1{2j+1}}\geq 2^{1-\frac1{\sqrt k-4}}.$$ This goes to $2$ as $k\to\infty$.