Self-similar random measures are locally scale invariant

Summary In an earlier paper Patzschke and U. Zähle [11] have proved the existence of a fractional tangent measure at the typical point of a self-similar random measure under rather special technical assumptions. In the present paper we remove the most restrictive one. Here we suppose the open set condition for the similarities, a constant positive lower bound for the random contraction ratios, and vanishing on the boundary of the open set with probability 1. The tangent measure isD-scale-invariant, whereD is the similarity dimension of . Moreover, we approximate the tangential distribution by means of and use this in order to prove that the Hausdorff dimension of the tangent measure equalsD. Since the former coincides with the Hausdorff dimension of we obtain an earlier result of Mauldin and Williams [9] as a corollary.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

The Terwilliger algebras of certain association schemes over the Galois rings of characteristic 4

In a cyclotomic scheme over a finite field, there are some relations between the irreducible modules of the Terwilliger algebra and the Jacobi sums over the field. These relations were investigated in [3]. In this paper, we replace the finite field by a commutative local ring which is called a Galois ring of characteristic 4. Hence we want to find similar relations between the irreducible modules of the Terwilliger algebra and the Jacobi sums over the local ring. Specifically, if we let be a Galois ring of characteristic 4,X a cyclotomic scheme over with classD and the Terwilliger algebra ofX, then we show that most of the irreducible -modules have standard forms; otherwise, certain relations of the Jacobi sums hold. When the classD is three, we can completely determine the irreducible -modules using Jacobi sums.     

On the abstract Cauchy problem for the operator\frac{{d^2 }}{{dt^2 }} - A.

LetX be a Banach space, A a closed operator with dense domainD(A) and non-void resolvent set; topologized by the semi-norm system. We prove that the Cauchy problem is well posed in the sense of distributions for the operator d²/dt²–A if and only if A restricted toD generates a locally — equicontinuous cosine function of class C inL _S D . This is an extension of Ushijima's smoothness result of distribution semi-groups [10].     

Diffusions réfléchies réversibles dégénérées

On a domain D in ^d, for a smooth enough probability density and a diffusion matrix which can degenerate, we construct the law Q ^s of a (x)d -symmetric reflecting process in D with matrix . Therefore, we use the associated Dirichlet form and a sequence of approximating processes already used by Pardoux and R. Williams in [23]. Under mild conditions on the boundary ofD (finite Minkowski content), we prove that Q ^s is the law of a semi-martingale and provide its decomposition. Comparing with the decomposition in additive functionals, we conclude that the process is reflected in the conormal direction ^* n where n denotes Chen's normal (cf [10]), that is, the reflection direction of the Brownian motion in Kuramochi compactification.     

Comments on Harn–Lin’s cheating detection scheme

Detection of cheating and identification of cheaters in threshold schemes has been well studied, and several solid solutions have been provided in the literature. This paper analyses Harn and Lin’s recent work on cheating detection and identification of cheaters in Shamir’s threshold scheme. We will show that, in a broad area, Harn–Lin’s scheme fails to detect cheating and even if the cheating is detected cannot identify the cheaters. In particular, in a typical Shamir (t, n)-threshold scheme, where n = 2t − 1 and up to t − 1 of participants are corrupted, their scheme neither can detect nor can identify the cheaters. Moreover, for moderate size of groups their proposed cheaters identification scheme is not practical.     

Isotropic Gauss-Markov currents

Summary A natural definition of the Markov property for multi-parameter random processes (random fields) is the following. Let {X _t,t ^N } be a multiparameter process. For any set D in ^N let _D denote the -field generated by {X _t , tD}. The field {X _t,tD} is said to be Markov (or Markov of degree 1 [6], or sharp Markov) if, for any bounded open set D with smooth boundary, _D and _D ^c are conditionally independent given _D . It has been known for some time that to find interesting examples of Markov processes under this definition; it is necessary to consider generalized random functions. In this paper we show that a natural framework for the Markov property of multiparameter processes is a class of generalized random differential forms (i.e., random currents). Our principal objective is to relate the Markovian nature of an isotropic gaussian current to its spectral properties.Work supported by the Army Research Office, Grant No. DAAG 29-85-K-0233Work done while at the University of California at Berkeley     

Orbifold index and equivariant <Emphasis Type="Italic">K</Emphasis>-homology

Let G be countable group and M be a proper cocompact even-dimensional G-manifold with orbifold quotient . Let D be a G-invariant Dirac operator on M. It induces an equivariant K-homology class and an orbifold Dirac operator on . Composing the assembly map with the homomorphism given by the representation of the maximal group C ^*-algebra induced from the trivial representation of G we define index . In the second section of the paper we show that index = index([D]) and obtain explicit formulas for this integer. In the third section we review the decomposition of in terms of the contributions of fixed point sets of finite cyclic subgroups of G obtained by W. Lück. In particular, the class [D] decomposes in this way. In the last section we derive an explicit formula for the contribution to [D] associated to a finite cyclic subgroup of G.     

Paths and cycles concerning independent edges

R. Häggkvist and C. Thomassen defined admissible paths in [5] which is a generalization of alternating paths. A path or a cycleD is said to beadmissible for a setL of pairwise independent edges if each edge ofL lies onD or has no vertex in common withD. For given two distinct verticesa andb, and a given setL of independent edges inG, we establish a necessary and sufficient condition for the existence of an admissible path forL connectinga andb inG. This theorem is analogous to Tutte's Theorem of Alternating Connection [14]. Futhermore we show a 2-connected version of this theorem which does not seem to have any analogue in the theory of alternating path. As a corollary of this theorem, we prove the 1-factor theorem. We conjecture that for a setL of given independent edges, |L| n, in ann-connected graphG, with very few exceptionsG has an admissible cycleC forL such thatC contains at leastn edges ofL. Using our results concerning admissible paths, we also prove this conjecture in the cases wheren = 2 and 3. Furthermore, we show how our results are applied to problems of alternating paths. As a final application, we prove that ifG is a 3-regular graph with a Hamiltonian cycleH, then for any edgee E(H), there exists an admissible cycle forE(G) — E(H) inG through the edgee.     

State-Homomorphisms on MV-Algebras

Riecan [12] and Chovanec [1] investigated states in MV-algebras. Earlier, Riecan [11] had dealt with analogous ideas in D-posets. In the monograph of Riecan and Neubrunn [13] (Chapter 9) the notion of state is applied in the theory of probability on MV-algebras. We remark that a different definition of a state in an MV-algebra has been applied by Mundici [9], [10] (namely, the condition (iii) from Definition 1.1 above was not included in his definition of a state; in other words, only finite additivity was assumed). Below we work with the definition from [13]; but, in order to avoid terminological problems we use the term "state-homomorphism" (instead of "state"). The author is indebted to the referee for his suggestion concerning terminology. Let be an MV-algebra which is defined on a set A with card A>1. In the present paper we show that there exists a one-to-one correspondence between the system of all state-homomorphisms on and the system of all -closed maximal ideals of . For MV-algebras we apply the notation and the definitions as in Gluschankof [3]. The relations between MV-algebras and abelian lattice ordered groups (cf. Mundici [8]) are substantially used in the present paper.     

Minimization of the Conformal Radius under Circular Cutting of a Domain

Let D be a simply connected domain on the complex plane such that 0 D. For r > 0 , let D _r be the connected component of D {z : |z| < r} containing the origin. For fixed r, we solve the problem on minimization of the conformal radius R(D _r, 0) among all domains D with given conformal radius R(D, 0). This also leads to the solution of the problem on maximization of the logarithmic capacity of the local -extension E (a) of E among all continua E with given logarithmic capacity. Here, E (a) = E {z : |z – a| }, a E, > 0. Bibliography: 12 titles.     

über straffe Wahrscheinlichkeitsverteilungen im Raum der Schwartzschen Distributionen

Zusammenfassung In den letzten Jahren erschien eine Reihe von Arbeiten, die sich systematisch mit Wahrscheinlichkeitsverteilungen auf topologischen Gruppen, Halbgruppen, topologischen RÄumen und topologischen linearen RÄumen beschÄftigten. Als besonders geeignet für eine topologische Wahrscheinlichkeitstheorie erwiesen sich hierbei die sogenannten straffen (tight) Wahrscheinlichkeitsverteilungen (vgl. Le Cam [3], Hildenbrand [11], Prochoeov [20], Varadarajan [25]).Die vorliegende Arbeit befa\t sich mit straffen Wahrscheinlichkeitsverteilungen im Raum D, dem topologischen Dualraum des Raumes D der auf der reellen Zahlengeraden definierten beliebig oft differenzierbaren Funktionen mit kompaktem TrÄger Tr .Der Ausgangspunkt für die Untersuchung von Zufallselementen mit Werten in linearen RÄumen, die nicht notwendig BanachrÄume sind, war wohl der von GELFAND [8] eingeführte Begriff des verallgemeinerten stochastischen Prozesses (VSP). Solange man bei einem solchen Proze\ Eigenschaften untersucht, die sich mit Hilfe seiner endlichdimensionalen Randverteilungen Q_{1,...,n}, _i D, beschreiben lassen, wird man sich wie im Fall eines gewöhnlichen stochastischen Prozesses natürlich die Frage stellen, ob ein geeigneter Standard-stichprobenraum existiert, etwa der Raum D, so da\ sich jeder VSP auffassen lÄ\t als Wahrscheinlichkeitsverteilung auf einem geeigneten hinreichend umfangreichen -Ring von Teilmengen des Raumes D. Die fundamentale Arbeit von MINLOS [18] gab hierzu die Lösung: Durch ein vertrÄgliches System endlichdimensionaler Wahrscheinlichkeitsverteilungen Q_{1,...,n}, _i D, mit gewissen Eigenschaften, die denen der Randverteilungen eines VSP entsprechen, lÄ\t sich auf dem SystemB der Zylindermengen des Raumes D eine sogenannte schwache Verteilung definieren, von der gezeigt wird, da\ sie -additiv ist. Durch EinschrÄnkung des Raumes der sogenannten Testfunktionen auf den metrisierbaren Teilraum D _K{ D:Tr K, K kompakt in } von D lÄ\t sich dieses Ergebnis wie folgt verschÄrfen: Die durch ein vertrÄgliches System endlichdimensionaler Randverteilungen Q_{1,...,n}, _i D, mit entsprechenden Eigenschaften, auf dem System B _K der Zylindermengen des Raumes D_K definierte schwache Verteilung K ist straff bezüglich der schwachen Topologie (D_K, D_K) in D_K.Die Frage nach der Gültigkeit einer entsprechenden VerschÄrfung für das Dualsystem >DD<, bzw. allgemeiner für ein Dualsystem E, F mit nicht notwendig metrisierbarem F, bildete den Gegenstand neuerer Untersuchungen, über deren Ergebnisse auf dem letzten Berkeley Symposium E. Mourier berichtete (vgl. [19]).Im ersten Kapitel der vorliegenden Arbeit des Verfassers wird demgegenüber eine Methode aufgezeigt, mit deren Hilfe, unter Verwendung des Minlosschen Satzes in seiner ursprünglichen Form, auf direktem Wege für das Dualsystem >D, D< der Nachweis gelingt, da\ eine schwache Verteilung auf B nicht nur -additiv, sondern automatisch straff ist (bzgl. der schwachen Topologie (D, D) in D) und sich somit eindeutig fortsetzen lÄ\t zu einer straffen Wahrscheinlichkeitsverteilung auf dem System 83 der Boreischen Mengen in D, welches den von den Zylindermengen erzeugten -Ring (B) umfa\t. Mit anderen Worten wird damit gezeigt, da\ man jeden VSP auffassen kann als straffe Wahrscheinlichkeitsverteilung auf den Boreischen Mengen in D. Wir sprechen dann auch von einer zufÄlligen Distribution.Im zweiten Kapitel betrachten wir spezielle zufÄllige Distributionen, nÄmlich Normal-verteilungen v, die aus Randverteilungen hervorgehen, welche n-dimensionale Normal-verteilungen sind, und beschÄftigen uns mit dem Problem der Äquivalenz und SingularitÄtzweier Normalverteilungen v₁ und v₂ in D. Für den Fall v₁ = v, v₂= v_{f 0}, wo v_{f 0}(Z) =v(Z – f₀), ZB fD, zeigte DUDLEY [6], da\ entweder Äquivalenz oder SingularitÄt vorliegt, wobei er ein notwendiges und hinreichendes Kriterium für den Fall der Äquivalenz angibt. Aus der Theorie der gewöhnlichen stochastischen Prozesse ist nun bekannt, da\ die beiden Wahrschein-lichkeitsma\e, die zwei beliebigen Gau\schen Prozessen auf dem Raum ihrer Realisierungen entsprechen, entweder Äquivalent oder singular sind. Es lag deshalb nahe, nach einem Kriterium zu suchen, welches es einerseits gestattet, im Fall zweier beliebiger Normalverteilungen v₁ und v₂ in D zu entscheiden, wann Äquivalenz vorliegt, und welches andererseits die naheliegende Vermutung bestÄtigt, da\ für zwei Normalverteilungen in D dieselbe Alternative wie im eben zitierten klassischen Fall vorliegt. Dieses Problem wird gelöst, indem wir zeigen, da\ sich ein von Kallianfur-Oodaira [13] aufgestelltes Kriterium für die Äquivalenz zweier Normalverteilungen auf den Boreischen Mengen eines separablen Hilbertraumes auf den Distributionsraum D übertragen lÄ\t.Im dritten Kapitel beschÄftigen wir uns mit der Frage der Äquivalenz zweier beliebiger (nicht notwendig normaler) Wahrscheinlichkeitsverteilungen in D.Abschlie\end möchte der Autor Herrn Professor Dr. K. Krickeberg (Heidelberg) für die Anregung zu dieser Arbeit sowie für die Unterstützung wÄhrend ihrer Durchführung herzlich danken.     

Positive Solutions of Nonlinear Elliptic Equations in Unbounded Domains in R 2

We study the existence of positive solutions of the nonlinear equation u+f(,u)=0, in D with u=0 on D, where D is an unbounded domain in R ² with a compact nonempty boundary D consisting of finitely many Jordan curves. The aim is to prove an existence result for the above equation in a general setting by using potential theory.     

On Fine Limits and Curving-Shaped Limits

This paper studies the boundary behavior of the so-called SIH-functions, i.e., the functions satisfying the scale invariant Harnack inequality on a domain D R^N (N 2). Suppose that D contains a curving-cone at a point D and u is a SIH-function on D. Then u has a curving-shaped limit L at , if u has a -fine limit (especially, a p-fine limit in the sense of [6] or an -fine limit in the sense of the Riesz potential theory [4]) L at .AMS Subject Classification (2000): 31B25, 31C15, 30C65     

Elations and symmetric designs having projective subspaces

Consider symmetric 2-designs D which have an automorphism group G containing sufficiently many elations. This paper investigates the case where there are the least number of elations. Under certain assumptions it is shown that D has a projective subspace and in a particular case D _n,q or D is obtained from _n,q by a process called K-alteration.The results in this paper form part of a PhD thesis submitted by the author to the University of London. The author gratefully acknowledges the support of the Commonwealth Scholarship Commission.     

Boundary Functionals for the Difference of Nonordinary Renewal Processes with Discrete Time

For the difference of nonordinary renewal processes, we find the distribution of the main boundary functionals. For the queuing system D |D |1, we determine the distribution of the number of calls in transient and stationary modes.     

Error estimates over infinite intervals of some discretizations of evolution equations

Classical discretization error estimates for systems of ordinary differential equations contain a factor exp (Lt), whereL is the Lipschitz constant. For strongly monotone operators, however, one may prove that for a-method, 0<<1/2, the errors are bounded uniformly in time and with errorO(t)², if=1/2–|O(t)|. This was done by this author (1977), for an operator in a reflexive Banach space and includes the case of systems of differential equations as a special case.In the present paper we restate this result as it may have been overlooked and consider also the monotone (inclusive of the conservative) and unbounded cases. We also discuss cases where the truncation errors are bounded by a constant independent of the stiffness of the problem. This extends previous results in [6] and [7]. Finally we discuss a boundary value technique in the context above.Dedicated to Germund Dahlquist: a stimulating teacher and researcher     

Exit probabilities and optimal stochastic control

This paper is concerned with Markov diffusion processes which obey stochastic differential equations depending on a small parameter. The parameter enters as a coefficient in the noise term of the stochastic differential equation. The Ventcel-Freidlin estimates give asymptotic formulas (as0) for such quantities as the probability of exit from a regionD through a given portionN of the boundary D, the mean exit time, and the probability of exit by a given timeT. A new method to obtain such estimates is given, using ideas from stochastic control theory.This research was supported by the Air Force Office of Scientific Research under AF-AFOSR 76-3063, and in part by the National Science Foundation under NSF-MCS 76-37247.     

Existence of global invariant jet differentials on projective hypersurfaces of high degree

Let be a smooth complex projective hypersurface. In this paper we show that, if the degree of X is large enough, then there exist global sections of the bundle of invariant jet differentials of order n on X, vanishing on an ample divisor. We also prove a logarithmic version, effective in low dimension, for the log-pair , where D is a smooth irreducible divisor of high degree. Moreover, these result are sharp, i.e. one cannot have such jet differentials of order less than n.     

On the dynamization of data structures

In this paper we present a simple dynamization method that preserves the query and storage costs of a static data structure and ensures reasonable update costs. In this method, the majority of data elements are maintained in a single data structure, and the updates are handled using smaller auxiliary data structures. We analyze the query, storage, and amortized update costs for the dynamic version of a static data structure in terms of a functionf, such thatf(n)<n, that bounds the sizes of the auxiliary data structures (wheren is the number of elements in the data structure). The conditions onf for minimal (with respect to asymptotic upper bounds) amortized update costs are then obtained. The proposed method is shown to be particularly suited for the cases where the merging of two data structures is more efficient than building the resultant data structure from scratch. Its effectiveness is illustrated by applying it to a class of data structures that have linear merging cost; this class consists of data structures such as Voronoi diagrams, K-d trees, quadtrees, multiple attribute trees, etc.