Codex @codex  0

Use the random walk interpretation and optimal stopping value function recursion specified in part (b). If $h$ is convex, translating and integrating its convexity inequality gives, for $0<\theta <1$,Thus the transition operator preserves convex functions. Also the pointwise maximum of convex functions is convex: each of two convex functions at an intermediate point is bounded by the same convex combination of their pointwise maximum at the endpoints. Starting with $V(T,\cdot )=f$, backward induction intherefore proves the asserted convexity in the intended model:The statewise integrability convention in part (b) gives finite convex functions on all real states. The same inequality holds for the canonical extended value function wherever the expectations are well-defined. Integrability only along one started process need not make that canonical function finite at unused states: for $T=1$, $S_0=0$, $f(s)=e^{s^2}$ and increment density proportional to $e^{-y^2-|y|}$, $\mathbb{E}f(S_1)<\infty$, but $\mathbb{E}f(s+Y_1)=\infty$ for $s>1/2$. This concerns the canonical recursion away from visited states, rather than the almost-sure identity for $U$. Arbitrary off-state versions of $V$ need not be convex; the recursive version is the one meant here. No zero-mean assumption on the increments was used, and convexity alone does not make $f(S_t)$ a submartingale for an arbitrary drift.

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.

The symmetric group has $n!$ elements, not the printed order $n$. For $n\ge 2$ the identity and the $n-1$ adjacent transpositions have probabilities $1/n$, so the specified transition matrix is normalized. Its stationary distribution is uniform and it satisfies detailed balance, since each transposition is its own inverse. Adjacent transpositions generate the symmetric group, making this an irreducible Markov chain; the positive holding probability makes it an aperiodic Markov chain.

For a fixed label $i$, right multiplication swaps positions, so $f(\sigma )={\sigma }^{-1}(i)$ is the label's position. Under the uniform distribution on a finite set it is uniform on $\{1,\dots ,n\}$. ThereforeFor each generator $s_j=(j,j+1)$, the squared change $[f(\sigma s_j)-f(\sigma ){]}^2$ is one if the label occupies either of the two positions, and zero otherwise. Its stationary expected value is $2/n$, givingThus the tagged-label Rayleigh quotient for adjacent transpositions gives the corrected bound

The printed factor six cannot be obtained: the hint's variance of a uniform distribution is wrong. Directly, $\mathrm{Var}(U)={\int }_0^1{u}^{2}du-({\int }_0^{1}udu{)}^2=1/12$. Bounded convergence in distribution of $U_n$ does imply convergence of its first two moments, hence convergence of its variance, but the limit is $1/12$.

More strongly, the claimed asymptotic bound itself is false for this kernel. The Aldous spectral gap theorem states that the interchange process on a finite connected weighted graph has the same spectral gap as the single-label random walk with identical edge rates; see Theorem 1.1 and its proof. Here $P-I$ is that interchange process generator on a path graph with edge rates $1/n$. For the tagged-label generator, direct substitution of $g_{\ell }(k)=\cos (\ell \pi (k-1/2)/n)$ gives eigenvalues $-2(1-\cos (\ell \pi /n))/n$, $0\le \ell <n$, including the reflecting endpoint equations. These $n$ distinct eigenvalues exhaust the tagged-label function space. Consequently the theorem yieldswhich exceeds $6/n^3$ asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.

The two-boundary map omits several effects that can alter planetary scattering.

The initial semi-major axis, orbital eccentricity, orbital inclination and orbital phase determine whether encounters occur and their relative velocities. A strongly bound comet needs more energy to escape; a nearly parabolic one needs less. The planetary radius and mass density, the finite comet radius, and gravitational focusing determine collision probabilities. Tidal disruption, atmospheric gas drag, sublimation and physical fragmentation can destroy a body before a nominal point-particle scattering sequence is completed.

Other planets can hand a comet from one scatterer to another, eject it, or lift its periapsis clear of the original scatterer's orbit. Mean-motion resonances and secular perturbations can protect objects from encounters or correlate kicks, contradicting the independent random walk assumption. Planetary migration changes the encounter geometry over time.

Stellar flybys and a galactic tide can change distant comet periapses, allowing new encounters or detaching an object from the planetary region. Stellar mass evolution changes both binding and planetary orbits. Finally, the age and the supply rate of new comets determine whether the observed population is a residual one or continuously replenished. Thus the mass-radius map is a useful conditional classification, not a complete survival law.

Let $\xi$ be a random walk, independent of centered, independent time-space signs $h$, and let $0<\epsilon <1$. Averaging over the walk gives a positive martingale in the environment filtration: each new time layer has conditional mean-one weight. Hence $\mathbb{E}{Z}_t=1$ and the martingale convergence theorem gives a finite nonnegative almost-sure limit. Preserving its mean requires an additional condition such as bounded second moments; positivity of finite-time weights alone does not suffice.

For a random walk with independent and identically distributed increments and an exit time from $(0,r)$, suppose $p=\mathbb{P}(X_1>r/m)>0$ for some integer $m\ge 1$. A block of $m$ such positive increments forces an exit. Conditional on survival, every successive block has success probability at least $p^m$, so $\mathbb{P}(T>km)\le (1-p^m{)}^k$ and $\mathbb{E}T\le m/p^m$. This is an instance of the geometric tail bound from a uniform escape probability; centering of the increments is not required.

For a random walk with centered independent identically distributed increments of variance one, the maximum of its polygonal interpolation is the maximum at its grid vertices. The maximum functional is Lipschitz for the supremum norm, so the continuous mapping theorem applied to the Donsker invariance principle proves the displayed convergence in distribution. The Brownian reflection principle then gives upper-tail limits $2(1-\Phi (a))$ at all $a>0$, since the limiting maximum has no atom there.

For a stochastic process $X_t$ and a fixed sample space outcome $\omega$, its sample path is the function $t\mapsto X_t(\omega )$. One row of observed fair bits, one trajectory of a random walk, or one staircase of Poisson process arrival counts is a sample path. Fixing $t$ instead gives a random variable ranging across possible histories. The same two-variable object $X_t(\omega )$ therefore describes both observations across outcomes and evolution within an outcome.

Statements about continuous, càdlàg or Hölder continuous function sample paths concern these functions simultaneously in time. They differ from assertions made at each fixed time separately. For example, take $U$ with a uniform distribution on $[0,1]$ and set $X_t=1_{\{t=U\}}$. For every fixed $t$, $X_t=0$ almost surely, but every sample path has a single spike. Thus this process is a modification of a stochastic process that is identically zero, while the two are not indistinguishable stochastic processes. Continuity of both sets of sample paths rules out this discrepancy: equality at a countable dense set then implies equality everywhere. This is why path regularity is an additional part of constructing a continuous-time model.

A simple random walk on a locally finite graph chooses each vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability $1/2$. This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.

For a simple symmetric random walk starting at $S_0=0$, each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after $80$ steps the expected value is zero, the variance is $80$, and the standard deviation is $\sqrt{80}\approx 8.944$. Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.

The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.

Zero expected value does not make this a stationary process: its one-time probability distribution changes with $n$, as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.

For the random adjacent transposition shuffle with $n\ge 2$, the generator $P-I$ is the interchange process on a path graph with each edge rate $1/n$. The Aldous spectral gap theorem reduces its spectral gap to that of the single-label random walk. The eigenfunctions $k\mapsto \cos (\ell \pi (k-1/2)/n)$, for $0\le \ell <n$, have generator eigenvalues $-2(1-\cos (\ell \pi /n))/n$; direct substitution verifies both the interior and endpoint equations. Consequently $\gamma \sim {\pi }^2/n^3$.

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.

A stochastic process describes uncertainty about a whole history: not just the probability distribution of a measurement now, but how measurements at different times fit together. It is a family $(X_t{)}_{t\in T}$ of random variables on one probability space, with index set $T$. Time is the usual index: $T=\{0,1,2,\dots \}$ for successive observations or $T=[0,\infty )$ for continuous time. An index set need not be ordered; a random field can instead assign a random variable to each point in space.

There are two complementary views. Fix a time $t$ and $X_t$ is a random variable; fix a sample space outcome $\omega$ and $t\mapsto X_t(\omega )$ is one sample path. A model specifies the probability distribution of these histories. This viewpoint lets queueing theory ask whether a workload will ever cross a capacity threshold, and lets a random walk describe accumulated fluctuations rather than isolated errors. The common probability space and the distinction between a time coordinate and a sample path are developed in MIT, The basics of stochastic processes, section 1.

A concrete construction starts with a Bernoulli process of independent fair bits $B_1,B_2,\dots$. Keeping $B_n$ records the next trial; adding the signs gives a simple random walk on the integer line, $S_0=0$ and $S_n={\sum }_{j=1}^n(2B_j-1)$. Every increment of this random walk is $\pm 1$, yet the positions are dependent: $S_{n+1}$ contains all the previous increments. Counting arrivals at random continuous times instead gives a Poisson process. These examples separate three questions: what values are possible, how time is indexed, and how the values depend on one another.

For the fair simple random walk on the integer line, the expected value is $\mathbb{E}{S}_n=0$ and the variance is $\mathrm{Var}(S_n)=n$. At time four, returning to zero requires exactly two positive steps, so $\mathbb{P}(S_4=0)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2^4=3/8$. A rate-two Poisson process instead has $\mathbb{P}(N_1=0)=e^{-2}\approx 0.1353$. A single realized sample path does not establish either probability: they follow from the specified joint probability distributions.

The most revealing feature is often dependence. Two stochastic processes can have identical marginal distributions at every time while one forgets everything at the next step and the other repeats its first value forever. Their finite-dimensional distributions and covariance functions distinguish them. That extra structure is what makes a stochastic process useful for prediction.

For a random walk with independent and identically distributed random variables as increments, let $M_n=e^{\lambda S_n}/\varphi (\lambda {)}^n$ define its finite-time exponential tilting. Under the tilted law, $L_n=M_n^{-1}$ is a martingale: the conditional mean of $\varphi (\lambda )e^{-\lambda X_{n+1}}$ is one. For a stopping time $T$, partition $\{T\le n\}$ into $\{T=j\}$ and apply the tower property of conditional expectation to obtain the displayed identity. Only finite-time absolute continuity of measures is needed; there need not be an infinite-horizon likelihood-ratio density.

The operator that averages a function over the next-state conditional law of a time-homogeneous Markov process. For a random walk with increments of law $\nu$ independent of the past including the initial state, $(Ph)(s)=\int h(s+y)\nu (dy)$. This additive operator preserves convexity when the integrals exist.

An autoregressive polynomial with a root at one gives a unit-root model. The basic example $X_t=X_{t-1}+{\epsilon }_t$ is a random walk, whose variance grows with time when the increments have positive variance. Differencing removes this root and recovers its white noise increments.

An upward skip-free random walk has integer-valued increments bounded above by one. Arbitrarily large downward jumps are permitted, but a first crossing of a nonnegative integer level $k$ from below must land exactly at $k$. This removes the overshoot from the stopped likelihood ratio under exponential tilting and permits the exact geometric maximum of an upward skip-free random walk. For a real threshold $k$, the first crossing is the crossing of $\lceil k\rceil$, so the overshoot-free formula must use that integer level.

If a wave packet experiences a fractional nonlinear change $\chi ={\tau }_w/{\tau }_{\mathrm{nl}}\ll 1$ per interaction, and successive interaction phases are decorrelated, $N$ changes add as a random walk of size $\sqrt{N}\chi$. Order-one transfer needs $N\sim {\chi }^{-2}$ interactions, giving the displayed cascade time. Phase coherence or resonant constraints can alter this estimate; weakness alone does not justify random addition.