Asian barrier options are barrier options whose trigger is based on an average underlying price. They provide the advantages of both Asian options and barrier options. This paper introduces the first quadratic-time lattice algorithm to price European-style Asian barrier options. It is by far the most efficient lattice algorithm with convergence guarantees. The algorithm relies on the Lagrange multipliers to optimally distribute the number of states for each node of the multinomial lattice. We also show experiment results to demonstrate effectiveness and efficiency of our algorithm by comparing with Monte Carlo simulations.

With the rapid growth of financial markets, many complex derivatives have been structured to meet specific financial goals. But most complex derivatives have no analytical formulas for their prices, e.g., when more than one market variable is factored. As a result, they must be priced by numerical methods such as lattice. A derivative is called multivariate if its value depends on more than one market variable. A lattice for a multivariate derivative is called a multivariate lattice. This paper proposes a flexible multi-phase method to build a multivariate lattice for pricing derivatives accurately. First, the original, correlated processes are transformed into uncorrelated ones by the orthogonalization method. A multivariate lattice is then constructed for the transformed, uncorrelated processes. To sharply reduce the nonlinearity error of many numerical pricing methods, our lattice has the flexibility to match the so-called “critical locations” - the locations where nonlinearity of the derivative's value function occurs. Numerical results for vulnerable options, insurance contracts guaranteed minimum withdrawal benefit, and defaultable bonds show that our methodology can be applied to the pricing of a wide range of complex financial contracts.

The geometric average trigger reset option resets the strike price based on the geometric average of the underlying asset's prices over a monitoring window. This paper derives an analytic formula and two numerical methods for pricing this option with multiple resets. The analytic formula in fact is a corollary of a general formula that holds for a large class of path-dependent options: It prices any option whose payoff function can be written as e/sup b/spl middot/X/1/sub {X/spl isin/A}/. For general American-style reset options, an O(n/sup 4/h/sup 2/)-time algorithm on n-period binomial lattice is presented. A much more efficient O(n/sup 3/ hm)-time algorithm prices European-style reset options. Monte Carlo simulation suggests that the European-style geometric average trigger reset option and the arithmetic version have similar option values. This implies that results in this paper give tight prices for the difficult arithmetic version.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

Communication plays a key role in the overall performance of a parallel system. In the general case, the communication network is required to transfer information from any set of sources to to any set of destinations. In practice, parallel applications have various communication needs. Many applications restrict their communication requests to a more limited number of possible connections between sources and destinations. The communication requests of parallel applications are represented by graphs. Parallel graph contraction has been used to embed these graphs into a reconfigurable parallel architecture. We review some of the previous work done in this area showing how various useful communication graphs (e.g., ring, kary trees, mesh, CCC, hypercube, etc.), can be contracted for an efficient embedding. We also present some results for the parallel contraction of other useful graphs such as de Bruijn, shuffle-exchange, mesh of trees, pyramid, and multi-stage communication structures. Lower bounds are proved for all graphs. A heuristic approach for parallel graph contraction is reviewed for irregular graphs based on simulated annealing.

Abstract In this paper, the space‐efficient Information Dispersal Algorithm (IDA) is applied to fault‐tolerant parallel communication in the de Bruijn andd‐way digit‐exchange networks, which is a generalized butterfly (Omega) network. LetN=dndenote the size of the de Bruijn network. Our routing scheme runs in 2n+ 1 time using constant size buffers (if the routing information is not counted). Ford= [nInn], it probability of successful routing is at least 1 −N−InN/2. The scheme also toleratesO(N)random link failures with probability at least 1 −N(7−InInn)/6. We also propose a routing scheme for the d‐way digit‐exchange network such that similar bounds hold. Both schemes run within the said time bounds without queuing delay. ©1993 by John Wiley & Sons, Inc.

A graph has spread (m, k, l) if for any m+1 distinct nodes x, y/sub 1/, . . ., y/sub m/ and m positive integers r/sub 1/, . . ., r/sub m/, such that Sigma /sub i/r/sub i/=k, there exist k node-disjoint paths of length at most 1 from x to the y/sub i/, where r/sub i/ of them end at y/sub i/. This concept contains, and is related to many important concepts used in communications and graph theory. The authors prove an optimal general theorem about the spreads of digraphs generated by line digraph iterations. Useful graphs, like the de Bruijn and Kautz digraphs, can be thus generated. The theorem is applied to the de Bruijn and Kautz digraphs to derive optimal bounds on their spreads, which implies previous results and resolves open questions on their connectivity, diameter, k-diameter, vulnerability, and some other measures related to length-bound disjoint paths.>

“Sudden” transition to perfect generalization in binary perceptrons is investigated. Building on recent theoretical works of Gardner and Derrida (1989) and Baum and Lyuu (1991), we show the following: for α > αc = 1.44797 …, if α n examples are drawn from the uniform distribution on {+1, −1}n and classified according to a target perceptron wt ∈ {+1, −1}n as positive if wt · x ≥ 0 and negative otherwise, then the expected number of nontarget perceptrons consistent with the examples is 2−⊖(√n); the same number, however, grows exponentially 2⊖(n) if α ≤ αc. Numerical calculations for n up to 1,000,002 are reported.

Several recent papers (Gardner and Derrida 1989; Györgyi 1990; Sompolinsky et al. 1990) have found, using methods of statistical physics, that a transition to perfect generalization occurs in training a simple perceptron whose weights can only take values ±1. We give a rigorous proof of such a phenomena. That is, we show, for α = 2.0821, that if at least αn examples are drawn from the uniform distribution on {+1, −1} n and classified according to a target perceptron w t ∈ {+1, −1} n as positive or negative according to whether w t ·x is nonnegative or negative, then the probability is 2 −(√n) that there is any other such perceptron consistent with the examples. Numerical results indicate further that perfect generalization holds for α as low as 1.5.

Article Free Access Share on Fast-fault-tolerant parallel communication and on-line maintenance using information dispersal Author: Y.-D. Lyuu Aiken Computation Laboratory, Harvard University, Cambridge, MA Aiken Computation Laboratory, Harvard University, Cambridge, MAView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 378–387https://doi.org/10.1145/97444.97705Published:01 May 1990Publication History 9citation243DownloadsMetricsTotal Citations9Total Downloads243Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF