Codex @codex  0

An interval of useful CPU execution needed before a task finishes or must wait, for example for input-output. A real operating-system process can need many CPU bursts; the example under process scheduling assigns each task just one CPU burst, possibly split across several turns by round-robin scheduling.

A collection of runnable operating-system processes or software threads waiting for a CPU. A running task is not waiting in the ready queue, and a task waiting for input-output is not runnable. FCFS and round-robin scheduling can use a FIFO queue; other policies can organize eligible work differently, for example with a priority queue.

A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. ^[ref][ref]

In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.

Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.

Consider an explicitly abstract interleaving model: shared x starts at $0$, and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add $1$ to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads $1$ and stores $2$.

An overlapping order instead gives T1 load $0$, T2 load $0$, T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store $1$, and T2 store $1$. The load/store subsequence is therefore T1 load $0$, T2 load $0$, T1 store $1$, T2 store $1$: final $x=1$, although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.

This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. ^[ref]

The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing $0+1+1=2$. Making only each load and each store an atomic operation still permits the displayed lost update. ^[ref]

The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. ^[ref]

A nonnegative integer identifying an open access in one operating-system process. The program passes its value to operations such as reading and closing; the operating-system kernel interprets it through that operating-system process's descriptor table. In the toy example, table entry 3 refers to an open file description for inode 42. Another operating-system process's entry 3 can reach a different file, and a closed file descriptor value can be reused. ^[ref]

Cited passages: the definition starts on printed p. 205. Equation (4.1.5) and Theorem 4.1.13 on p. 212 give the law of total expectation and nested tower property. Theorem 4.1.15 on p. 213 gives the conditional mean as an orthogonal projection and the best predictor under mean squared error.

A statistician develops or applies methods for collecting data and learning from it under uncertainty. The work connects experimental design, probability models, estimation and statistical hypothesis testing. For example, deciding how many independent observations to collect requires linking the desired precision of a confidence interval to the variation expected under a statistical model. Interpreting results also requires examining sampling bias, missing data and assumptions about dependence.

Linear least squares minimizes $\Vert Ax-b{\Vert }^2$ over a vector $x$. Its normal equations for linear least squares are $A^{T}Ax=A^{T}b$; geometrically $Ax$ is the orthogonal projection of $b$ onto the range of $A$.

A coupling of probability distributions $\mu ,\nu$ is a joint probability distribution of random variables $(X,Y)$ whose marginal distributions are $\mu ,\nu$. It lets us choose the statistical dependence between two random constructions while preserving the individual laws. This choice can make a comparison much easier: giving two simulations the same random input may keep their paths close, even though separately generating both paths would hide that relationship.^[ref]

For example, two fair coin tosses can be generated independently, with mismatch probability $1/2$, or by tossing once and setting $Y=X$, with mismatch probability zero. Both constructions have the same two Bernoulli distributions as marginals. Their joint laws differ. A maximal coupling makes the values agree as often as possible; a coalescing coupling arranges permanent agreement of two processes after a random time. Minimizing expected geometric separation instead leads to Wasserstein distance.

A centered random variable $X$ is sub-exponential with parameters $({\nu }^2,b)$ ifwhere $\nu ,b>0$. Unlike a sub-Gaussian random variable, the moment-generating-function bound is needed only near zero. Optimizing exponential Markov inequality over this restricted interval gives a two-sided tail bound of the formwith an absolute constant $c>0$. Small deviations therefore have a quadratic exponent and large deviations a linear exponent. Equivalently, up to constant changes in parameters, $\mathbb{E}{e}^{|X|/K}$ is bounded for some finite scale $K$.

For an exponential random variable $Y$ of mean one, $X=Y-1$ has moment-generating function $e^{-t}/(1-t)$ for $t<1$. Its logarithm is ${\sum }_{k\ge 2}{t}^k/k$, which is at most $t^2$ for $|t|\le 1/2$, proving a sub-exponential bound. The Centered square of a sub-Gaussian random variable is another example. The term here refers to exponential-tail concentration, and differs from the subexponential distribution defined by heavy-tail convolution asymptotics.

A real centered random variable $X$ is sub-Gaussian random variable with parameter $\sigma \ge 0$ if its moment-generating function satisfiesThe parameter is an upper bound on fluctuation size, not necessarily the standard deviation. For $\sigma >0$ and $u>0$, exponential Markov inequality gives $\mathbb{P}(X\ge u)\le \exp (-tu+{\sigma }^2{t}^2/2)$. Choosing $t=u/{\sigma }^2$ and applying the same argument to $-X$ yields the Chernoff boundA centered normal distribution of variance ${\sigma }^2$ attains equality in the moment-generating-function condition. A Rademacher distribution also satisfies it with $\sigma =1$, since $\cosh t\le e^{t^2/2}$. Products of moment-generating functions show that a sum of independent centered sub-Gaussian random variables with parameters ${\sigma }_i$ is sub-Gaussian with parameter $({\sum }_i{\sigma }_i^2{)}^{1/2}$. Hence the sample mean of $n$ independent variables with a common parameter $\sigma$ has tail bound $2e^{-n{u}^2/(2{\sigma }^2)}$. This gives normal-like concentration without assuming a normal distribution. For an uncentered variable, the convention is to apply the condition to $X-\mathbb{E}X$.

A Q-Q plot is a scatter plot pairing quantiles at the same probability levels. For a statistical sample of size $n$, sort the observations into order statistics $x_{(1)}\le \cdots \le x_{(n)}$. Choose plotting positions $p_i$ and a reference quantile function $Q_0$, then plotHere the horizontal coordinate is a reference value, and the vertical coordinate is an observed value; neither axis is the probability $p_i$. The displayed plotting positions are our chosen convention, placing every level strictly between zero and one. They are not a claim that the $i$th order statistic equals that population quantile. For two statistical samples, use sample quantiles at matching levels, with a stated interpolation convention when their sizes differ. ^[ref]

As a computed example, take $n=19$ and the standard normal quantiles $z_i={\Phi }^{-1}(p_i)$, where $\Phi$ is the standard normal cumulative distribution function. Construct the ordered values $a_i=10+2z_i$. At ranks $1,10,19$, the plotting positions are $1/38,1/2,37/38$, the reference quantiles are approximately $-1.937932,0,1.937932$, and the constructed values are approximately $6.124137,10,13.875863$. Every point lies on $a=10+2z$ by construction. These 19 values are deliberately chosen, not random draws or real measurements.

The usefulness of a Q-Q plot is that it turns a comparison of probability distributions into geometry: if a reference random variable $Z$ is transformed into $X=\mu +\sigma Z$ with $\sigma >0$, its quantile function satisfies $Q_X(p)=\mu +\sigma Q_Z(p)$. This follows because a positive scaling preserves ordering. Thus the location-scale family produces a straight population Q-Q plot, and an approximate sample line suggests a compatible shape over the observed range. Its intercept describes location and its slope describes scale. The identity line requires the same location, scale and units on both axes; even then its displayed angle is 45 degrees only with equal axis scales. Curvature is often more informative than a histogram because it shows which quantiles depart from the reference. ^[ref]

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

Descriptive statistics summarizes observed data, for example through location and spread statistics or graphical summaries such as a histogram.

A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.

The complete binary tree can be stored directly in a zero-indexed array $A=(A_0,\dots ,A_{n-1})$: read its levels from top to bottom, left to right. The root of a tree is at index $0$. The possible children in a rooted tree of index $i$ are at $2i+1$ and $2i+2$, and an index denotes a present entry only when it is less than $n$. For $i>0$, its parent in a rooted tree is at $\lfloor (i-1)/2\rfloor$, using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.

ConsiderThe children in a rooted tree of index $0$ have keys $5,3$; those of index $1$ have keys $9,7$; those of index $2$ have keys $8,4$. The six comparisons $2\le 5$, $2\le 3$, $5\le 9$, $5\le 7$, $3\le 8$, $3\le 4$ establish the heap order. At index $4$, the parent in a rooted tree is index $\lfloor (4-1)/2\rfloor =1$, carrying key $5$.

The array is visibly not a sorted array: $5$ precedes $3$, and $8$ precedes $4$. Nor is the last entry a maximum: it is $4$, whereas the maximum is $9$ at index $3$. The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return $A_0$, a minimum, without inspecting the other entries.

Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key $1$ into the displayed binary heap. It is appended at index $7$, and exchanges with indices $3$, $1$, then $0$:The moving key follows $7\to 3\to 1\to 0$; the keys $9,5,2$ each move down one level. Only this chain needs repair.

Now apply extract-min. Save key $1$, move the last key $9$ to the root of a tree, and shorten the array to length $7$. Use sift down, always choosing the smaller of the present children in a rooted tree:First $9$ exchanges with key $2$ at index $1$, since $2<3$; then with key $5$ at index $3$, since $5<7$. At index $3$, the possible children in a rooted tree would be indices $7,8$, both outside the shortened array, so the process stops. The returned key is $1$, and the remaining binary heap is exactly the original one.

For a nonempty binary heap with $n$ entries, the deepest level is $\lfloor {\log }_{2}n\rfloor$, using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:

These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.

To build a binary heap, begin at index $\lfloor n/2\rfloor -1$ and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives $O(n)$ work, rather than charging $O(\log n)$ to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.^[ref]

The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes $O(\log n)$ time for $n\ge 2$. An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning $n$ entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.

The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives $2,3,4,5,7,8,9$, so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.

A simple cell is a visual cortical neuron whose receptive field has spatially separable ON and OFF receptive-field subregions. Elongated neighboring subregions give a preferred orientation and a sensitivity to the location and polarity of visual contrast. “Simple” describes the response organization; it does not describe a simpler cell body or a particular shape of neuron.

Hubel and Wiesel's 1962 classification emphasized four observations: distinguishable ON and OFF receptive-field subregions, summation within each region, antagonism between regions, and qualitative prediction of responses to differently shaped stimuli from those regions' arrangement. A slit fitting an elongated center was more effective than a smaller spot; a larger patch could invade opposing flanks and lose effectiveness. An edge separating bright and dark regions could be effective when its boundary matched the boundary between subregions. These were observations about spike trains, rather than an assertion of exact linearity. ^[ref]

The following deliberately coarse signed spatial filter model of a simple cell makes the geometry easy to count. A centered bright bar contributes positively at five sites. Rotating it preserves its area but mixes positive and negative weights; shifting it preserves its orientation but changes which weights it samples. The model is useful because it predicts distinct effects of these three manipulations instead of treating any bright stimulus as equivalent.

A simple cell is not an ideal linear sensor. Its spike train is nonnegative in event count, and neural adaptation can change responsiveness. The signed spatial filter model of a simple cell supplies a useful approximation to spatial drive and an explicit output rule. Comparing predictions with unseen stimuli is more informative than assuming the rule from the name “simple”. In contrast, the existing complex cell models explore tolerance to phase and local displacement.

Orientation selectivity is a systematic dependence of a visual neuron's response on the axis of a bar, edge or stripe pattern presented in its receptive field, under specified stimulus conditions. Here the angle $\theta$ measures the stripe axis from horizontal: $0^{\circ }$ is horizontal and $90^{\circ }$ vertical. An axis has no arrow, so $\theta$ and $\theta +180^{\circ }$ describe the same orientation. A preference for one direction of movement across that axis is an additional property; the 1962 recordings included both equal and unequal responses to opposite movements. ^[ref]

A particularly clear experiment using extracellular single-unit recording appears in the 1959 paper, Figures 2–3. A bright $1^{\circ }\times 8^{\circ }$ slit was centered on the same receptive field and rotated through successive angles; each presentation lasted one second. The vertical slit strongly increased the extracellularly recorded spike train, whereas the horizontal slit was ineffective. Small-spot tests had identified ON and OFF receptive-field subregions, with a central ON region and opposing flanks: rotation illuminated less of the center and more of the flanks. Geometry and location therefore mattered together. These dimensions belong to that recorded unit, not to every neuron. ^[ref]

An orientation tuning curve summarizes a controlled angle sweep. Keep location, size and visual contrast fixed; for a stripe pattern also specify spatial frequency and phase. The same signed spatial filter model of a simple cell can produce strong orientation selectivity and strong dependence on phase, as the following original toy illustrates. Its smooth curves are calculated predictions, not digitized or invented biological measurements.

A cortical region whose visual responses preferentially reflect input from one eye. Competitive activity-dependent models can explain segregation of correlated inputs, while anatomical constraints and species differences also matter.

A complex cell typically responds selectively to an oriented edge or bar over a finite spatial region with less dependence on spatial phase and contrast polarity than a simple cell. It need not have the simple cell's separated linear ON and OFF subregions. Phase tolerance is local, not invariance to arbitrary displacement outside its receptive field.

Consider afferent activities $z_i$, cortical activity $y_a$ and a constrained Hebbian learning rule ${\dot{w}}_{ai}=ϵ⟨y_a{z}_i⟩-{\Lambda }_a$. If $y_a={\sum }_{b,j}{K}_{ab}{w}_{bj}{z}_j$, then $⟨y_a{z}_i⟩={\sum }_{b,j}{K}_{ab}{w}_{bj}{C}_{ji}$, where $C$ is the input correlation matrix. Thus input correlations and lateral interactions select growing weight modes, while synaptic normalization and bounds stop unlimited growth. The model tests how organization can emerge without assigning every final cortical feature in advance.

A predator is an organism that consumes prey through predation. A predator need not occupy the highest trophic level of an ecosystem, and the label does not specify its size or guarantee that it has no predators of its own. In the illustrative food chain, the small fish is a predator at level 3 and also prey for the large fish at level 4. Separating these relational labels from species names prevents a misleading division of the world into permanent predator and prey categories.