This part's conditional-expectation representation is its own hypothesis; it does not need the incorrect unrestricted claim in part (b). Fix , and write
The assumed representation makes a martingale. The stochastic Fubini theorem gives
Apply the Itô formula to and use the equation for from part (a), including the cross-variation. The result is
Uniqueness of the continuous semimartingale decomposition makes the drift vanish. Initially this is a statement; the assumed continuity in time and maturity extends it to the continuous versions simultaneously. Let to obtain
Substitute back and differentiate the maturity integrals using their continuous integrands:
This is the forward drift restriction for square-root stock claims. The term comes from the product cross-variation and must be retained. For the uninformative zero-stock case, the representation does not identify ; as usual a positive initial stock price is understood.
The coefficient is , but independence alone does not make the printed right-hand side -measurable. The future variance integral need not be known at time . This is a genuine missing information assumption in the PDF.
The Itô formula or explicit stochastic exponential gives
If the volatility path is fixed at time zero and independent of , conditioning on that path makes the first factor an exponential of a centered Gaussian variable with the compensating half-variance, so its conditional expectation is one. More generally, this conditioning works when enlarging the filtration by the entire independent volatility path preserves the Brownian property. For the usual joint filtration of Brownian history and independent volatility history, the valid conditional square-root price under independent volatility is
When the integral is already -measurable, the outer conditional expectation can be removed, giving the intended printed formula. In particular this holds for deterministic volatility or an independent path disclosed initially.
For a counterexample to the unqualified printed assertion, take an independent fair Bernoulli variable , disclose it at time , and let
With the filtration generated by the Brownian history and this disclosure, is Brownian and is bounded, continuous, adapted, and independent of . At , the variance integral is , while is trivial. Direct Gaussian conditioning gives
a constant. The proposed factor is random, so cannot equal that conditional expectation. The formula requires knowledge of future integrated variance; independence by itself is insufficient.
For , the stochastic exponential solution stays strictly positive. Put . The Itô formula gives
Thus is a nonnegative local supermartingale. To justify the true supermartingale property, stop where or its stochastic integral exceeds successive bounds. The stopped Itô formula gives for . The conditional Fatou lemma and yield
In particular . The case is the identically zero process. This is the square-root stock supermartingale.
Use the conditional second-moment matrix from the PDF. By part (b), the filtration is finite-state at every finite time. On a time- atom let be the successor price vectors and their conditional probabilities. Then and
Positive definiteness gives rank , so . Hence , and the successor vectors have linear independence.
We use the finite-horizon fundamental theorem of asset pricing in deflator form: an arbitrage-free finite market admits a strictly positive adapted process , with , such that is a martingale. Equivalently, on every step,
Fix a finite horizon containing the step in question. On the parent atom, write on successor and . Then
The proposed values satisfy precisely the same equation:
Because the have linear independence and the are positive, this linear system has a unique solution. Thus , proving
This is the positive regression deflator in a complete finite market. It also proves the suggested conclusion: with and ,
Hence is a strictly positive martingale deflator. Finite-state structure makes these expectations integrable on each finite horizon. Positive definiteness alone would not ensure positivity of the regression factor; market completeness and the positive deflator are essential.
We prove the stronger finite branching bound in a complete market: modulo null sets, is generated by at most atoms. Here an atom is a positive-probability event which cannot be split into two positive-probability measurable pieces.
At time zero there is one atom because is trivial. Suppose has at most atoms, and fix one such atom . Any predictable process holdings over are constant on , so the restriction to of every time- replicable payoff lies in
a vector space of dimension of a vector space at most . If contained disjoint positive-probability events, their indicators would have linear independence on . Market completeness would replicate each indicator, contradicting that dimension bound.
For clarity, the absence of disjoint positive pieces implies that is a union of at most atoms: start with and repeatedly split any non-atom into two positive pieces. Each split increases the count by one. The process must stop before the count exceeds , and at termination every piece is an atom. Thus each time- atom has at most successors. Induction gives at most atoms at time .
Each disjoint positive-probability event contains at least one distinct atom. Therefore
The argument includes and uses the ability to replicate the indicator claims at every intermediate maturity.
A complete market permits claim replication for every finite maturity and every bounded claim measurable at that maturity: there are an initial capital and a predictable self-financing portfolio whose terminal wealth equals the claim almost surely. In a finite-state market this is equivalent to replicating every terminal payoff, since all such payoffs are bounded. Trading is allowed dynamically in the existing assets; adding a new security is not part of the definition.
Write . In a continuation interval, the Euler differential equation has power solutions and : substitution of gives . A decreasing bounded value uses the second solution.
Let be the exercise boundary. Value matching and smooth fit require and . Dividing gives . Consequently
This is a perpetual reciprocal-payoff American option.
To verify the obstacle inequality, observe that increases up to and decreases afterwards, because its logarithmic derivative is . Therefore for . In the continuation region . In the exercise region,
The quadratic is convex. At the two endpoints of it equals and , respectively, so it is negative throughout that interval. Thus the obstacle problem is satisfied on both regions, with value matching and smooth fit at . The second derivative has a jump at ; the equation is understood piecewise and in the generalized Itô sense described in part (a).
For optimality, use the Risk-neutral measure for the Black-Scholes model, under which . The Itô formula makes a nonnegative supermartingale, so every exercise time satisfies
Before hitting the exercise region, its drift vanishes. Since , the stopped process is a bounded martingale. Apply the optional sampling theorem at and let . The contribution from is at most , while the boundary value equals the payoff. Hence equality holds for
If , exercise immediately; otherwise wait for the first down-crossing. If that time is infinite, the discounted payout is zero. This proves both the value and the optimal stopping policy, and part (a) supplies its superhedge.
Figure 1.
Perpetual reciprocal-payoff option value and exercise boundary for two interest-to-variance ratios
. Details.
Put and define the nonnegative reserve rate . The obstacle problem gives and . The American-option superhedge with a funded reserve invests the local surplus in the bond rather than consuming it.
For initial wealth , set
and choose the stock and bond holdings
Thus and , pathwise at every time. The Itô formula under the original drift gives
Adding these equations yields
This is a self-financing strategy, and its nonnegative wealth makes it an admissible trading strategy. Continuity of the stock and local regularity of ensure local integrability of the holdings. The construction does not require .
For a classical solution, the usual Itô formula applies directly. The smooth fit solution below is and piecewise , with locally absolutely continuous first derivative. The generalized Itô formula applies with its almost-everywhere second derivative; the absence of a derivative jump means no boundary local time of a semimartingale term. This is the usual regularity interpretation of the perpetual American option obstacle equation.
Row operations multiply each original tableau equation by an invertible matrix. The slack variable block therefore records that matrix and allows the original payoff matrix to be recovered without guessing.
From the first tableau, let be the coefficient block of and that of . Since its original equations were , we have . Here
so
For the second tableau, writing its and blocks as , the original equations give . We obtain
Thus a representative pair of payoff matrices is
Both reconstructed right-hand sides are , as a check on the tableau normalization. Independent transformations , , with , preserve best responses and hence identify the same strategic solution up to positive affine payoff transformations.
Directly,
The supports of and lie entirely among their respective best-response coordinates, confirming the Nash equilibrium found above. Since this representative is a symmetric bimatrix game, swapping the players' strategies preserves the Nash equilibrium conditions. Explicitly, is maximized on the support of , and is maximized on the support of . Therefore
In the first tableau the basis is , giving
The second basis is , giving and . This pair is not yet a Nash equilibrium: label is missing and label is duplicated.
Resolve the duplicate by bringing into the second tableau. Its column is , so the simplex ratio test gives
Variable leaves, giving
Now label is duplicated. Bring into the first tableau; its column is . The positive-entry ratios are and . Thus leaves, giving
All labels are now present and . Each unnormalized strategy has total mass , so the Lemke-Howson algorithm produces
Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfying
Thus its two polytopes are and . A label occurs when or ; a label occurs when or . The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.
Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slackness
A nonzero completely labelled pair has both vectors nonzero: if , then forces , and the converse is analogous. Normalize to mixed strategies
The inequalities imply that every row payoff against is at most , with equality on every row receiving positive probability in . Thus is a best response to . Likewise is a best response to using . Hence is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.
For an explicit algorithm, keep an unnormalized residual , initially , whose row and column sums all equal a common mass , initially one. While , find a perfect matching in its positive support, form its permutation matrix , and subtract , where is the smallest selected entry. Record and replace by .
If the residual mass is positive, the same proof of the Hall marriage theorem condition applies after division by . Every subtraction removes at least one positive entry and creates no new positive entries. Before the last subtraction, any positive-mass residual has at least positive entries; the last step removes all its entries. If is the initial number of positive entries, then
Since the residual ultimately vanishes, summing the recorded subtractions gives , and the row sums give .
A perfect matching can be found by at most searches for an augmenting path in a matching, each costing in a graph with at most edges. Thus each iteration costs , including forming the support and updating the residual, and there are iterations. Hence
This bound uses exact real arithmetic. For rational input, a common denominator lets all residual subtractions be performed on integers of polynomial bit length, giving a polynomial bit-time implementation as well.
The preceding perfect matching gives a permutation matrix supported on the positive entries of . Let
If , every row's selected entry is one and all other entries vanish, so . Otherwise
is a doubly stochastic matrix with strictly fewer positive entries. Induct on the number of positive entries: the base case has exactly positive entries and is a permutation matrix. By induction, write as a convex combination. Then
is another convex combination, with nonnegative coefficients summing to one. Thus
This constructive proof of the Birkhoff-von Neumann theorem is Birkhoff decomposition by support matchings.
Form a bipartite graph with one vertex for each row and one for each column, putting an edge exactly where . For a set of row vertices, let be its neighbouring column vertices. Since is a doubly stochastic matrix,
The Hall marriage theorem therefore supplies a perfect matching. Its incidence entries define a permutation matrix supported on the positive entries of , hence on the ones of . Entrywise , so
The three-colourability problem belongs to NP: a colour assignment is a polynomial-length complexity certificate, and all edges can be checked in time.
For NP-hardness, reduce 3-SAT to the three-colourability problem. Start with a palette graph triangle with vertices . Its colours are necessarily distinct, and name them by these vertices. For each Boolean variable , add vertices , join them to each other, and join each to . The graph triangle is the forcing component of the Boolean-pair colouring gadget, so the two literal vertices receive opposite colours .
For each Boolean clause, attach a fresh copy of the three-colour clause gadget, identify its with the palette vertex , and identify its three input vertices with the Boolean clause's Boolean literal vertices. Copies share only palette or literal vertices. A Boolean clause with one or two Boolean literals is padded to three by repeating a literal; an empty Boolean clause can be mapped immediately to the uncolourable graph .
Any graph colouring with three colours gives a truth assignment by reading colour as true. The three-colour clause gadget forbids three false inputs, so every Boolean clause is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.
There are vertices for variables and nonempty padded clauses, and edges. The construction is a polynomial-time many-one reduction. Using the permitted NP-completeness of 3-SAT, we obtain
Name the upper graph triangle's vertices , where is adjacent to and to . Name the middle left vertex and the lower right vertex . Then is adjacent to , the lower graph triangle is , and is adjacent to .
Suppose all have colour , while has a different colour ; denote the third colour by . In the upper graph triangle, and cannot have colour and are adjacent, so they have colours in some order and has colour . In the lower graph triangle, is adjacent to both and , forcing to have colour , and then must have colour . But the edge now has equal-coloured endpoints, a contradiction. Thus
For the three-colour clause gadget used in a reduction, one also needs the converse extension property for Boolean-coloured inputs. With and , every tuple other than extends. If , take ; this works regardless of . If , take . Finally, if , take . Each assignment satisfies every edge. Therefore this three-colour clause gadget realizes exactly a three-input disjunction on Boolean inputs.
The displayed graph consists of three graph triangles sharing the vertex . In a graph colouring with three colours, every graph triangle uses all three colours. The edge and the edges therefore force to be the two colours different from . Likewise the graph triangle forces to be those same two colours. The third graph triangle imposes no further restriction on these four vertices. Hence
Both two-element sets and their union have cardinality two. This is a Boolean-pair colouring gadget: after fixing a palette graph triangle, the pair encodes opposite truth values.
Run breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.
If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The breadth-first search work is with adjacency lists. Therefore
This is also the two-colourability criterion for bipartite graphs.

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