Tiempo esperado para ir de abajo a la izquierda a arriba a la derecha en un cuadrado

Question

Considerar dos dimensiones de paseo aleatorio de inicio en la esquina inferior izquierda de una $n$ $n$ plaza. En cada paso que usted toma un paso hacia arriba, hacia abajo, a la izquierda o a la derecha de la distancia de $1$. Cada elección tiene igual e independiente de la probabilidad de $1/4$. La única excepción es si el $x$ o $y$ coordinar es $0$ o $n$, que es tocar una pared de la plaza. Como usted nunca camine fuera de la plaza, si son de tocar una pared que usted elija una de las opciones disponibles de nuevo con la misma probabilidad.

¿Cuál es el tiempo de espera para llegar a la esquina superior derecha de la plaza asintótica?

Intuitivamente parece que se debe de tomar algo como $n^3$ tiempo asintóticamente, pero no sé cómo derivar este matemáticamente.

Answer 1

Por simetría, esto es $\frac12C_n$ donde $C_n$ indica el tiempo de viaje entre dos esquinas opuestas de la discreta cuadrado del tamaño de $n\times n$. Exacto asymptotics de $C_n$ al $n\to\infty$ puede ser desconocido, pero que, para cada gráfico, el tiempo de viaje $C_{uv}$ entre algunos vértices $u$ $v$ es $$C_{uv}=2mR_{uv},$$ where $m$ is the total number of edges and $R_{uv}$ the effective resistance between $u$ and $v$. Also, $R_{uv}\leqslant L_{uv}$ where $L_{uv}$ is the length of the shortest path from $u$ to $v$. En el presente caso, $m=2n^2$ $L_{uv}=2n$ por lo tanto $$C_n\leqslant8n^3.$$ On the other hand, for every graph on $k$ vertices, $C_{u,v}\geqslant k\log k\,(1+s(1))$ hence, in the present case, $$C_n\geqslant2n^2\log n\,(1+o(1)).$$ Por esto y mucho más, ver el paseo Aleatorio en los gráficos: una encuesta por László Lovász.

Edit: Un análisis cuidadoso de los valores propios y los vectores propios de los asociados Laplaciano (ver allí) muestra que, para cada $n$, la resistencia efectiva $R_n$ entre dos esquinas opuestas de la plaza de la celosía de tamaño $n\times n$ es tal que $$R_n\lt6+4\log n,$$ hence $$C_n\leqslant16n^2\log n+O(n^2).$$