Search results for "Logarithm"
showing 10 items of 182 documents
Analytic Extension of Non Quasi - Analytic Whitney Jets of Beurling Type
1998
Let (Mr)r∈ℕ0 be a logarithmically convex sequence of positive numbers which verifies M0 = 1 as well as Mr ≥ 1 for every r ∈ ℕ and defines a non quasi - analytic class. Let moreover F be a closed proper subset of ℝn. Then for every function f on ℝn belonging to the non quasi - analytic (Mr)-class of Beurling type, there is an element g of the same class which is analytic on ℝ,nF and such that Dαf(x) = Dαg(x) for every α ∈ ℕn0 and x ∈ F.
Lower space bounds for randomized computation
1994
It is a fundamental problem in the randomized computation how to separate different randomized time or randomized space classes (c.f., e.g., [KV87, KV88]). We have separated randomized space classes below log n in [FK94]. Now we have succeeded to separate small randomized time classes for multi-tape 2-way Turing machines. Surprisingly, these “small” bounds are of type n+f(n) with f(n) not exceeding linear functions. This new approach to “sublinear” time complexity is a natural counterpart to sublinear space complexity. The latter was introduced by considering the input tape and the work tape as separate devices and distinguishing between the space used for processing information and the spa…
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
2005
A language L over an alphabet A is said to have a neutral letter if there is a letter [email protected]?A such that inserting or deleting e's from any word in A^* does not change its membership or non-membership in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach …
Application of kolmogorov complexity to inductive inference with limited memory
1995
A b s t r a c t . We consider inductive inference with limited memory[l]. We show that there exists a set U of total recursive functions such that U can be learned with linear long-term memory (and no short-term memory); U can be learned with logarithmic long-term memory (and some amount of short-term memory); if U is learned with sublinear long-term memory, then the short-term memory exceeds arbitrary recursive function. Thus an open problem posed by Freivalds, Kinber and Smith[l] is solved. To prove our result, we use Kolmogorov complexity.
Law of the Iterated Logarithm
2020
For sums of independent random variables we already know two limit theorems: the law of large numbers and the central limit theorem. The law of large numbers describes for large \(n\in \mathbb{N}\) the typical behavior, or average value behavior, of sums of n random variables. On the other hand, the central limit theorem quantifies the typical fluctuations about this average value.
Quasihyperbolic boundary conditions and Poincaré domains
2002
We prove that a domain in ${\Bbb R}^n$ whose quasihyperbolic metric satisfies a logarithmic growth condition with coefficient $\beta\le 1$ is a (q,p)-\Poincare domain for all p and q satisfying $p\in[1,\infty)\cap(n-n\beta,n)$ and $q\in[p,\beta p^*)$ , where $p^*=np/(n-p)$ denotes the Sobolev conjugate exponent. An elementary example shows that the given ranges for p and q are sharp. The proof makes use of estimates for a variational capacity. When p=2 we give an application to the solvability of the Neumann problem on domains with irregular boundaries. We also discuss the relationship between this growth condition on the quasihyperbolic metric and the s-John condition.
Spatial Search on Grids with Minimum Memory
2015
We study quantum algorithms for spatial search on finite dimensional grids. Patel et al. and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.
Uncountable Realtime Probabilistic Classes
2018
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.
Assessing fat-tailed sequential forecast distributions for the Dow-Jones index with logarithmic scoring rules
2007
We use the logarithmic scoring rule for distributions to assess a variety of fat-tailed sequential forecasting distributions for the Dow-Jones industrial stock index from 1980 to the present. The methodology applies Bruno de Finetti''s contributions to understanding how to compare the quality of different coherent forecasting distributions for the same sequence of observations, using proper scoring rules. Four different forms of forecasting distributions are compared: a mixture Normal, a mixture of convex combinations of three Normal distributions, a mixture exponential power distribution, and a mixture of a convex combination of three exponential power distributions. The mixture linear com…
Multiplicity in financial equilibrium with portfolio constrains under the generalized logarithmic utility model
2012
Previous research on the effects of constraints to take unbounded positions in risky financial assets shows that, under the logarithmic utility function, multiplicity of equilibrium may emerge. This paper shows that this result is robust to either constant, decreasing or increasing relative risk aversion obtained under the generalized logarithmic utility function.