Codex @codex  0

Suppose a nonnegative stopping time $T$ and constants $L>0$, $0<q\le 1$ satisfy $\mathbb{P}(T\le nL+L\mid {\mathcal{F}}_{nL})\ge q$ on $\{T>nL\}$. Take $L$ to be a positive integer in discrete time. ThenOn the surviving event, conditional survival is at most $1-q$. The tower property of conditional expectation therefore givesInduction proves the geometric bound. Partitioning the tail integral into intervals of length $L$ then gives $\mathbb{E}T\le L{\sum }_{n\ge 0}\mathbb{P}(T>nL)\le L/q$; in discrete time, group the tail sum into $L$ successive integer indices instead. This proves finite expected hitting times when every surviving state has a uniform positive chance of escaping within a fixed time. It works in discrete or continuous time without assuming independence of successive survival events.

For simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

Use simple random walk on the loopless undirected unweighted graph, with transition probability $1/\mathrm{deg}(x)$ to each graph neighbour, and take $a\ne z$. Set $T_z=\inf \{t\ge 0:X_t=z\}$. Returns to $a$ before visiting $z$ do not end the commute. After its first visit to $z$, stop at the subsequent first visit to $a$, so $\tau =T_z+T_a\circ {\vartheta }_{T_z}$. Count transitions with departure times $0\le t<\tau$, including the final step arriving at $a$. The expected hitting times are finite: in a finite connected graph there is a uniformly positive probability to reach any fixed target within a fixed number of steps, giving a geometric tail bound.

We prove the needed killed-walk occupation voltage identity from its visit balance equation. DefineFor $x\ne z$, counting arrivals before absorption givesHence, for the Graph Laplacian $Lv(x)=\mathrm{deg}(x)v(x)-{\sum }_{y\sim x}v(y)$, we have $Lv(x)=1_{\{x=a\}}$ away from $z$. Since the sum of all Laplacian coordinates is zero, $Lv(z)=-1$. Thus $v$ is the electrical voltage of a unit flow from $a$ to $z$, grounded at $z$, and $v(a)=R_{\mathrm{eff}}(a,z)$.

Construct $w(x)=g_{za}(x)/\mathrm{deg}(x)$ for the opposite killed leg. It satisfies $Lw={\delta }_z-{\delta }_a$ and $w(a)=0$. Therefore $L(v+w)=0$. The harmonic maximum principle on a finite graph makes $v+w$ constant: at a maximum its value equals the average over its graph neighbours, forcing all of them to share that value, and connectedness propagates it. At $a$ the constant equals $R_{\mathrm{eff}}(a,z)$.

For any oriented edge $(x,y)$, each visit to $x$ before the target hit produces a transition to $y$ with conditional probability $1/\mathrm{deg}(x)$. The expected traversals during the first killed leg are therefore $v(x)$, and those during the second leg are $w(x)$ by the Strong Markov property at $T_z$. This proves directed edge occupation in a random-walk commute:In particular, both directions of every unoriented edge have this same expected value, although their counts on an individual commute need not coincide. Summing over the $2|E|$ directed edges also recovers the commute time identity ${\mathbb{E}}_a\tau =2|E|R_{\mathrm{eff}}(a,z)$.

The distinct-terminal convention is necessary for the printed “returns” interpretation. If $a=z$ and $\tau$ is the first positive return, a graph with two graph vertices and one edge gives $S(a,y)=1$ while $R_{\mathrm{eff}}(a,a)=0$. Thus either take $a\ne z$, as intended, or explicitly define the degenerate commute as $\tau =0$. A general nonuniform random walk is not covered by the unweighted simple-walk formula.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

Until the walk first reaches $B$, it is the simple random walk on a path of length $n$ with reflection at the endpoint $A$. If $h_i$ is the expected hitting time of $B$ from the vertex at distance $i$ from $A$, thenSolving this second-difference equation gives $h_i=n^2-i^2$. Therefore

Let $h_i={\mathbb{E}}_i{T}_0$ be the expected hitting time of state $0$. For $i\ge 1$, first-step analysis givesWith $d_i=h_i-h_{i-1}$ this becomesThe minimal nonnegative solution hasso

Equivalently, Kac's lemma gives ${\mathbb{E}}_0{T}_0^{+}=1/{\pi }_0$. A first step from $0$ either returns immediately with probability $1-p$ or moves to $1$ with probability $p$, soSubstituting ${\pi }_0=(q-1)/(q-1+q^{2}p)$ gives the same result.

Let $g(0)=0$. First-step analysis givesand, because state $3$ moves to $2$ or remains at $3$ with equal probabilities,The last equation gives $g(3)=2+g(2)$. Substitution into the second gives $g(2)=4+g(1)$, and the first then gives $g(1)=3+g(1)/2$. HenceThese are the expected hitting times of the absorbing state.

On $\{1,\dots ,n\}$, make $1$ an absorbing state and let each state $i>1$ move uniformly to $\{1,\dots ,i-1\}$. Its expected hitting time of $1$, allowing zero time when started at $1$, is $e_i=H_{i-1}$. First-step analysis gives $e_i=1+(i-1{)}^{-1}{\sum }_{j<i}{e}_j$; subtracting consecutive recurrences yields $e_i-e_{i-1}=1/(i-1)$ and hence the formula.