Use the natural filtration and the usual integrable definition of the Snell envelope. Since the factors are positive, its terminal value is . If , independence of random variables gives
The backward recursion therefore becomes
This proves the assertion by backward induction. All constants are finite and at least one. More explicitly,
where the empty product is one. This is the Snell envelope of a multiplicative process. The standard Snell envelope hypothesis includes integrable rewards; independence of random variables and positivity then give finite first moments of the factors. If that hypothesis is dropped, an infinite-mean factor gives an infinite continuation value, so finite constants need not exist.
For the discrete-time binomial market, write . The assumptions give , positive bank account and stock prices, and
Thus
The finite discrete-time fundamental theorem of asset pricing states that a market with a strictly positive numéraire has no arbitrage if there is an equivalent probability measure under which all numéraire-denominated asset prices are martingales. The original probability measure is already such an equivalent martingale measure, proving no arbitrage.
The complete-market American-option pricing theorem identifies the discounted replication or superhedging value with the Snell envelope of the discounted exercise rewards. Here
The independent factors have common mean
The Snell envelope recursion consequently gives . At every time before , the continuation value strictly exceeds immediate exercise, so optimal exercise is at maturity. The undiscounted value process is , and the time-zero replication cost is
In fact is a martingale, not just a supermartingale, because the Snell envelope has no exercise compensator before maturity.
To hedge the optimally exercised payoff, subtract the two next-state portfolio equations. The first-period delta hedge is
The corresponding bank account holding, since , is . Substitution into either next-state equation verifies both terminal values at time one. Repeating this two-state calculation at every node gives a self-financing strategy replicating the maturity payoff. It also covers earlier exercise: at all dates, so the seller can meet any earlier payment with the available wealth.
A one-period self-financing strategy is a deterministic holdings vector , with initial cost and terminal wealth . In the zero-initial-cost convention, an arbitrage satisfies
The convention allowing a nonpositive initial cost is equivalent here: invest any initial proceeds in the strictly positive numéraire to obtain a zero-cost portfolio with nonnegative terminal wealth.
Suppose a strictly positive state-price density satisfies the asset-pricing equations, with the indicated products integrable. By linearity,
For an arbitrage, the right-hand side is zero while the left-hand side is strictly positive, since the integrand is nonnegative and is positive with positive probability. This contradiction proves absence of arbitrage.
An attainable European contingent claim is a terminal random payoff for which some holdings vector satisfies almost surely; its replication cost is . To prove uniqueness in a complete market, suppose is another positive state-price density. For every event , attainability gives a portfolio replicating . Its initial cost has both representations, so
The signed random variable here is integrable, because . Take to be the event where it is positive and then where it is negative. Both its positive and negative parts have expectation zero, and hence vanish almost surely. Since ,
This proves that complete markets have unique state-price densities without requiring an extra lower bound on the random terminal numéraire.
For the finite-state example, order the states from top to bottom in the diagram and write the density values as . The two pricing equations are
Adding gives . Put ; substitution then gives
These are all the strictly positive solutions, and each satisfies both equations. The parameter is a state-price-density value, not a probability.
For a concrete unattainable contingent claim, take the payoff vector . A replicating portfolio would have to satisfy and in the first and third states. These imply , contradicting the required payoff one in the middle state. Thus the market is an incomplete market, despite having strictly positive state-price densities.
A martingale describes an observable after its predictable drift has been removed. For a Markov chain the drift is the change produced by its transition operator; for Brownian motion it is one half of the Laplacian. Requiring the resulting processes to be martingales for a sufficiently rich class of observables determines the transition law itself. The same identities, combined with optional stopping, determine hitting probabilities, expected exit times and recurrence or transience. The duplicated Q5 paragraph in the PDF is a repeated printing of this one essay request.
For a finite or countable-state Markov chain with transition matrix , define for a bounded test function . The Markov property says . Consequently
is a martingale, since each increment has conditional expected value zero. Conversely, if these processes are martingales for every bounded , taking the conditional expectation of an increment recovers that identity. With it gives for every state . Thus, given the initial law, these identities characterize the Markov chain, not merely a few of its moments. This is the discrete-time Markov chain martingale characterization.
The drift operator is . If away from a target set, is a stopped martingale, where is the first hit of that set. Under boundedness or suitable uniform integrability, the optional stopping theorem expresses in terms of boundary hitting probabilities. Similarly, if away from the target and on it, then is a martingale, giving when the terminal limit is justified.
For a concrete calculation, take a simple symmetric random walk on stopped at , its first hit of or . In the interior, has zero drift, while satisfies
The stopped identity gives , proving finite with finite mean. Bounded convergence in both stopped identities now yields the gambler's ruin answers
This illustrates why the integrability justification is part of using a martingale, rather than an automatic consequence of writing an equation.
For a finite-state continuous-time Markov chain with generator matrix , the corresponding martingale problem for a continuous-time Markov chain uses
These are martingales. Conversely, suppose an adapted càdlàg finite-state process satisfies these identities. Let , fix , and set . Then . Apply deterministic integration by parts to the finite collection of indicator martingales to obtain the time-dependent Dynkin formula: is a martingale. Therefore
This recovers the Markov property and the entire semigroup, proving the characterization. On countable spaces one uses nonexplosion and localization to justify the analogous unbounded-rate formulas.
For -dimensional Brownian motion, the Itô formula shows that, for ,
is a true martingale, since its bounded derivatives make the integral square-integrable on each bounded horizon. This is the martingale problem for Brownian motion with generator .
Here is why it also characterizes Brownian motion. Suppose a continuous adapted process , with , satisfies that martingale problem. Use smooth cutoff test functions equal to and inside successively larger balls, and stop before leaving those balls. The coordinate tests show that are continuous local martingales; the product tests show that are local martingales. The Itô product rule consequently gives
the difference between the two proposed compensators is a continuous finite-variation local martingale, hence constant and zero at time zero. For each , another application of the Itô formula gives the exponential local martingale
Its modulus is the deterministic quantity , so it is a true martingale on every bounded time interval. Taking its conditional expectation and dividing by its known value at time gives
The conditional characteristic function identifies a centered multivariate normal distribution of covariance , independent of the past. Together with continuity, this is the defining law of Brownian motion. This proves the Lévy characterization of multidimensional Brownian motion in the form needed for the generator characterization.
The analytic use of these martingales parallels the chain case. A harmonic function satisfies , so it yields a stopped local martingale until the process leaves its domain of harmonicity. Bounded stopped observables permit optional stopping and solve boundary hitting problems. A solution of with zero boundary values gives an expected exit time. For example, in the ball of radius , gives ; stopping first at proves finiteness and justifies the limiting calculation. The Brownian local time construction in Q4 is another example: the predictable compensators of approximations to recover its increasing occupation term.
We now prove the required three-dimensional transience of Brownian motion in dimension at least three, in the strong sense almost surely. Start first at a point with , and let be the first exit from this annulus. The radial Laplacian in dimension three gives
Thus is a bounded martingale. The exit time is finite: stopping gives . At exit, continuity puts at either or . The optional stopping theorem therefore yields
and hence the Brownian sphere-hitting probability in dimension three
As , the events increase to : a continuous path is bounded on the finite interval preceding any finite inner hit. This argument assumes no transience. Consequently
To pass from a positive escape probability to almost-sure eventual escape, take Brownian motion started at zero. Let be its first hit of the sphere of radius . Stopping the squared-norm martingale proves . At , the Strong Markov property and the preceding hitting formula give
The Strong Markov property here follows from independent Brownian increments by approximating a stopping time from above with dyadic-valued stopping times and using path continuity. Choose . The exit times increase to infinity, since a continuous path is bounded on every compact time interval. The events of a return to the closed ball of radius after decrease and have probabilities . Their intersection has probability zero. Thus almost surely there is some finite exit time after which the path never again enters that ball. Apply this simultaneously to all positive integer . This proves the last visit to a bounded ball for three-dimensional Brownian motion conclusion and therefore
For , the continuous martingale is . Since has the centered normal distribution of variance ,
For , the continuous martingale is . The Gaussian fourth moment gives
This verifies both cases. The time integral in the printed identity is understood with its omitted .
Write . The derivatives of the approximations are
Thus . The Itô formula gives . This use of the formula is valid despite the two second-derivative discontinuities: mollify the function , whose derivative is Lipschitz. Its smooth derivatives converge boundedly, while the second derivatives are bounded by and converge except at . For every , the normal distribution of assigns those points zero probability. Dominated convergence for the drift integral and the Itô isometry for the stochastic integral pass the smooth formula to . Equivalently, this identifies the martingale in the assumed decomposition and permits its cross-covariances to be calculated.
If , then . The Itô isometry and Doob L2 maximal inequality therefore give, for every fixed ,
The Gaussian density is bounded by , so
Consequently the processes are Cauchy in the complete space of continuous random paths with norm . They have a continuous-path limit there. Limits obtained for different integer horizons agree on overlaps; choose these versions consistently. Each is adapted, and passing to the limit in shows that is a continuous martingale. Letting in the preceding bound proves the requested convergence, with an explicit rate:
The same Itô isometry identifies , with .
There is a genuine factor-of-two error in the last printed conclusion. The stated has second derivative almost everywhere, and the generator in the decomposition is one half of the second derivative. Hence the exact identity is
Because and , this already proves uniform convergence on bounded intervals to . It does not by itself prove almost-sure convergence of the full sequence, so we supply that additional step.
Take . For each fixed integer and each , the maximal-error bound and Markov's inequality imply
The first Borel-Cantelli lemma, applied to rational positive and integer , gives uniform almost-sure convergence of this subsequence on every bounded interval. Therefore uniformly there almost surely.
For , the indicator windows are nested. The ratio-one interpolation for shrinking-window occupation integrals gives
Both ratios tend uniformly to one as . The two bounds converge uniformly to the continuous nonnegative process , so the entire sequence does too. Thus the correct normalized conclusion is
and with the factor actually printed in the question the limit is
These are the occupation approximations for Brownian local time. In the Tanaka formula convention, is the local time of a semimartingale at zero. It is not identically zero: for , since starts at zero and is a martingale. Thus the discrepancy cannot be removed by treating the two limits as equal. The standard normalization is also given in Lalley's notes on the Itô calculus and local time.
On the real line, Prohorov's theorem states that a sequence of probability measures is uniformly tight if and only if every subsequence has a further subsequence converging weakly to a probability measure. Here uniformly tight means that, for every , some compact interval contains mass at least for every measure in the sequence. This is relative sequential compactness for weak convergence of probability measures, not merely the existence of one convergent subsequence.
We first prove the characteristic-function tail bound. Put . For ,
At the expression is zero by continuity. If , the supplied elementary bound, with , makes it at least . The integrand is nonnegative, so Tonelli's theorem yields
Thus one valid universal constant is
The estimate controls spatial tails using only the characteristic function near zero.
Apply it to each . For fixed , pointwise convergence of the characteristic functions and the bound allow dominated convergence on the finite integration interval, giving
Continuity of a characteristic function and make the last expression tend to zero as . Given , choose making it less than ; then for all sufficiently large , the preceding tail is less than . Enlarge the compact interval to handle the finitely many remaining probability measures. This proves uniform tightness of the whole sequence.
By Prohorov's theorem, every subsequence has a further weakly convergent subsequence, say with limit . The real and imaginary parts of are bounded continuous functions, so along that subsequence
The uniqueness theorem for characteristic functions implies . All subsequential weak limits are therefore . If the original sequence failed to converge weakly to , a bounded continuous test function and a subsequence would keep its integrals a fixed distance from the limiting integral; a further weakly convergent subsequence would contradict that. Hence
This supplies the required proof of the Lévy continuity theorem in the stated case.
For the final request, the printed is not defined; the intended function is , the characteristic function of a summand. We prove that without assuming integrability. Write . Independence gives . Moreover convergence in probability to implies uniform convergence of these characteristic functions on each bounded frequency interval: for and ,
First let , then .
The potential logarithm-branch ambiguity needs to be resolved, not discarded. By continuity of near zero, its principal complex logarithm is defined at for all and all large , with value zero at . Also
uniformly on , so uniformly there. The two continuous logarithms differ by an integer multiple of :
That integer is continuous in and zero at zero, hence identically zero. Consequently
For arbitrary nonzero , take and . Eventually , so dividing the preceding error by shows . Exponentiating at zero proves the derivative forced by the weak law:
This is the weak law forces a characteristic-function derivative argument. Its estimates use bounded exponentials, not . If is integrable, dominated convergence permits differentiation inside the expectation and gives , so then .
Absolute integrability is genuinely unnecessary. For an explicit weak law without an absolute first moment, take a symmetric variable with
with mass at zero and no mass with . This is a valid law: the specified tail decreases from to zero, and its derivative defines the continuous part beyond . Its absolute first moment is infinite because . For independent copies, set . Symmetry gives , and integration of the tail gives
For the last estimate, split the integral at ; the initial part is and the remainder is at most , apart from a fixed initial constant. Chebyshev's inequality now gives in probability. The probability that any truncation changes a summand is at most , so in probability although . The derivative is zero, but the usual expectation of does not exist.
If either the positive or negative part is integrable, the finite weak-law limit does force full integrability. For example, if , then is integrable and its sample averages have the weak law of large numbers limit . Since they are bounded above by the original averages, for every . Letting shows . The symmetric argument handles the other one-sided hypothesis. The nonintegrable example necessarily has both one-sided expectations infinite.
A Lévy measure on the real line is a nonnegative Borel measure satisfying
It records the intensity per unit time of jumps of a Lévy process. Under the additional small-jump first-moment condition, the uncompensated Lévy–Khintchine formula is
where and . The integral is absolutely convergent: near zero its integrand has absolute value at most , while outside a neighborhood of zero it is at most and has finite mass. If the usual compensated Lévy–Khintchine formula uses drift , this convention has .
A Lévy process starts at zero and has stationary independent increments and stochastic continuity. Its characteristic function at time is , with and continuous. The given time-one characteristic function is strictly positive. It therefore has the unique continuous logarithm vanishing at zero,
Any other continuous exponent would differ by an integer multiple of ; continuity on the real line and the value at zero make that integer identically zero. This determines all increment laws. More explicitly, for ,
Thus it determines every finite-dimensional distribution. For the standard càdlàg version of a Lévy process, coordinates at rational times determine the path, so these laws determine the entire process law on its canonical path space as well.
To find the Lévy measure, try the symmetric density . Its jump exponent is
Differentiation under the integral is justified by the integrable bound . The elementary Fourier sine transform gives
Since , integration in yields . Choosing matches the prescribed exponent exactly. This is the Lévy measure of a symmetric Laplace time-one law:
The candidate satisfies the Lévy measure condition because its density is of order near zero and decays exponentially at infinity; moreover . Uniqueness of the triplet in the Lévy–Khintchine formula proves that these are the required coefficients. The infinite mass near zero means infinitely many small jumps, not a Gaussian component; their total variation is finite on bounded time intervals because .
For , let be the number of completed upcrossings by the observations : buy when the value is at most , sell at the first subsequent value at least , and repeat. With , one form of the Doob upcrossing inequality for a martingale is
For completeness, hold either zero or one unit according to this rule. The holding at each step is measurable before the next martingale increment, so the total gain has expected value zero. Completed trades earn at least each; an unfinished trade loses at most . Thus , proving the inequality.
Suppose . For each rational pair the inequality and monotone convergence give
Every rational interval therefore has only finitely many upcrossings, simultaneously outside a countable union of null sets. If , there is a rational interval strictly between them and infinitely many upcrossings, a contradiction. Thus the limit exists in the extended real line almost surely. Fatou's lemma now gives
The limit is finite almost surely and integrable. This proves the martingale convergence theorem rather than using it as the deduction.
The exact extra condition for convergence in L1 is uniform integrability:
To see sufficiency, first discard the tails of uniformly and the tail of the integrable . On the set where both absolute values are at most , their difference is bounded by and tends to zero almost surely; dominated convergence finishes the proof. Conversely, if in , then
Make the first term uniformly small for all sufficiently large , then control the finitely many remaining integrable variables by increasing . Hence uniform integrability is necessary too. In this case the conditional expectation identity follows by taking the limit in for .
The coin-doubling martingale shows why an bound is not enough. Let be independent fair coin indicators and set
Conditional on the first coins, the next value is either or zero with equal probabilities, so this is a nonnegative martingale. Its expected value is always , while a first failure occurs almost surely, giving almost surely. Yet for every . Indeed, whenever , its tail expected value above is still . Thus convergence in L1 fails because uniform integrability fails.
Here is the rate per individual active flow, and is its route's aggregate rate. On routes with , a proportionally fair allocation is a feasible positive rate vector satisfying
for every feasible competitor , where feasibility means . This is equivalent to maximizing weighted logarithmic utility : its gradient gives the displayed inequality, and the supporting-tangent inequality proves sufficiency. The objective is strictly concave on active rates. Rates assigned to absent flows are irrelevant and may be set to zero.
For the linear flow network, an active local route can increase its rate if its link constraint has slack, improving the objective without affecting any other link. Thus
Put and . If and , eliminate the active local rates by . Up to constants, the utility becomes
Its derivative is , which vanishes exactly at
Strict concavity proves this is the optimum, and unused local links impose no stronger constraint because . If , maximizing gives , the same formula. If , each active local route has . These are the proportionally fair allocation on a linear flow network. When , there is no service to allocate.
The memoryless property of exponential document sizes makes a flow transmitting at rate complete with intensity . Summing over its flows gives the flow-level network model transition rates
and, for nonempty states,
All absent-route departure intensities, including those at the empty state, are zero. In particular the local completion rate is the aggregate rate , not . Total rates are bounded by , so the continuous-time Markov chain is nonexplosive.
Set and consider the weights
The binomial coefficient is the balance function of a flow-level network. For a through-route arrival, its adjacent-weight ratio is
The reverse departure rate is , so . For a local-route arrival,
and the reverse departure rate is , giving the same detailed balance identity. This includes arrivals from the empty state.
To normalize, first fix all local counts and sum over . The negative binomial series gives
The remaining geometric series factor, so
This is finite precisely under the stated strict load inequalities for each resource. Thus detailed balance proves the stationary law of a linear flow network:
With positive arrival rates this is the unique stationary distribution of the irreducible chain. Zero arrival rates are handled by restricting to the accessible class with their counts zero, interpreting .
Summing this distribution over gives local-count independence in a linear flow network:
These are independent geometric distributions. Differentiating a geometric series, or summing its mean directly, gives
This independence concerns the local counts at one stationary time; their evolving processes share the through route and are not independent processes.
Each user maintains a transmission rate . Resource measures its aggregate load and returns the resource congestion price . The user adds these feedback signals to form its route congestion price . Its increase term is the constant , while its decrease term is proportional to both its current rate and the congestion signal. This is a distributed congestion control algorithm: resources need only local loads, and users need only prices along their own routes.
There is a needed distinction in the word increasing. If it permits nondecreasing price functions, the all-zero prices are allowed. Then , so there is no equilibrium. The intended convergence statement holds when each nonempty route meets at least one resource whose price is positive at some load. This is automatic if every price is strictly increasing and nonnegative. We prove it under the more general nondecreasing assumption with this explicit condition, for finite sets of nonempty routes and nonnegative initial rates.
Write . Each is convex and nondecreasing, and the primal congestion potential is
On positive rates this is strictly concave: the sum of positive-weight logarithms is strictly concave, while the resource term is convex. Its derivatives are
Consequently the gradient flow with diagonal mobility satisfies
with equality exactly at an equilibrium.
We must also prove trapping and existence of the equilibrium. For each route choose a resource on it and constants such that its price is at least beyond load . Finiteness gives common constants . If is large, a resource on a maximizing route has load at least , so the resource penalty is at least . With , therefore,
Once all rates are bounded above, a rate tending to zero also makes through its positive-weight logarithm. Thus every nonempty superlevel set of is compact inside the positive orthant. A maximum exists by restricting to such a superlevel set, and strict concavity makes it unique, say . It is interior and satisfies , equivalently
Conversely every positive equilibrium is a stationary point of the strictly concave function and hence is this maximum.
Only continuity of the price functions is given, so it is useful to justify trajectories without silently assuming differentiability. Put and . The dynamics become ordinary gradient flow ascent, . The function is strictly concave on the positive orthant: its user terms are plus constants, and each penalty is a convex nondecreasing function composed with the convex load . Hence the supporting-tangent inequalities give
The squared distance between two solutions is nonincreasing, proving uniqueness even though the vector field need only be continuous.
Nonnegative initial rates enter the positive orthant immediately: along a solution, variation of constants in expresses as a positive exponential times plus a strictly positive integral. Also , so rates cannot become infinite in finite time. The distance argument applies after any positive time and, by taking that time down to zero, also proves uniqueness for initial zero rates.
For a positive starting time, the increasing traps the trajectory in a compact superlevel set. Its derivative has finite integral since is bounded above there. It is uniformly continuous in time, being a continuous function of the state on a compact set with bounded velocity. By uniformly continuous integrable functions vanish at infinity, . Every limit point consequently has for every , since all rates are bounded away from zero. There is only the limit point , so
This establishes global convergence of primal congestion control with the needed nonzero-price condition, and supplies the zero-price counterexample when increasing is read in the weak sense.
For the alternative increasing-supply resource-price dynamics, consider the dual congestion potential
Its domain is with every . Each integrated supply is strictly convex, because is strictly increasing, and each negative logarithm of a positive linear function is convex. Thus is strictly convex. Its sublevel sets are bounded: for each , gives a linear lower bound on the supply primitive at large , whereas the negative logarithmic terms grow only logarithmically in . A route-price sum tending to zero makes on a bounded set. A minimum therefore exists in this domain.
The derivatives are
If a used resource had at the minimum, then but , so increasing that coordinate would strictly lower . Therefore the minimizer has strictly positive prices at every used resource. An unused resource has its unique minimizing price zero. At used resources its equations are
The multiplicative dynamics are . On strictly positive used-resource prices, equilibrium is equivalent to these equations, and strict convexity proves existence and uniqueness of the positive equilibrium. No full-row-rank assumption on is needed here: the strictly increasing individual supplies already give strict convexity.
If zero prices at used resources are allowed, the unqualified uniqueness assertion is false because of boundary equilibria of multiplicative resource prices. For one unit-weight route using two resources and , all three price vectors
are equilibria. At the user rate is one; the first resource has demand equal to supply, while the second has zero derivative because its price is zero. The last two vectors do not minimize . Thus the positive-price domain, or a boundary rule preventing a used resource from remaining at zero price, is essential.
Finally, the primal and dual equilibrium equations agree when and are inverse functions on the relevant ranges. For example, continuous strictly increasing prices with and have inverses satisfying the stated supply assumptions. Then is equivalent to , while both systems have . With inverse price and supply functions, the two equilibria describe the same rates and prices. Without this relation they need not agree: for one route and one resource with , and , the primal equilibrium is while the dual equilibrium is .
Let be the routes serving source-sink pair . The source-sink route incidence matrix and link-route incidence matrix are
Thus fixes the demands, and gives link throughputs. Assume a finite route set with at least one route for each positive demand. A Wardrop equilibrium is a feasible flow for which every used route has minimum delay among the routes for its source-sink pair. Writing
this means that, for each , there is a number with for , with equality whenever . No individual user can reduce its delay by switching routes while treating the aggregate throughputs as fixed.
The feasible set is a nonempty compact convex set: within each source-sink pair its route flows lie in a simplex of total . The Beckmann potential
is continuous and convex, and has . It therefore attains a minimum on . For a differentiable convex function, minimizes exactly when
Indeed necessity follows by differentiating along the feasible segment from to , and sufficiency follows from the supporting-tangent inequality. This condition is equivalent to Wardrop equilibrium. Necessity of the route condition follows by moving a small amount of positive flow from a used route to any other route of the same pair. Conversely, under the route condition,
because the terms involving vanish and both flows have the same pair totals. This proves both existence and the claimed convex optimization characterization, with .
Since each is strictly increasing, its primitive is strictly convex. Thus is strictly convex in . If two minimizing flows had different link throughputs, their midpoint would have strictly smaller potential. Hence the equilibrium link throughputs are unique.
The route flows need not be unique. Consider one unit of demand through two successive stages, each with two parallel links, labelled in the first stage and in the second. The four routes are , and all link delays are . For any , choose
Every link then carries and every route has delay one, so each vector is a Wardrop equilibrium. They all produce the same link throughputs but give distinct route decompositions.
For the toll construction, put . The total delay is and the average delay is , so they have the same minimizers. Compactness of gives a global minimizer , with . Its differentiable objective satisfies the necessary route-flow inequality
This inequality is necessary even when total delay is not convex, since it follows from the right derivative along each feasible segment.
Use optimal-flow calibrated congestion tolling:
Here . The toll is nonnegative, continuously differentiable and nondecreasing, because . The perceived cost is strictly increasing. At it equals , so the displayed necessary inequality makes a Wardrop equilibrium for these perceived costs, by the preceding Beckmann potential argument. Their strictly increasing costs give unique equilibrium link throughputs. Therefore every tolled equilibrium has link loads and minimizes average delay. Constant tolls also suffice; the added positive-part term makes them genuinely traffic-dependent without moving the optimum. Zero total demand is the trivial empty-flow case.
The usual marginal external cost toll makes its Beckmann potential equal , but concluding that all its equilibria minimize requires convexity of . Strict increase of delays alone does not supply this. For example, on two parallel links with and demand six, the equal split is an equilibrium under marginal-cost tolls, while its total delay exceeds , the delay at . The calibrated construction avoids adding a hypothesis absent from the printed question.
For a fixed routing loss network, let be finite integer resource capacities and the integer resource requirement of one route- call. Assume each route uses a resource, independent Poisson processes of calls with rates , independent exponential distributions of holding times with parameters , and immediate rejection when any required resource is unavailable. There is no waiting. The continuous-time Markov chain of call counts has feasible set
Put and
The ratios of adjacent weights satisfy whenever the arrival is feasible. Thus detailed balance proves the product-form stationary distribution of a loss network,
An arriving route- call is admitted precisely when . By Poisson arrivals see time averages, its exact blocking probability is
Define to be zero if a capacity is negative. This is an exact finite sum, not an independence approximation for resource blocking events.
For the triangle, denote the physical link capacities by and the numbers of calls between the pairs by . Assume unit capacity per call on each traversed link, unrestricted instantaneous rearrangement of existing calls, no interruption or extra resource cost during rearrangement, and independent exponential distributions of holding times whose parameters depend on the endpoint pair but not on the chosen path. Arrivals for each pair are independent Poisson processes, and admission occurs whenever some routing of all calls is feasible. These assumptions make the count vector a Markov process even though individual paths can change.
The necessary cut constraints are
Each counts calls that must cross the two links separating one node from the others. They are also sufficient. If every pair count is at most its direct capacity, route all calls directly. Otherwise at most one pair can exceed its direct capacity: two such excesses would contradict their pairwise cut constraint. Suppose it is , and put . Route of these calls directly and divert the remaining through node . Route the other calls directly. The loads on links and are respectively and by the two cut constraints involving . This is an integer routing of every call. The other cases follow by relabelling.
Consequently the rearrangeable triangular loss network is equivalent, at the level of call counts and blocking, to a fixed routing loss network with three virtual node resources:
The columns correspond to , and a call uses its two endpoint resources. Its normalizer is
With now indexing virtual resources, the three exact answers are
The preceding detailed balance proof applies because departures occur at rates regardless of the current routing. Without unrestricted rearrangement, feasibility can depend on the existing path assignments and this equivalence need not hold.
Choose a surjection . Since is a Noetherian ring, a finite free module is a Noetherian module, and its kernel is a finitely generated module. Choose a finite free surjection and repeat. This constructs a resolution by finitely generated free modules
whose terms are, in particular, finitely generated projective modules. It may be infinite; the request is finite generation of every term, not finite length.
Now suppose the nonzero finitely generated module has finite projective dimension . For , its th syzygy in this free resolution is projective. Indeed, dimension shifting along the successive kernel sequences gives
for every module . The vanishing follows by computing the latter Ext functor from any length- projective resolution. Vanishing of makes every short exact sequence ending in split: apply the long exact sequence of Ext groups to a free surjection onto to lift its identity. Thus is a projective module. It is finitely generated by the preceding construction. Truncating gives
with every term finite projective.
Apply the Hom functor and write . At the top degree,
If this group were zero, would be surjective. The dual module of a finite projective module is finite projective, so this surjection has a section . Finite projective modules identify with their double dual modules: the evaluation map is an isomorphism for a finite free module and passes to its direct summands. Dualizing therefore gives . Hence splits, and is projective. Replacing the last two terms by this quotient shortens the projective resolution to length , contradicting minimality. This proves top Ext detects finite projective dimension:
For , is a nonzero finite projective module and embeds as a summand of . Some coordinate projection restricts nontrivially to , proving as required.
For infinite projective dimension, take the dual-number algebra and . Multiplication by has image and kernel both equal to , giving the periodic resolution over dual numbers
Applying makes every differential zero, so for every . A finite projective resolution would force all sufficiently high Ext functors to vanish. Thus .
The finite-generation hypothesis is essential if the middle sentence's “a module” is interpreted as an unrestricted new module. A concrete vanishing top Ext without finite generation occurs for and . This Noetherian ring has the exact free presentation
Injectivity of follows by examining the largest index of a finitely supported input, since is a non-zero-divisor. For exactness in the middle, use the relations to move a finite sum to its largest index ; its remaining coefficient is , which is zero precisely when its image in is zero. The map onto is surjective because every Laurent series has a lower bound on its exponents.
Applying gives on products the map . It is surjective: for any , set . These are well-defined formal power series, because each coefficient receives only finitely many contributions, and . Consequently . But : the image of every must lie in , since it is divisible by every power of . A nonzero projective module is a summand of a free module and therefore has a nonzero coordinate map to . Thus is not projective, while its displayed resolution has length one. In particular,
The nonvanishing conclusion proved above retains the finitely generated introduced at the start of the question.
Here the usual homological algebra convention is that the right-exact functor is additive. Module categories have enough projective modules, because any module is a quotient of a free module. Choose a projective resolution
Apply to the unaugmented chain complex and define the left derived functors by
Additivity ensures that preserves zero maps, sums of maps and homotopy identities, so the transformed differentials still compose to zero.
For a module homomorphism , lift it to a chain map between chosen projective resolutions. In degree zero, lift through using projectivity of . In each higher degree, the already constructed map lands in the next kernel; exactness of and projectivity of supply the next lift. Any two lifts are chain homotopic: their degree-zero difference lands in , so it lifts to . Inductively lift the remaining difference after subtracting the preceding homotopy term. This gives
Applying preserves this identity, so the lifts induce the same homology map. Identity lifts and composable lifts show that is a functor. Comparison lifts between two resolutions over the identity of are inverse up to chain homotopy; hence the construction is independent of the chosen resolution up to its canonical natural isomorphism.
Right exactness identifies naturally with . For a projective module , the length-zero resolution gives for . For a short exact sequence , the horseshoe lemma builds a degreewise split short exact sequence of projective resolutions. Concretely, lift the projective generators covering into and combine them with generators covering ; repeat on the kernels. The middle projective term in each degree is the direct sum of the two outer ones. An additive functor preserves these split sequences, and lifting cycles, taking their differentials and returning to the subcomplex produces the connecting maps in
This is the natural long exact derived-functor sequence. In particular, if has projective, then for , and . These are dimension-shifting formulas. Positive degrees can be killed by the surjection . If is exact, it preserves every resolution's exactness and all its positive left derived functors vanish. Conversely, if vanishes on all modules, the displayed long exact sequence makes exact. A natural transformation between additive right-exact functors induces transformations on the left derived functors by applying it termwise.
For extension of scalars , these derived functors are the Tor functors . When and is a non-zero-divisor, there is the length-one free resolution
Although the construction above resolves , one may instead use this resolution of . To justify that calculation, tensor a free resolution of with the two-term resolution of to form a double complex. Taking homology first along the resolution of leaves ; taking it first along the resolution of leaves . The free terms preserve exactness under tensoring. The double complex is first-quadrant with finitely many terms on each total diagonal, so both filtrations compute the same total homology. This proves the required balancing directly.
The kernel and cokernel of multiplication by now give Tor for a principal non-zero-divisor quotient:
These are naturally -modules. For , the degree-one group is zero; for , multiplication by is zero and both degrees zero and one are . Thus, when , degree one explicitly detects the failure of this base-change functor to be exact.
An algebraic line bundle over is an invertible module: a finitely generated projective module such that for every prime ideal . Define the Picard group of a ring as the set of its isomorphism classes, with
The tensor product of modules of two finite projective modules is finite projective: write each as a direct summand of a finite free module and tensor the two decompositions. Localization gives , so this multiplication stays within the set of invertible modules. It is well defined on isomorphism classes. The associativity and symmetry isomorphisms of the tensor product give associativity and commutativity, and is the identity.
Let be the dual module. A finite direct-summand presentation shows that is finite projective and that localization commutes with this dual. Since is free of rank one, so is . The evaluation homomorphism
is an isomorphism after every prime localization. Its kernel and cokernel are therefore zero, by exactness of localization and localization detects zero elements for modules. Thus , proving that is an abelian group.
For a ring homomorphism , tensoring a split presentation gives , so is finite projective. For put . Every element of becomes a unit in , and
This proves base change of invertible modules. Moreover, the canonical map
is an isomorphism, with inverse . It shows that is a group homomorphism. Identity maps induce the identity, and for , the associativity isomorphism proves composition compatibility. Therefore is a covariant functor to abelian groups.
The polynomial ring is a principal ideal domain by division with remainder. A submodule of a finite free module over a principal ideal domain is free: induct on the ambient rank, project onto the first coordinate, and note that the image is a principal ideal, hence either zero or a free rank-one module. This gives a split exact sequence with that image as quotient; the kernel lies in a free module of one smaller rank, completing the induction. A finite projective module is such a submodule, and so is free. An invertible module has rank one after passing to the fraction field, so its free rank is exactly one. Hence every algebraic line bundle over is trivial and
A Noetherian module satisfies the ascending chain condition on its submodules; equivalently every submodule is a finitely generated module. If the latter condition holds, the union of an ascending chain has a finite generating set lying in one member, so the chain stabilizes. Conversely, a submodule with no finite generating set allows successive choices outside the submodule generated so far, producing a strictly ascending chain. A Noetherian ring is a ring that is Noetherian as a module over itself, equivalently one whose ideals are all finitely generated.
The formal power series ring consists of sequences written , with coefficientwise addition and the Cauchy product:
Every coefficient uses a finite sum; no analytic convergence is involved. Evaluation at zero gives . A quotient ring of a Noetherian ring is Noetherian, because its ascending chains of ideals lift to such chains upstairs. Thus one direction of Noetherianity of a formal power series ring is immediate.
For the other direction suppose is Noetherian, and let be an ideal. Define the coefficient ideals of a formal power series ideal
Each is an ideal, and multiplication by gives . Choose with . For , choose generators for , and choose series whose coefficients are those generators. Empty generating sets are allowed for zero ideals.
These finitely many series generate . To prove this without assuming that is closed, start with and cancel its coefficients successively. If the residual lies in , its coefficient lies in . Put ; since when , write that coefficient as and subtract . The new residual belongs to .
For , the generators are used only at the single step . For , their accumulated multipliers are the genuine formal power series . Thus the construction yields the exact coefficientwise identity
Every coefficient of the residual vanishes after finitely many steps. This is an ordinary finite generating expression in , not merely an approximation by elements of a smaller ideal. Therefore every ideal is finitely generated, proving
Finally, for the surjective module endomorphism , the kernels stabilize because is a Noetherian module. Take with . If , surjectivity of gives with . Then , so and . Hence is injective as well as surjective; its inverse is automatically -linear. This proves is an isomorphism, the statement that Noetherian modules are Hopfian.
Let be a multiplicative subset, containing one and closed under products. On , use
The relation is reflexive and symmetric. For transitivity, if and , then multiplication and addition give . Thus it is an equivalence relation. Write for the equivalence class. The localization of a ring has operations
They are well defined. For example, replacing by in its sum with gives cross-numerator difference , and in its product with gives . The same annihilating element kills both differences. Replacing the other input works identically. Associativity and distributivity then follow by putting all terms over the product of their denominators and using the ring identities in . Addition and multiplication are commutative, with identities and , and the displayed negative is an additive inverse. Hence is a commutative ring. If , the fraction relation identifies all elements, producing the zero ring.
The canonical ring homomorphism , , makes each a unit, with inverse . The universal property of localization states that any ring homomorphism sending into the units factors uniquely through . Define the factor by
If , then is invertible, so , proving well-definedness. The fraction operations prove that is a ring homomorphism. Its value is forced by , so it is unique. This property characterizes the localization up to a unique compatible isomorphism.
For a prime ideal , its complement is a multiplicative subset, and the localization at a prime ideal is . Fractions with numerator outside are units; those with numerator in form the unique maximal ideal . Thus it is a local ring.
For the nilpotent question, suppose and . Its annihilator is a proper ideal, so it lies in some maximal ideal . The fraction criterion says in only if for some , which is impossible by the choice of . Thus is a nonzero nilpotent element in that localization. This proves reducedness is detected by prime localizations: if every prime localization is reduced, has no nonzero nilpotent elements.
For the domain question take with a field. Its only prime ideals are and : a prime ideal must contain one of the orthogonal idempotents , and the corresponding quotient is . Localizing at makes invertible and kills , giving ; similarly . But with both factors nonzero. Therefore domain prime localizations do not force to be an integral domain, as expressed by domain prime localizations do not imply a domain.
Throughout, rings are commutative with identity and ring homomorphisms preserve identity. The spectrum of a commutative ring is . For an ideal , put ; these are the closed sets of the Zariski topology. Its axioms follow from
For the last equality, a prime ideal containing must contain or : if it contained neither, choose and , contradicting . The other equalities follow directly from containment. Thus arbitrary intersections and finite unions of closed sets are closed, proving that this is a topology.
The Zorn lemma says that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. For , apply it to proper ideals ordered by inclusion. The zero ideal is proper. The union of a nonempty chain is an ideal and is proper, because containing one would put one in a member of the chain; the empty chain has the zero ideal as an upper bound. There is therefore a maximal ideal . If , then , so the class of in is invertible. This quotient ring is a field, making a prime ideal. Hence .
For a ring homomorphism , define by . The inverse image is proper because , and primality follows from . Moreover
where is the ideal generated by . This proves continuity. Inverse images also give and . Thus is a contravariant functor from rings to topological spaces.
For the specified inclusion, the fundamental theorem of algebra gives the points and of . Over , the nonzero prime ideals are generated either by with , or by with , ; all irreducible real polynomials have degree one or two. Contraction gives the spectrum map for the complexification of a real polynomial ring:
Indeed, a real polynomial vanishing at a nonreal also vanishes at , and is divisible by their quadratic factor; the converse is immediate. This map is surjective. Its fibers contain one point over a real linear factor, two conjugate points over an irreducible quadratic factor, and only the generic point over zero. It identifies complex-conjugate pairs. Since each proper Zariski-closed set in either one-variable polynomial ring is a finite set of closed points, images of closed sets are closed; hence the Zariski topology on the target is the quotient topology for this identification.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact