Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGrowth rate for the expected value of a generalized random Fibonacci sequence
218
0
0.0
(
0
)
Authors
Elise Janvresse
Ask ChatGPT about the research
No Arabic abstract
A random Fibonacci sequence is defined by the relation g_n = | g_{n-1} +/- g_{n-2} |, where the +/- sign is chosen by tossing a balanced coin for each n. We generalize these sequences to the case when the coin is unbalanced (denoting by p the probability of a +), and the recurrence relation is of the form g_n = |lambda g_{n-1} +/- g_{n-2} |. When lambda >=2 and 0 < p <= 1, we prove that the expected value of g_n grows exponentially fast. When lambda = lambda_k = 2 cos(pi/k) for some fixed integer k>2, we show that the expected value of g_n grows exponentially fast for p>(2-lambda_k)/4 and give an algebraic expression for the growth rate. The involved methods extend (and correct) those introduced in a previous paper by the second author.
rate research
Read More
We study the generalized random Fibonacci sequences defined by their first nonnegative terms and for $nge 1$, $F_{n+2} = lambda F_{n+1} pm F_{n}$ (linear case) and $widetilde F_{n+2} = |lambda widetilde F_{n+1} pm widetilde F_{n}|$ (non-linear case), where each $pm$ sign is independent and either $+$ with probability $p$ or $-$ with probability $1-p$ ($0<ple 1$). Our main result is that, when $lambda$ is of the form $lambda_k = 2cos (pi/k)$ for some integer $kge 3$, the exponential growth of $F_n$ for $0<ple 1$, and of $widetilde F_{n}$ for $1/k < ple 1$, is almost surely positive and given by $$ int_0^infty log x d u_{k, rho} (x), $$ where $rho$ is an explicit function of $p$ depending on the case we consider, taking values in $[0, 1]$, and $ u_{k, rho}$ is an explicit probability distribution on $RR_+$ defined inductively on generalized Stern-Brocot intervals. We also provide an integral formula for $0<ple 1$ in the easier case $lambdage 2$. Finally, we study the variations of the exponent as a function of $p$.
We study two kinds of random Fibonacci sequences defined by $F_1=F_2=1$ and for $nge 1$, $F_{n+2} = F_{n+1} pm F_{n}$ (linear case) or $F_{n+2} = |F_{n+1} pm F_{n}|$ (non-linear case), where each sign is independent and either + with probability $p$ or - with probability $1-p$ ($0<ple 1$). Our main result is that the exponential growth of $F_n$ for $0<ple 1$ (linear case) or for $1/3le ple 1$ (non-linear case) is almost surely given by $$int_0^infty log x d u_alpha (x), $$ where $alpha$ is an explicit function of $p$ depending on the case we consider, and $ u_alpha$ is an explicit probability distribution on $RR_+$ defined inductively on Stern-Brocot intervals. In the non-linear case, the largest Lyapunov exponent is not an analytic function of $p$, since we prove that it is equal to zero for $0<ple1/3$. We also give some results about the variations of the largest Lyapunov exponent, and provide a formula for its derivative.
We consider the problem of numerically evaluating the expected value of a smooth bounded function of a chi-distributed random variable, divided by the square root of the number of degrees of freedom. This problem arises in the contexts of simultaneous inference, the selection and ranking of populations and in the evaluation of multivariate t probabilities. It also arises in the assessment of the coverage probability and expected volume properties of the some non-standard confidence regions. We use a transformation put forward by Mori, followed by the application of the trapezoidal rule. This rule has the remarkable property that, for suitable integrands, it is exponentially convergent. We use it to create a nested sequence of quadrature rules, for the estimation of the approximation error, so that previous evaluations of the integrand are not wasted. The application of the trapezoidal rule requires the approximation of an infinite sum by a finite sum. We provide a new easily computed upper bound on the error of this approximation. Our overall conclusion is that this method is a very suitable candidate for the computation of the coverage and expected volume properties of non-standard confidence regions.
We call $i$ a fixed point of a given sequence if the value of that sequence at the $i$-th position coincides with $i$. Here, we enumerate fixed points in the class of restricted growth sequences. The counting process is conducted by calculation of generating functions and leveraging a probabilistic sampling method.
A t by n random matrix A is formed by sampling n independent random column vectors, each containing t components. The random Gram matrix of size n, G_n, contains the dot products between all pairs of column vectors in the randomly generated matrix A; that is, G_n = transpose(A) A. The matrix G_n has characteristic roots coinciding with the singular values of A. Furthermore, the sequences det(G_i) and per(G_i) (for i = 0, 1, ..., n) are factors that comprise the expected coefficients of the characteristic and permanental polynomials of G_n. We prove theorems that relate the generating functions and recursions for the traces of matrix powers, expected characteristic coefficients, expected determinants E(det(G_n)), and expected permanents E(per(G_n)) in terms of each other. Using the derived recursions, we exhibit the efficient computation of the expected determinant and expected permanent of a random Gram matrix G_n, formed according to any underlying distribution. These theoretical results may be used both to speed up numerical algorithms and to investigate the numerical properties of the expected characteristic and permanental coefficients of any matrix comprised of independently sampled columns.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
