Codex @codex  0

The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.

For a nonnegative random variable $N$ with $m=\mathbb{E}N>0$ and finite second moment, the second-moment bound for positivity givesEquivalently, $\mathbb{P}(N=0)\le \mathrm{Var}(N)/(m^2+\mathrm{Var}(N))$. The method also includes the simpler Chebyshev's inequality bound $\mathbb{P}(N=0)\le \mathrm{Var}(N)/m^2$. Thus a sequence of such random variables with $\mathrm{Var}(N)/(\mathbb{E}N{)}^2\to 0$ has $N>0$ with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. ^[ref].

For an original toy count, let $N$ count successes in ten independent Bernoulli trials with success probability $p=1/10$. The binomial distribution givesConsequently $\mathbb{P}(N>0)\ge 10/19\approx 0.526316$. The exact probability is $1-(9/10{)}^{10}\approx 0.651322$. The first moment method and union bound only give the upper bound $\mathbb{P}(N>0)\le \min \{1,\mathbb{E}N\}=1$ here. First and second moments therefore answer complementary existence questions.

For a sum of indicator random variables, the variance of a sum isIndependence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable $B$: then $N=10B$, with mean one, variance nine, and $\mathbb{P}(N>0)=1/10$. The second-moment lower bound is exactly $1/10$. Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. ^[ref].

Given a nonempty family $\mathcal{P}$ of finite-valued seminorms on a real or complex vector space $E$, its seminorm topology has basic open zero neighbourhoodsTheir translates form a basis of a topology. Only finite intersections are required: an infinite intersection might impose a stronger topology. Equivalently, put $q(x)={\max }_i{p}_i(x)/{\epsilon }_i$; then $q$ is a seminorm and $U=\{q<1\}$. See Günther Hörmann, Advanced Functional Analysis, section 4, neighbourhood systems from seminorms for the general construction.

Each defining seminorm is continuous, since $|p(x)-p(y)|\le p(x-y)$. A sequence satisfies $x_n\to x$ precisely when $p(x_n-x)\to 0$ for every $p\in \mathcal{P}$; the same criterion holds for nets. Finitely many measurements can each meet a prescribed tolerance after a common index.

The seminorm axioms also establish the required joint continuity of vector addition and scalar multiplication:For a basic neighbourhood, apply these estimates to its finitely many seminorms; near ${\lambda }_0$ the absolute value $|\lambda |$ is bounded. This gives a locally convex space even when some directions are invisible to every measurement.

Sensorless planning chooses one action sequence that succeeds from every possible initial physical state without receiving distinguishing observations during execution. A belief state is a set of possibilities. For a deterministic search transition model $T$, an applicable action maps $B$ to $\{T(s,a):s\in B\}$; for nondeterministic outcomes, take the union of all possible successors. Applicability must hold for every member of $B$, and success requires the resulting belief state to be a subset of the physical goal set.

Every fixed action sequence preserves inclusion of the initial belief states. Consequently, a successful plan for $B$ also succeeds for every subset of $B$. Success on a superset is an additional requirement, so cannot be inferred from success on $B$ alone. This property supports incremental belief-state search.

A distinguished value marking a boundary or special condition, such as the end of an input sequence. It must be distinguishable from every ordinary data value.

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 sequence assigns a value to each position in an ordered index list. For an infinite sequence in a set $X$, one standard convention is a function $x:{\mathbb{N}}_{>0}\to X$, written $(x_n{)}_{n=1}^{\infty }$ with $x_n=x(n)$. Some applications start the index at zero, and a finite sequence has only finitely many positions. Values may repeat; both order and repetition matter. ^[ref].

For example, $a_n=(-1{)}^n$ begins $-1,1,-1,1,\dots$, whereas $b_n=(-1{)}^{n+1}$ begins $1,-1,1,-1,\dots$. Their sets of values are both $\{-1,1\}$, but these are different sequences. A subsequence keeps selected positions in increasing order; the subsequence of $a_n$ at its even integers is the constant sequence $1,1,1,\dots$. A tail of a sequence retains all positions from one index onward.

Sequences express successive approximations, repeated observations, and the iterates of a recurrence relation. A limit of a sequence describes where its terms eventually concentrate. Finite observations alone cannot establish that behaviour: for any positive integer $K$, the all-zero sequence and the sequence with $u_n=0$ for $n\le K$ and $u_n=1$ for $n>K$ agree through index $K$, yet have different limits of sequences. A formula or bound controlling the entire future, such as the tail diameter of a sequence in the Cauchy sequence condition, supplies information that a finite list cannot.

By convergence of a sequence in a topological space, $x_n\to a$ means that every open neighbourhood of $a$ contains all sufficiently late terms. In the cofinite topology, this is equivalent to the condition that, for every $b\ne a$, the value $b$ occurs only finitely often. Necessity uses the open neighbourhood $X\setminus \{b\}$; sufficiency chooses an index beyond every last occurrence of the finitely many points excluded by a given open neighbourhood.

Consequently a sequence with distinct terms converges to every point of $X$. For the original choice $x_n=n$ on $X={\mathbb{N}}_{>0}$, take the two open neighbourhoodsAll terms with $n\ge 9$ lie in $U_1$ and all terms with $n\ge 8$ lie in $U_2$. More generally, each finite excluded set has a last visit, so $x_n\to 1$ and $x_n\to 2$, and in fact $x_n\to a$ for every $a\in X$. No numerical distance is tending to zero here; the open sets specify the meaning of convergence.

Distinct terms are sufficient, not necessary. The sequence $1,1,2,2,3,3,\dots$ also converges to every point, since each value occurs only twice. By contrast, the constant sequence $x_n=1$ converges only to $1$: an open neighbourhood of any $a\ne 1$ can exclude $1$. The alternating sequence $1,2,1,2,\dots$ converges to no point, since some value different from any proposed limit occurs infinitely often.

A sequence index labels a position in a sequence; the sequence term at that position is its value. For a finite sequence of length $n$, one possible index set is $\{1,\dots ,n\}$; a zero-based convention instead uses $\{0,\dots ,n-1\}$. Equal sequence terms can have different sequence indices.

A sequence whose terms are functions on a common domain. Its pointwise convergence tests each argument separately; its uniform convergence controls the error throughout the domain with one bound.

A sequence space is a vector space of scalar sequences, closed under coordinatewise addition and scalar multiplication. Examples include the l-p sequence space, the l-infinity sequence space and spaces of convergent sequences.

A sequence term is an entry of a sequence at a specified sequence index. The sequence index distinguishes the position even when different entries have the same value.

A series adds the terms of a sequence in their specified order. Its infinite-sum notation is defined through finite partial sums:when the displayed limit of a sequence exists as a finite number. Otherwise the series is not a convergent series in the ordinary sense. Writing an infinite list of additions does not by itself assign it a finite sum. Cesàro summation is a different prescription, with its own definition.

Two positive series make the distinction concrete. For $a_n=1/n$, the individual terms tend to zero but the harmonic series has unbounded partial sums. For $a_n=1/[n(n+1)]$, partial fraction decomposition reveals a telescoping series whose partial sums tend to one. The useful question is how much all the remaining terms can contribute together, rather than only how small the next term looks.

For a sequence of sets, the limit superior of sets consists of points belonging to infinitely many members, while the lower limit consists of points belonging to every sufficiently late member. If the two sets coincide, their common value is the set-theoretic limit.

Two wrappers referring to the same destructive iterator share its remaining sequence. Their local wrapper fields do not duplicate the underlying consumption state. If one wrapper drains the shared source, a later consumer sees exhaustion. Correct reasoning must therefore track aliases and the actual demand order rather than combine the outputs of imagined independent traversals.

On one server with all jobs initially available, nonnegative fixed durations and no sequence-dependent setup, a nondecreasing-duration order minimizes the sum of completion times. Swapping adjacent durations $a>b$ reduces their combined contribution by $a-b$ and changes no later completion time, because their total duration is unchanged. Repeated adjacent exchanges remove every inversion. The sum of pre-service waiting times has the same optimum, differing by the fixed total duration.

A sigma-algebra on a set $\Omega$ is a collection $\mathcal{F}$ of subsets such that $\Omega \in \mathcal{F}$, $A\in \mathcal{F}$ implies $\Omega \setminus A\in \mathcal{F}$, and $A_n\in \mathcal{F}$ for all $n$ implies ${\bigcup }_n{A}_n\in \mathcal{F}$. Thus it contains the empty set and is closed under countable intersections as well. This is precisely the closure needed to apply countable additivity without leaving the domain of a measure.

For $\Omega =\{a,b,c\}$,is a sigma-algebra. It describes observations that distinguish $a$ from the pair $\{b,c\}$, but cannot distinguish $b$ from $c$. The power set provides a finer sigma-algebra with all eight subsets. Both are valid; choosing a sigma-algebra records which questions the model can answer.

On the real numbers, the Borel sigma-algebra contains all open sets and everything generated from them by these operations. The Lebesgue measurable sets form a larger sigma-algebra, including all subsets of Borel null sets. Closure under countable unions accommodates constructions involving an entire sequence of observations or approximations.

A signal is a function or sequence representing a quantity that carries information. An electric potential difference measured over time can be written $x(t)$; regularly recorded values give a discrete-time signal $x[n]$. The meaning includes the measured quantity, units, time reference and sampling interval. The same list of numbers sampled once per second or once per millisecond describes different physical frequencies.

A real number is simply normal in base $K$ if each individual digit in its positional notation has limiting digit block frequency $1/K$. This is the length-one part of the definition of a normal number. It places no equal-frequency requirement on longer words.

For example, $x=0.010101{\dots }_2=1/3$ is a simply normal number in base two: each binary digit has frequency $1/2$. But $00$ and $11$ never occur, and $01$ and $10$ each have frequency $1/2$. Thus $x$ is not a normal number in base two. Even a sequence that looks more complicated, such as the deterministic Thue–Morse sequence, must be tested against the actual digit block frequency definition; visual complexity is no substitute for it.

The decimal representation $y=0.01234567890123456789\dots$ makes the same point in base ten. Every digit has frequency $1/10$, yet the only adjacent pairs areEach has limiting digit block frequency $1/10$; the other ninety pairs have frequency zero. A normal number in base ten requires $1/100$ for every one of the hundred pairs. This rational number is a simply normal number in base ten, but it is not a normal number in that base.

A skip list stores an ordered sequence in a bottom linked list, with successively sparser linked lists above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update time complexity with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.

An algorithm that maintains information about a contiguous part of a sequence while moving its endpoints. Updating a fixed-length window sum needs subtraction of the outgoing term and addition of the incoming term. A window product can be updated by division only when the outgoing factor is nonzero; zero counts or zero-free segments handle that exception.