Codex @codex  0

Put $Z_i=Y_{i-1}{Y}_i$ for $1\le i\le n$. Independence of the underlying exponentials gives $\mathbb{E}{Z}_i=1$ andBy the covariance of overlapping independent products, adjacent terms have covariance one. Terms separated by at least two indices use disjoint independent factors, so their covariance is zero. There are $n-1$ adjacent pairs. Linearity of expectation and the variance of a sum formula therefore yieldIn particular, the products themselves are not independent merely because the original $Y_i$ are.

Let $I_c$ be the indicator random variable that colour $c$ appears at least once. Then $X=I_R+I_B+I_G$. For a colour of single-roll probability $p_c$, independence of rolls gives $\mathbb{P}(I_c=0)=(1-p_c{)}^n$. By linearity of expectation,The three indicators are not independent, but linearity of expectation does not require them to be. This is the expected number of observed categories.

Let $I_B$ be the indicator that black bead $B$ belongs to the white bead's connected component. The number of such black beads is ${\sum }_B{I}_B$. By linearity of expectation, no independence between these indicators is needed.

For $n=7$, the six oriented distances $1,\dots ,6$ give respective probabilitiesTheir sum is $2$, the expected number of black beads in the white component. As a check, summing the formula from (i) and using ${\sum }_{k=1}^{n-1}\left(\genfrac{}{}{0ex}{}{k}{3}\right)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ gives the general value $2\left(\genfrac{}{}{0ex}{}{n}{4}\right)/\left(\genfrac{}{}{0ex}{}{n}{3}\right)=(n-3)/2$, again equal to $2$ when $n=7$.

By linearity of expectation, $\mathbb{E}[Z]={\sum }_i\mathbb{E}[X_i]=0$. Expanding the square and again using linearity of expectation givesHere the zero means imply $\mathbb{E}[X_i^2]={\sigma }_i^2$ and $\mathbb{E}[X_i{X}_j]=\mathrm{Cov}(X_i,X_j)$. The covariance expansion itself does not require independence. Under the additional independence stated here, $\mathbb{E}[X_i{X}_j]=\mathbb{E}[X_i]\mathbb{E}[X_j]=0$, so it simplifies further to $\mathrm{Var}(Z)={\sum }_i{\sigma }_i^2$.

The finite-partition form of the law of total expectation statesBecause the events form a partition of a sample space of the sample space, ${\sum }_j{1}_{B_j}=1$ pointwise. Multiply by $X$ and use linearity of expectation to obtainAn event of zero probability contributes zero to the middle expression and is omitted from the final expression, so no undefined conditional expectation is multiplied by zero.

Write $h_i={\mathbb{E}}_i[J]=i/k$ and $v_i={\mathbb{E}}_i[JX]$. Since $0\le JX\le X$, the latter expected value is finite. Conditional on the first move to $i-1$ or $i+1$, total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation giveAt either absorbing boundary the remaining time is zero, so $v_0=v_k=0$.

Let $w_i=i(k^2-i^2)/(3k)$. The linear term has zero second difference and $i^3$ has second difference $6i$. Consequentlywhich is exactly the required recurrence, and $w_0=w_k=0$. Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. HenceThis is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.

Assume finite second moments and set $Y_i=X_i-\mathbb{E}{X}_i$. By linearity of expectation, centring $X_1+X_2$ gives $Y_1+Y_2$. Expanding its square and using the definitions of variance and covariance,No independence assumption is required for this variance of a sum identity.

By linearity of expectation, $\mathbb{E}{N}_n=n{p}_n$. The variance of a sum and the negative covariance just proved giveApply Chebyshev's inequality to the empty-box indicators in uniform allocation:This proves the required concentration of the empty-box fraction. Since $p_n\to e^{-1}$, it also yields convergence in probability of $N_n/n$ to $e^{-1}$.

First $0\le M_n\le {\sum }_i{E}_i$, so linearity of expectation gives $\mathbb{E}{M}_n\le n<\infty$. The tail integral formula for expectation, followed by the finite binomial theorem expansion, givesThe exchange involves only a finite sum. As a useful check, substitution $t=e^{-x}$ rewrites the integral as ${\int }_0^1[1-(1-t{)}^n]/tdt={\sum }_{j=0}^{n-1}{\int }_0^1(1-t{)}^{j}dt={\sum }_{k=1}^{n}1/k$, the harmonic number $H_n$.

Apply the law of total expectation to the bounded random variable $R_{k+1}$. Linearity of expectation givesThis also holds for the first step from $r_0=n$.

The sum of independent Bernoulli random variables with possibly unequal success probabilities $p_i$ has a Poisson binomial distribution. Its probability generating function is $G_K(z)={\prod }_i(1-p_i+p_{i}z)$: expand the product to read off the probability mass function. Linearity of expectation and additivity of variance for independent random variables give $\mathbb{E}K={\sum }_i{p}_i$ and $\mathrm{Var}(K)={\sum }_i{p}_i(1-p_i)$. Equal $p_i=p$ recover the binomial distribution.

For three trials with success probabilities $1/10,3/10,4/5$, expanding $(9/10+z/10)(7/10+3z/10)(1/5+4z/5)$ gives masses $0.126,0.572,0.278,0.024$ at $0,1,2,3$. Their expected value is $1.2$ and variance is $0.46$. Replacing all three success probabilities by their average $0.4$ preserves the expected value but gives binomial distribution variance $0.72$, so it does not preserve the law.

In a uniform balls-in-bins allocation with $m\to \infty$ and $n/m\to \lambda \in (0,\infty )$, a fixed bin count has convergence in distribution to a Poisson distribution variable of mean $\lambda$ by the Poisson limit theorem. If $N_j$ counts bins containing exactly $j$ balls, symmetry and the linearity of expectation give $\mathbb{E}[N_j]/m=\mathbb{P}(B_1=j)\to e^{-\lambda }{\lambda }^j/j!$ for each fixed $j$. In particular the expected empty fraction tends to $e^{-\lambda }$, and the expected fraction with at least two balls tends to $1-(1+\lambda )e^{-\lambda }$. These are statements about expectations; convergence of the random fractions requires an additional argument.

Every finite graph with $m$ edges has a cut of a graph of size at least $m/2$, and hence a spanning bipartite graph with at least $m/2$ edges. Put each vertex independently on either side with equal probability. Every edge crosses with probability $1/2$, so linearity of expectation gives expected cut size $m/2$.

A real-valued random variable is a measurable function $X$ from a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ to the real numbers with their Borel sigma-algebra. More general targets give random elements. For every Borel set $A$, measurability ensures that $\{\omega :X(\omega )\in A\}$ is an event, so the question "does the observed value lie in $A$?" has a defined probability.

The function $X$ is fixed; its input outcome is uncertain. This separates what we measure from how the uncertainty is modeled. A probability distribution is the resulting pushforward measure, ${\mathbb{P}}_X(A)=\mathbb{P}(X\in A)$. A cumulative distribution function, probability mass function, or probability density function describes that measure in an appropriate setting. The random variable and its probability distribution are different objects: the former also retains its relationship to other measurements on the same sample space.

For two independent uniform dice, let $U,V$ record their results and define $S=U+V$ and $M=\max (U,V)$. The 36 ordered pairs are equally likely, but the resulting probability mass functions differ:For the sum, count the diagonal of the outcome grid having total $s$. For the maximum, subtract the $(m-1{)}^2$ pairs with both results below $m$ from the $m^2$ pairs with both results at most $m$. These examples show how a deterministic function transforms a simple input probability distribution into a nonuniform output one.

The corresponding expected values are $\mathbb{E}S=7$ and $\mathbb{E}M=161/36$. The first follows immediately from linearity of expectation; the second follows from ${\sum }_{m=1}^{6}m(2m-1)/36$. Neither number must be an attainable result. An expected value describes an average under the probability measure, not a prediction that the next observation will equal it.

The distinction between a random variable and its probability distribution matters for dependence. $U$ and $V$ have the same discrete uniform distribution and are independent random variables. $U$ and a second copy of $U$ also have that same marginal probability distribution, but they always agree. Their joint probability distribution is concentrated on the diagonal; the marginals alone cannot say which relationship holds. This is why a model for several measurements must specify their joint law or an appropriate independence assumption.

Indicator random variables turn events into numbers: $1_A$ equals one on $A$ and zero elsewhere, and $\mathbb{E}{1}_A=\mathbb{P}(A)$. This connects event counting with expected value and variance, and lets tools for random variables answer questions about probabilities. More complicated functions of observations can describe totals, waiting times, or estimation errors using the same framework.

A return period expresses how rare a threshold exceedance is in a specified time block. Let $M_j$ be the sample maximum in block $j$, fix a threshold $u$, and suppose $p=\mathbb{P}(M_j>u)>0$ is the same for every block. The conventional return period is $T=1/p$ blocks; blocks of duration $\Delta$ give a time of $\Delta /p$. Thus an annual exceedance probability $p=0.01$ means a 100-year return period. This names a frequency scale, not a schedule or a guarantee of one exceedance in each century. The annual convention and the misleading “once every 100 years” interpretation are discussed in USGS: the 100-year flood.

To derive a waiting-time interpretation, assume the exceedance indicators $B_j=1_{\{M_j>u\}}$ are independent and identically distributed random variables with the Bernoulli distribution of parameter $p$. Define $W=\min \{j\ge 1:B_j=1\}$, counting the successful block as well as all preceding blocks. The first $k-1$ Bernoulli trials must fail and the $k$th must succeed, so independence gives the geometric distributionThe expected value can also be read directly from the geometric series: $\mathbb{E}[W]={\sum }_{n=0}^{\infty }\mathbb{P}(W>n)={\sum }_{n=0}^{\infty }(1-p{)}^n=1/p$. This counts blocks from the starting boundary, not the exact time of an exceedance within its block. Counting only failed blocks instead would give expected value $T-1$. The waiting law and its memorylessness of the geometric distribution are developed in Kyle Siegrist, Random Services: the geometric distribution.

For a horizon of $n$ complete years, at least one exceedance is the complement of no exceedances. Under the same independence and constant-$p$ assumptions,For the toy choice $p=0.01$, this gives $9.6\%$ in 10 years, $26.0\%$ in 30 years, $39.5\%$ in 50 years, and $63.4\%$ in 100 years. Even after 100 years there is a $36.6\%$ chance of no exceedance. These numbers are exact model calculations rounded to one decimal place, not measured frequencies. The median waiting count is 69 years, since $1-0.99^{68}<1/2\le 1-0.99^{69}$; the expected value is 100 years. A mean and a median answer different questions.

The exceedance count $N_n={\sum }_{j=1}^n{B}_j$ has the binomial distribution under independence, with expected value $np$. Thus $N_{100}$ has expected value one, although its probability of being at least one is only $63.4\%$: some realizations contribute several exceedances. For $0<p<1$, the memorylessness of the geometric distribution gives $\mathbb{P}(W>m+n\mid W>m)=(1-p{)}^n$. A long quiet spell does not make the next independent year's exceedance overdue, and an exceedance this year does not force a quiet interval. Two specified consecutive years both exceed with probability $p^2=0.0001$ in this toy model.

A reproducible tabletop experiment makes the assumptions tangible. Put 100 identical slips numbered 1 to 100 in a bag; after thoroughly mixing, draw one and record whether it is 100. Replace the slip and mix again before every draw. Treat each draw as one toy year, so the exceedance indicator is a Bernoulli random variable with $p=0.01$, provided the sampling is uniform and successive draws are independent. Repeat complete 30-draw runs and record the fraction containing at least one 100; separately repeat runs stopped at the first 100 and record their waiting counts. The first fraction targets $1-0.99^{30}$; the waiting-count histogram targets $0.99^{k-1}(0.01)$. Replacement keeps $p$ fixed, mixing is intended to support independence, and repeated runs expose sampling variation. This is a proposed demonstration of the toy model; no experimental results are asserted here.

Stationarity supports a time-invariant annual probability distribution, but does not imply independence. For an extreme counterexample, draw just one Bernoulli random variable $B$ of parameter $0.01$ and set $B_j=B$ for every year. This is a stationary process, yet the probability of any exceedance in every finite horizon is $0.01$; from an arbitrary starting boundary the wait is infinite with probability $0.99$. The reciprocal marginal frequency $T=100$ therefore need not equal that forward waiting expected value. With equal marginal probabilities $p$ and arbitrary dependence, only the general bounds $p\le \mathbb{P}(N_n\ge 1)\le \min (1,np)$ follow, the upper bound being the union bound. Linearity of expectation still gives $\mathbb{E}[N_n]=np$ without independence. Mere zero correlation does not restore the product formula; even pairwise independence does not imply joint independence. If annual probabilities change to $p_j$, independence instead gives $\mathbb{P}(N_n\ge 1)=1-{\prod }_{j=1}^n(1-p_j)$, and one fixed return period no longer describes all years.

Fix $N>1$ real population values $y_1,\dots ,y_N$. Define the finite population mean and two normalizations of the finite population variance byThe values are fixed; only the selected subset $A$ is random. For its sample mean ${\bar{y}}_A=n^{-1}{\sum }_{i\in A}{y}_i$, the exact design expectation and variance areThe sample mean is an unbiased estimator of the finite population mean. At $n=N$, every unit is observed and ${\bar{y}}_A=\bar{Y}$ exactly, so the variance is zero. The $N=1$ case is deterministic and is handled directly, since $S^2$ is undefined then.^[ref]

The finite population correction depends on the baseline. With the $N-1$ normalization it is $1-n/N$ multiplying $S^2/n$. With the $N$ normalization it is $(N-n)/(N-1)$ multiplying ${\sigma }_N^2/n$, the exact variance for independent uniform sampling with replacement. The standard error uses the square root of the relevant variance factor. Mixing the two normalizations gives a wrong answer even at $n=1$, when replacement cannot matter. For the six-value example, $\bar{Y}=7$, ${\sum }_i(y_i-7{)}^2=70$, $S^2=14$ and ${\sigma }_N^2=35/3$, reproducing $14/3$ without replacement and $35/6$ with replacement.

A short proof exposes the statistical dependence. Let $X_r$ be the value at position $r$ in uniform sequential sampling without replacement, so each $X_r$ has expected value $\bar{Y}$ and variance ${\sigma }_N^2$. Write $d_i=y_i-\bar{Y}$. Every ordered pair of distinct labels is equally likely, and ${\sum }_i{d}_i=0$, hence for $r\ne s$,Linearity of expectation proves unbiasedness without requiring independence. The variance of a sum includes all $n(n-1)$ ordered covariance terms, givingFor the original population, each pair of distinct draw positions has covariance $-7/3$. Drawing a high value leaves a lower mean among the remaining values, balancing subsequent draws. Equal marginal probability distributions therefore coexist with negative covariance.

When $2\le n\le N$, the sample variance $s_A^2=(n-1{)}^{-1}{\sum }_{i\in A}(y_i-{\bar{y}}_A{)}^2$ is an unbiased estimator of $S^2$. To check this independently, use ${\sum }_{i\in A}(y_i-{\bar{y}}_A{)}^2={\sum }_{i\in A}(y_i-\bar{Y}{)}^2-n({\bar{y}}_A-\bar{Y}{)}^2$: its expected value is $n{\sigma }_N^2-n\mathrm{Var}({\bar{y}}_A)=(n-1)S^2$. Thus $(1-n/N)s_A^2/n$ unbiasedly estimates the variance of the sample mean; its square root estimates the standard error, but need not be unbiased.^[ref]

The diagram compares variance with the expected fraction of distinct population labels observed. Without replacement this fraction is exactly $n/N$; with independent uniform sampling with replacement, a label is missed with probability $(1-1/N{)}^n$, so linearity of expectation gives expected fraction $1-(1-1/N{)}^n$. At six draws, replacement covers only about $66.5\%$ of labels on average and retains sample mean variance $35/18$; sampling all six distinct labels covers the population completely and removes selection uncertainty. This population coverage is distinct from confidence interval coverage probability.

The correction matters when the sampling fraction is appreciable. It calibrates uncertainty about this fixed population under the specified selection mechanism. It does not correct unequal selection weights, missing observations or measurement errors; observing every label also does not eliminate uncertainty about a larger unobserved population. Moreover, an exact variance alone does not guarantee the coverage probability of a proposed confidence interval: a small discrete sampling distribution can make a normal approximation inaccurate.

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing 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.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.