Random Walks — From a Drunkard's Stagger to PageRank

Introduction — The Drunkard's Return

A drunk stands under a lamppost. At each step, he moves left or right with equal probability. Will he eventually return to where he started?

This problem traces back to a short letter Karl Pearson published in Nature in 1905. Pearson was trying to model a mosquito's displacement after many randomly directed flights. Lord Rayleigh promptly replied with a solution, and this exchange helped popularize the term random walk. In the same year, the same limiting model was central to Einstein's theory of Brownian motion, so closely related ideas about random motion emerged from statistics and physics at the same time.

The answer is yes. In one and two dimensions the walker returns to its starting point with probability 1, but in three or more dimensions there is a positive probability that it never returns. Chapter 1 derives this difference from how quickly the probability of being at the origin decays. Chapter 2 applies the same rule to any graph and shows that the probability of being at each node settles into a stationary distribution. Chapter 3 explains that Google's PageRank is this stationary distribution computed on the web's link structure.

Show transcript

A drunkard under a lamppost steps left or right at random. Will he ever return to where he started? From that simple question, we'll trace a path to Markov chains on graphs, and finally to PageRank.

In one dimension, each step is +1 with probability one half, or -1 with probability one half. The position after n steps, S_n, is the sum of independent step variables X_i. The expectation is zero, variance is n, and standard deviation is square root n. The mean stays put while the spread diffuses.

To be back at the origin after 2n steps, the walk must take the same number of +1 and -1 steps. That probability comes from the central binomial coefficient, and Stirling's approximation makes it about one over square root of pi n. It gets smaller, but the sum of one over square root n diverges. So in 1D, the walker returns infinitely often with probability 1.

But the time of the first return is a different story. The first-return probability decays roughly like one over n to the three halves, and the expected first-return time is infinite. The walker returns almost surely, yet the expected return time is infinite. That is null recurrence.

In 1921, George Pólya showed that recurrence changes with dimension. In one and two dimensions, the walk is recurrent: it returns to the starting point with probability 1. In three dimensions and above, it is transient. In 3D the return probability is about 0.3405, so about 66% never return.

If the number line is a graph, the one-dimensional random walk is a walk on an infinite path graph. On any graph, we can choose the next node uniformly at random from the current node's neighbors. This is a Markov chain: multiplying the probability vector at time t by the transition matrix P gives the vector at time t+1.

A finite connected graph has a unique stationary distribution satisfying pi equals pi P. For an undirected graph, pi_i equals degree of i over twice the number of edges. Higher-degree nodes are visited more often. The reason is detailed balance: the probability flow across each adjacent pair balances in both directions.

When the chain is aperiodic, the full distribution also converges toward the stationary distribution. The speed is set by the second-largest eigenvalue modulus: the larger the spectral gap, one minus that modulus, the faster. Complete graphs mix in a few steps, path graphs need O of n squared steps, and expanders need O of log n.

The same idea leads directly to ranking pages on the web. In 1976, Gabriel Pinski proposed ranking academic journals using the structure of citation networks. In 1998, Larry Page and Sergey Brin viewed the web as a giant directed graph. PageRank is the recursive idea that a page linked from important pages is itself important.

The PageRank random surfer usually follows an outgoing link. But with probability one minus d, the surfer gets bored and teleports to a random page. d is typically 0.85. The surfer always jumps from dangling pages with no outgoing links, and jumps keep it from being trapped in absorbing clusters.

The PageRank vector is the stationary distribution of the damped transition matrix M. Starting from the uniform distribution, power iteration updates the scores again and again. Because M is primitive, Perron-Frobenius guarantees uniqueness and convergence. With d = 0.85, the error bound is multiplied by 0.85 every iteration — after 50 iterations, by about 2.96 × 10^-4.

Random walks also reach Monte Carlo methods, MCMC, clustering, recommendations, and GNNs. In the article, you can explore this whole path with interactive demos for the line, the graph, and PageRank.

---

Chapter 1 — 1D Random Walk

The Simplest Model

Start at the origin on the number line. At each step, move $+1$ with probability $1/2$ and $-1$ with probability $1/2$. If we denote the position after $n$ steps as $S_n$:

$S_n = X_1 + X_2 + \cdots + X_n$

where each $X_i$ independently takes $+1$ or $-1$. We call each $X_i$ a step.

In the limit, this model converges to Brownian motion (the Wiener process). Shrink the step size to $1/\sqrt{n}$ and let the number of steps go to infinity, and you get a continuous stochastic process. In that sense, the 1D random walk is "discrete-time Brownian motion." The Black-Scholes model in financial engineering is built on this continuous version.

Expected Value and Variance

By symmetry, the expected value is zero. Each step has expectation $E[X_i] = (1/2)(+1) + (1/2)(-1) = 0$, so:

$E[S_n] = \sum_{i=1}^{n} E[X_i] = 0$

What about variance? Each step has variance $\mathrm{Var}(X_i) = E[X_i^2] - (E[X_i])^2 = 1 - 0 = 1$. Since the $X_i$ are independent, variances add:

$\mathrm{Var}(S_n) = \sum_{i=1}^{n} \mathrm{Var}(X_i) = n$

The standard deviation is $\sqrt{n}$. The average position stays at 0 no matter how long the walk runs, but the spread grows like $\sqrt{n}$. The standard deviation is 10 after 100 steps and 100 after 10,000 steps: 100 times as many steps only make the spread 10 times wider. This growth in proportion to the square root of the number of steps is called diffusion.

The demo below runs 5 independent random walks simultaneously. Individual paths vary widely, and the variance measured over the 5 walks fluctuates around the theoretical value $n$ as it grows with the number of steps.

Recurrence — Returning to the Origin

A one-dimensional random walk returns to the origin with probability 1.

To show this, first compute the probability of being at the origin after $2n$ steps. For $S_{2n} = 0$ to hold, we need exactly $n$ steps of $+1$ and $n$ steps of $-1$. The number of ways to choose $n$ positions from $2n$ trials is $\binom{2n}{n}$, and each sequence has probability $(1/2)^{2n}$:

$P(S_{2n} = 0) = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n}$

Using Stirling's approximation $n! \approx \sqrt{2\pi n}\,(n/e)^n$:

$\binom{2n}{n} = \frac{(2n)!}{(n!)^2} \approx \frac{4^n}{\sqrt{\pi n}}$

Therefore:

$P(S_{2n} = 0) \approx \frac{4^n}{\sqrt{\pi n}} \cdot \frac{1}{4^n} = \frac{1}{\sqrt{\pi n}}$

This probability decays to 0 as $n$ grows, but slowly. The expected number of returns to the origin is:

$E[\text{returns}] = \sum_{n=1}^{\infty} P(S_{2n} = 0) \approx \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \infty$

The series $\sum 1/\sqrt{n}$ diverges (compare with the integral $\int_1^\infty x^{-1/2}\,dx = \infty$). Because the expected number of returns is infinite, the walker returns to the origin infinitely many times with probability 1. A walk with this property is called recurrent.

The terms $1/\sqrt{n}$ are small, but not small enough for their sum to converge. As we'll see, in 3D the probability of being at the origin decays like $1/n^{3/2}$, the series converges, and return is no longer guaranteed.

First Return Time Distribution

The walker is certain to return, but the expected time until it first returns is infinite.

Let $f_{2n}$ be the probability of first returning to the origin at step $2n$:

$f_{2n} = \frac{1}{2n - 1} P(S_{2n} = 0) \approx \frac{1}{2n - 1} \cdot \frac{1}{\sqrt{\pi n}} \sim \frac{1}{n^{3/2}}$

The expected first return time is:

$E[\text{first return}] = \sum_{n=1}^{\infty} 2n \cdot f_{2n} \sim \sum_{n=1}^{\infty} \frac{1}{\sqrt{n}} = \infty$

The walker returns with probability 1, yet the expected return time is infinite. This property is called null recurrence. On a finite connected graph, the expected return time is finite: using the stationary distribution $\pi_i$ from Chapter 2, the expected time to return to node $i$ is $1/\pi_i$.

Pólya's Theorem — Dimension and Recurrence

Whether the walk is recurrent depends on the dimension.

In the 2D random walk, at each step we move in one of four directions (up, down, left, right) with equal probability. The probability of being at the origin after $2n$ steps is:

$P(S_{2n} = \mathbf{0}) \approx \frac{1}{\pi n}$

The expected number of returns is $\sum 1/(\pi n)$, which diverges like the harmonic series. So 2D is also recurrent.

What about 3D? At each step we move in one of six directions with equal probability. The probability of being at the origin after $2n$ steps is:

$P(S_{2n} = \mathbf{0}) \approx 2\left(\frac{3}{4\pi n}\right)^{3/2}$

The expected number of returns is proportional to $\sum n^{-3/2}$, which converges. Because the expected number of returns is finite, there is a positive probability of never returning. George Pólya proved the results for all dimensions in 1921:

• 1 dimension: Recurrent (returns with probability 1)
• 2 dimensions: Recurrent (returns with probability 1)
• 3 dimensions and above: Transient (positive probability of never returning)

The return probability in 3D can be computed from Watson's triple integral and is approximately 0.3405, so a 3D random walker has about a 66% chance of never returning to the origin. In higher dimensions, the walker's position after $n$ steps spreads over more sites, and the probability of being at the origin decays faster, like $n^{-d/2}$ in $d$ dimensions.

Shizuo Kakutani expressed Pólya's result thus: "A drunk man will find his way home, but a drunk bird may get lost forever."

The same difference appears in diffusion on a lattice. On a 2D lattice, a single particle visits every site with probability 1; in 3D, unvisited sites remain.

---

Chapter 2 — Random Walks on Graphs

From Lines to Graphs

If we view the number line as a graph, with each integer as a node and edges between adjacent integers, it is an infinite path graph. The 1D random walk is a random walk on this path graph.

The operation "be at a node, move to a neighbor" can be defined on any graph: a social network, a transit map, the bonds in a molecule. So we now consider the same walk on an arbitrary graph.

Transition Rule

From the current node, choose the next node uniformly at random from among the neighbors. When at node $i$, the probability of moving to node $j$ is:

$P(i \to j) = \frac{1}{\deg(i)} \quad \text{(when $j$ is adjacent to $i$)}$

At high-degree nodes, the transition probability to each neighbor is small; at low-degree nodes, it's large. A drunk at a busy intersection is less likely to take any particular road.

Formulation as a Markov Chain

This process is a Markov chain: the next state depends only on the current state, not on history (the Markov property, or "memorylessness").

Define the transition matrix $P$ as the $|V| \times |V|$ matrix with entries:

$P_{ij} = \begin{cases} 1/\deg(i) & \text{if $i$ and $j$ are adjacent} \\ 0 & \text{otherwise} \end{cases}$

The probability vector $\mathbf{p}^{(t)}$ (a row vector of the probabilities of being at each node at time $t$) evolves as:

$\mathbf{p}^{(t+1)} = \mathbf{p}^{(t)} P$

The distribution after $t$ steps is simply the initial distribution multiplied by $P^t$.

Stationary Distribution

For a finite connected graph, the random walk has a unique stationary distribution $\pi$. It is a probability distribution (nonnegative entries summing to 1) satisfying $\pi = \pi P$, which makes it the left eigenvector of the transition matrix for eigenvalue 1. For the distribution at each time step to converge to $\pi$ from any starting distribution, the chain must also be aperiodic. A simple undirected graph without self-loops is aperiodic if it is not bipartite. A connected bipartite graph still has a stationary distribution, and long-run visit frequencies converge, but the distribution at each step oscillates between even and odd steps.

For finite connected undirected graphs, the stationary distribution has a closed form:

$\pi_i = \frac{\deg(i)}{2|E|}$

where $|E|$ is the number of edges. The denominator $2|E|$ equals the sum of all degrees (each edge contributes 1 to the degree of each endpoint — the handshaking lemma).

Nodes with higher degree (more edges) are visited more often, because walkers arrive at a node with many entrances from many directions.

For example, in a graph with 5 edges where node $A$ has degree 3, we get $\pi_A = 3/10 = 0.3$. In the long run, the walker spends 30% of its time at node $A$.

In the demo below, a random walker moves around a 6-node graph, and its visit frequencies converge to the theoretical stationary distribution $\pi_i = \deg(i) / 2|E|$.

Why a Stationary Distribution Exists — Detailed Balance

The detailed balance condition gives a short proof that $\pi$ satisfies $\pi = \pi P$:

$\pi_i P_{ij} = \pi_j P_{ji}$

This condition means "the probability flow from $i$ to $j$ equals the flow from $j$ to $i$." If inflow and outflow balance for every pair, no node's probability changes.

Substituting $\pi_i = \deg(i) / 2|E|$ and $P_{ij} = 1 / \deg(i)$, for any adjacent pair $(i, j)$:

$\frac{\deg(i)}{2|E|} \cdot \frac{1}{\deg(i)} = \frac{1}{2|E|} = \frac{\deg(j)}{2|E|} \cdot \frac{1}{\deg(j)}$

Both sides are equal, so detailed balance holds. A distribution satisfying detailed balance is necessarily stationary (summing $\pi_i P_{ij}$ over $i$ for each $j$ recovers $\pi_j$), completing the proof.

A Markov chain satisfying detailed balance is called reversible. Random walks on finite undirected graphs are reversible with respect to this stationary distribution (within each connected component), but Markov chains on general directed graphs need not be. The web that PageRank works on in Chapter 3 is a directed graph, so there is generally no closed form like $\pi_i = \deg(i)/2|E|$ that depends only on degrees, and the stationary distribution has to be computed iteratively.

Convergence Speed — Mixing Time

An aperiodic chain converges to the stationary distribution, but the speed of convergence also matters. For reversible chains, the rate is governed by the second-largest eigenvalue modulus $\lambda_* = \max_{i \ge 2} |\lambda_i|$ of the transition matrix:

$\|\mathbf{p}^{(t)} - \pi\|_{\text{TV}} \leq C \cdot \lambda_*^t$

The closer $\lambda_*$ is to 1, the slower the convergence; the closer to 0, the faster. The gap $1 - \lambda_*$ is the relevant spectral gap for mixing (for lazy or nonnegative-spectrum chains this coincides with $1 - \lambda_2$).

The mixing time $t_{\text{mix}}$ is the number of steps needed for the distribution to get "close enough" to stationarity. Up to logarithmic factors that depend on the target accuracy and the smallest stationary probability, it is on the order of $1/(1 - \lambda_*)$. For lazy random walks, which stay put with probability 1/2 at each step to avoid periodicity, the shape of the graph makes a large difference:

• Complete graph ($K_n$): Large spectral gap, mixes in just a few steps
• Path graph (a line): Small spectral gap, needs $O(n^2)$ steps
• Expander graphs: Constant spectral gap, mixes in $O(\log n)$ steps

Mixing time also determines how fast MCMC converges, which Chapter 4 covers.

Hitting Time and Cover Time

Two more measures describe how quickly a random walk explores a graph:

• Hitting time $h(u, v)$: Expected number of steps from node $u$ to first reach node $v$
• Cover time $C(G)$: Expected number of steps from some node to visit every node at least once

The cover time of any connected $n$-node graph is known to be $O(n^3)$. This is a worst-case upper bound, and many graphs are covered much faster. The cover time of the complete graph is $\Theta(n \log n)$, which has the same structure as the coupon collector problem (expected number of draws to collect all $n$ types of coupons).

---

Chapter 3 — The Invention of PageRank

From Citation Networks

Before the web, there was already research on evaluating academic journals from citation relationships. The Impact Factor is a simple metric based on citation counts, and it doesn't distinguish between "a citation from a high-quality paper" and "a citation from a low-quality one."

In 1976, Gabriel Pinski and Francis Narin proposed a method for ranking academic journals using the structure of the citation network. Their method weights each citation by the influence of the citing journal, and its definition closely resembles PageRank's, making it a precursor.

The Web as a Giant Directed Graph

Larry Page and Sergey Brin, then graduate students at Stanford, focused on the link structure of the web and published PageRank in 1998. Search engines of the time, such as AltaVista and Lycos, ranked results by keyword frequency, which made them vulnerable to spam and hurt result quality.

Each page is a node; each hyperlink is a directed edge. Their question was:

"Can we compute a page's 'importance' purely from link structure?"

They defined importance recursively: "A page linked from important pages is itself important." The definition uses importance to define importance, so it looks circular, but it can be formulated as an eigenvector problem.

The Random Surfer Model

This importance can be expressed as a random walk on the graph. An imaginary "random surfer" browses the web as follows:

1. From the current page, click one of the outgoing links uniformly at random
2. With probability $1 - d$, get bored and jump to a random page instead

The damping factor $d$ is typically set to $0.85$, so the surfer follows a link with probability 85% and jumps to a random page with probability 15%.

The jump solves two technical problems:

1. Dangling nodes: Pages with no outgoing links (PDFs, images) would halt the walk. In practice their transition row is first replaced by the teleportation distribution
2. Absorbing states: Small clusters of mutually linking pages could trap the walker. With positive-probability teleportation, every entry of the final transition matrix is positive. The matrix is therefore primitive, and every node can be reached from every node

In matrix notation, after patching dangling rows so $P$ is row-stochastic, the jump-augmented matrix $M$ is:

$M = d \cdot P + (1 - d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N}$

where $P$ is the link-based transition matrix and $\mathbf{1}\mathbf{1}^T/N$ is a matrix of uniform transition to all nodes (the teleportation matrix).

Power Iteration

The PageRank vector $\mathbf{r}$ is the stationary distribution $\pi M = \pi$, computed by power iteration:

$r_j^{(t+1)} = \frac{1-d}{N} + d \sum_{i \to j,\,\text{out}(i)>0} \frac{r_i^{(t)}}{\text{out}(i)} + \frac{d}{N}\sum_{i:\,\text{out}(i)=0} r_i^{(t)}$

Start from the uniform distribution $r_i^{(0)} = 1/N$ and apply this formula repeatedly. Since $M$ is primitive, the Perron-Frobenius theorem guarantees that the eigenvector for eigenvalue 1 is unique. Haveliwala and Kamvar (2003) also showed that all other eigenvalues have absolute value at most $d$, so the error shrinks geometrically, in proportion to $d^t$:

$\|\mathbf{r}^{(t)} - \pi\| \leq C \cdot d^t$

With $d = 0.85$, 50 iterations shrink the damping-only factor to $0.85^{50} \approx 2.96 \times 10^{-4}$; the actual stopping point depends on the chosen tolerance and graph. Even for the web of tens of millions of pages covered in the 1998 paper, this simple iteration computed rankings at practical speed.

The demo below runs PageRank power iteration on a small 6-page web graph. With each iteration, the scores settle toward fixed values.

Mathematical Meaning of PageRank

PageRank is the stationary distribution of a damped random walk.

• With $d = 1$ (no jumps), it's a pure random walk on a directed graph. Dangling nodes and disconnected components make the stationary distribution non-unique
• The jump with $d < 1$ makes every entry of the transition matrix positive. By Perron-Frobenius, the left eigenvector for eigenvalue 1 is unique, and the iteration converges to it from any starting distribution

The property from Chapter 2, that a random walk's visit frequencies converge to the stationary distribution, is what guarantees that the PageRank computation converges to a unique answer.

Limitations and Legacy

PageRank was at the core of Google's early ranking, but modern web search combines link structure with hundreds of other signals (text relevance, user behavior, page quality metrics, etc.). PageRank is also vulnerable to link farms (artificially generating mutual links to inflate scores).

Still, PageRank's idea of using a random walk's stationary distribution to compute importance within a network is used today in social network analysis, gene network analysis in bioinformatics, and systemic risk assessment of financial networks.

---

Chapter 4 — The Reach of Random Walks

Monte Carlo Methods

Monte Carlo methods use randomness for numerical computation. The name comes from the casino city of Monte Carlo. Von Neumann and Stanislaw Ulam pioneered the approach in the 1940s Manhattan Project for simulating neutron diffusion.

The best-known example is estimating $\pi$. Throw random points into the unit square $[0,1]^2$, and let $p$ be the fraction that lie within distance 1 of the origin; then $\pi \approx 4p$. With $N$ points, the estimation error is $O(1/\sqrt{N})$, and this rate does not depend on the dimension. Traditional numerical integration methods such as Simpson's rule lose accuracy rapidly as the dimension grows (the "curse of dimensionality"), so Monte Carlo has the advantage for high-dimensional integrals.

MCMC (Markov Chain Monte Carlo)

The Monte Carlo methods so far assume we can sample from a uniform distribution. Real problems often require sampling from complex distributions, such as posterior distributions or Boltzmann distributions in statistical physics.

MCMC constructs a Markov chain whose stationary distribution is the target distribution, and generates samples with a random walk. The theory from Chapter 2 applies directly.

• Metropolis-Hastings (1953/1970): Generate a candidate $x'$ from proposal distribution $q(x'|x)$, accept with probability $\alpha = \min(1, \frac{\pi(x') q(x|x')}{\pi(x) q(x'|x)})$, otherwise stay put. With this acceptance probability, detailed balance holds and $\pi$ is the stationary distribution. Because the normalization constant of $\pi$ need not be known, the method is widely used in Bayesian statistics for sampling from posterior distributions

• Gibbs Sampling (1984): Sequentially sample each variable from its conditional distribution given the others. A special case of Metropolis-Hastings. Standard in image processing (Markov random fields) and latent variable models (LDA topic models)

MCMC is more efficient when its mixing time (the number of steps needed to get practically close to the stationary distribution) is small. The mixing time is determined by the spectral gap from Chapter 2, so random walk theory can be used directly to analyze efficiency.

Graph Clustering

A random walker tends to stay within the same community for a long time and rarely crosses the bridge edges between communities. This property can be used to detect a graph's community structure.

• Markov Clustering (MCL): Alternates between expansion (computing $P^2$) and inflation (raising each element to the power $r$ and re-normalizing columns). Expansion corresponds to two-step random walks, creating inter-cluster flow. Inflation amplifies strong flows and eliminates weak ones. Repeating this makes the cluster structure appear. It is widely used to analyze protein interaction networks

• Personalized PageRank: Standard PageRank jumps uniformly to all nodes, but Personalized PageRank fixes the teleportation destination to a specific node $v$ and returns to $v$ with probability $1-d$. The result assigns each node a "closeness" score as seen from $v$. Twitter's Who to Follow service used a random walk similar to Personalized PageRank to find each user's "circle of trust," the users closest to them, and built its recommendations on it (Gupta et al., WWW 2013)

Recommendation Systems

On a bipartite graph of users and items (connected by purchases, views, or clicks), start a random walk from a given user. Item nodes frequently visited by the walker become recommendations.

This approach has two advantages:

1. Balance between exploration and exploitation: Candidates include items close to those already purchased (= exploitation) and also items farther away in the graph (= exploration). This produces an effect similar to collaborative filtering
2. Cold start handling: Even new items can be recommended if they're indirectly connected to other items in the graph

Pixie (Pinterest's recommendation engine) runs biased random walks on a graph of billions of nodes and returns personalized recommendations in real time.

Connection to Graph Neural Networks

Graph Neural Networks (GNNs) and related graph representation learning methods also use the random walk idea:

• DeepWalk (2014): Performs random walks on graphs, treats the node visit sequences as "sentences," and trains them with Word2Vec's SkipGram. Co-occurrence in random walk sequences captures node similarity
• Node2Vec (2016): Extends DeepWalk by introducing bias parameters $p, q$ that set the weight between BFS-like exploration (capturing local structure) and DFS-like exploration (capturing community structure)
• GCN (Graph Convolutional Network): Spectral graph convolutions can be approximated by polynomial filters such as Chebyshev polynomials. The common first-order GCN layer uses a symmetrically normalized adjacency matrix with self-loops. It is not the random walk transition matrix itself, but it can be read as random-walk-like diffusion of neighborhood information

---

Summary — From the Number Line to PageRank

1. 1D random walk: Expected value 0 and variance $n$, so the spread grows in proportion to $\sqrt{n}$. Recurrent in 1D and 2D (returns with probability 1), transient in 3D and above (Pólya's theorem). In 1D the walker always returns, yet the expected return time is infinite (null recurrence)
2. Random walks on graphs: Formulated as Markov chains. On a finite connected undirected graph, the stationary distribution is $\pi_i = \deg(i) / 2|E|$, which follows from detailed balance. The speed of convergence (mixing time) is governed by the spectral gap
3. PageRank: Computes the importance of web pages as the stationary distribution of a damped random walk. It can be computed by power iteration, and the Perron-Frobenius theorem guarantees convergence to a unique answer
4. Applications: Monte Carlo methods, MCMC, graph clustering, recommendation systems, GNNs

Recurrence and diffusion, seen on the number line, become questions about stationary distributions and convergence speed on graphs. PageRank and MCMC use these two properties directly in their computations.