Let . Suppose particles independently start simultaneously from the origin and perform one-dimensional simple random walks. We say the particles meet whenever all particles occupy the same position. Find the probability that these particles meet infinitely often.

When or the probability is ; when the probability is .

Probability Theory Solution – Problem 33: Find the probability that these particles meet infinitely often

Question

Let $k \geq 2$ . Suppose $k$ particles independently start simultaneously from the origin and perform one-dimensional simple random walks. We say the $k$ particles meet whenever all particles occupy the same position. Find the probability that these $k$ particles meet infinitely often.

Step-by-step solution

Denote the position of the $i$ -th particle by $X_n^{(i)}$ , $n=0,1,2,\dots$ . Consider the relative coordinates: $Y_n^{(j)} = X_n^{(j)} - X_n^{(1)}, \quad j=2,\dots,k$ Then the meeting event is: $Y_n^{(2)} = Y_n^{(3)} = \dots = Y_n^{(k)} = 0$ i.e., the vector $\mathbf{Y}_n = (Y_n^{(2)},\dots,Y_n^{(k)})$ equals the zero vector.

Initial condition: $\mathbf{Y}_0 = \mathbf{0}$ . $X^{(1)}$ and $X^{(j)}$ are independent, and the increments $\Delta X^{(1)}_n, \Delta X^{(j)}_n$ are i.i.d., each taking values $\pm 1$ . Thus $\Delta Y^{(j)}_n = \Delta X^{(j)}_n - \Delta X^{(1)}_n$ with possible values: - $2$ (probability $1/4$ ); $-2$ (probability $1/4$ ); $0$ (probability $1/2$ ) Hence $Y^{(j)}$ is a zero-mean, finite-variance random walk (the increment equals $0$ with probability $1/2$ , but it remains a Markov chain). Compute the covariance (for $j \ne m$ ): $\mathrm{Cov}(\Delta Y^{(j)}, \Delta Y^{(m)}) = E[(\Delta X^{(j)} - \Delta X^{(1)})(\Delta X^{(m)} - \Delta X^{(1)})]$ Since $\Delta X^{(j)},\Delta X^{(m)},\Delta X^{(1)}$ are pairwise independent with mean $0$ and variance $1$ : $= 0 - 0 - 0 + 1 = 1$ Covariance matrix: $\Sigma = \begin{pmatrix} 2 & 1 & \dots & 1 \\ 1 & 2 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & 2 \end{pmatrix}$ Therefore $\Sigma$ is positive definite, and $\mathbf{Y}_n$ can be regarded as a nondegenerate $d=k-1$ dimensional random walk (which, after a linear transformation, becomes a standard random walk). By Pólya's theorem, a $d$ -dimensional simple random walk (nondegenerate, zero-mean, finite variance) is recurrent if and only if $d \le 2$ . Here $\mathbf{Y}_n$ is a nondegenerate $d=k-1$ dimensional random walk, so: - When $k-1 \le 2$ , i.e., $k \le 3$ : recurrent $\Rightarrow$ starting from the origin, the walk returns to the origin infinitely often with probability $1$ $\Rightarrow$ the probability of meeting infinitely often is $1$ . - When $k-1 \ge 3$ , i.e., $k \ge 4$ : transient $\Rightarrow$ the walk returns to the origin only finitely many times $\Rightarrow$ the probability of meeting infinitely often is $0$ . $P(\text{meeting infinitely often}) = \begin{cases} 1, & k = 2, 3, \\ 0, & k \ge 4. \end{cases}$ In conclusion, when $k=2$ or $k=3$ the probability is $1$ , and when $k \ge 4$ the probability is $0$ .

Final answer

When $k=2$ or $k=3$ the probability is $1$ ; when $k \ge 4$ the probability is $0$ .

Marking scheme

The following is a complete marking rubric based on the official solution and undergraduate mathematics grading standards.

Grading Instructions

Total: 7 points.
The student's approach may differ from the official solution (e.g., using asymptotic estimation). Grade according to [Path A] or [Path B] below.
Mutual exclusion rule: Choose the path that best matches the student's main line of reasoning and take the higher score of the two paths. Do not combine scores across paths.

I. Step-by-Step Grading Criteria (Checkpoints)

Path A: Relative Coordinates and Random Walk Dimension Reduction (Official Solution Approach)

Constructing the relative coordinate system and problem reformulation (2 points)
Introduce relative coordinate variables (e.g., $Y_n^{(j)} = X_n^{(j)} - X_n^{(1)}$ or a similar linear transformation) and identify that the meeting of $k$ particles is equivalent to the $(k-1)$ -dimensional vector process $\mathbf{Y}_n$ returning to the origin (or the zero vector).
[Bonus criterion] As long as the student correctly identifies that the essence of the problem is to examine the recurrence of a $d=k-1$ dimensional random walk, this score is awarded.
Verifying nondegeneracy / computing the covariance (2 points)
[2 points] By computing the covariance matrix (e.g., diagonal entries equal to 2, off-diagonal entries equal to 1), proving the matrix is positive definite, or using linear independence arguments to establish that $\mathbf{Y}_n$ is a nondegenerate random walk on $\mathbb{Z}^{k-1}$ (i.e., it can traverse the lattice with positive probability rather than being confined to a lower-dimensional subspace).
[1 point] Merely asserting that $\mathbf{Y}_n$ constitutes a $(k-1)$ -dimensional simple random walk without verifying its nondegeneracy or describing the covariance structure.
Applying Pólya's theorem / dimension criterion (2 points)
Cite the recurrence criterion for $d$ -dimensional simple random walks (zero-mean, finite variance): recurrent if and only if $d \le 2$ (probability 1); transient for $d \ge 3$ (probability 0).
Explicitly state that in this problem the dimension is $d = k-1$ .
Final classification and conclusion (1 point)
Correctly combine the value of $k$ to state the conclusion:
When $k-1 \le 2$ (i.e., $k=2, 3$ ), the probability is 1.
When $k-1 \ge 3$ (i.e., $k \ge 4$ ), the probability is 0.
*Note: If only the answer is given without derivation, this point is not awarded.*

Path B: Asymptotic Probability Estimation (Analytic Approach)

Establishing the meeting probability model (2 points)
Express the probability of meeting at time $n$ , $u_n$ , as the sum of probabilities that all particles occupy the same site: $u_n = \sum_{x} [P(X_n^{(1)}=x)]^k$ or an equivalent integral form.
Deriving the asymptotic order (2 points)
Using the local central limit theorem (Local CLT) or Stirling's formula, correctly derive the asymptotic behavior of $u_n$ :

$u_n \sim C \cdot n^{-(k-1)/2}$

*Note: If an incorrect order is obtained (e.g., $n^{-k/2}$ , missing the summation over the spatial variable $x$ ), this item receives 0 points.*
Connecting series convergence/divergence to recurrence (2 points)
State that the probability of meeting infinitely often depends on the convergence or divergence of the series $\sum u_n$ (via the Borel--Cantelli lemma or Markov chain properties):
$\sum u_n = \infty \implies$ probability is 1 (recurrent).
$\sum u_n < \infty \implies$ probability is 0 (transient / finitely many meetings).
Final classification and conclusion (1 point)
Analyze the series $\sum n^{-(k-1)/2}$ :
For $k=2,3$ , the exponent is $\le 1$ , the series diverges $\to$ probability 1.
For $k \ge 4$ , the exponent is $> 1$ , the series converges $\to$ probability 0.

II. Zero-Credit Items

Modeling error: Incorrectly modeling the meeting of $k$ particles in 1 dimension as a single particle returning to the origin in $k$ -dimensional space.
*Consequence*: This leads to an incorrect dimension ( $d=k$ ), yielding the erroneous conclusion that the probability is 1 for $k=2$ and 0 for $k \ge 3$ . This typically receives 0 points, unless the solution contains some correct general theorem statements (at most 1--2 points).
Guessing the critical value of $k$ by intuition alone, without mathematical derivation or citing a theorem.
Simply restating the given conditions of the problem.

III. Deductions

*In this section, apply the largest single-item deduction; deductions stop at zero (no negative scores).*

Imprecise logic/conclusion (-1 point)
For the transient case ( $k \ge 4$ ), the student concludes "the probability is less than 1" or "the probability is very small" without explicitly stating that the probability is 0 (neglecting the zero-one law for tail events).
Similarly, for the recurrent case, failing to explicitly state that the probability is 1.
Dimension/exponent calculation error (-1 point)
In Path A, an error in computing the rank of the matrix; or in Path B, an error in the integral/summation, leading to an incorrect critical value (e.g., concluding that $k=3$ is also transient).
Missing necessary conditions (-1 point)
When applying the recurrence theorem for random walks, completely failing to mention conditions such as "zero mean" or "step distribution," and directly applying the formula (not enough for zero credit, but insufficiently rigorous).

Total Check

Full marks: 7 points
Path A and Path B scores are not additive.

Probability Theory – Problem 33: Find the probability that these particles meet infinitely often