Search

Consider a Markov process $\{\Phi(t) : t\geq 0\}$ evolving on a Polish space ${\sf X}$. A version of the $f$-Norm Ergodic Theorem is obtained: Suppose that the process is $\psi$-irreducible and aperiodic. For a given function $f\colon{\sf X}:\to[1,\infty)$, under suitable conditions on the process the following are equivalent: \begin{enumerate} \item[(i)] There is a unique invariant probability measure $\pi$ satisfying $\int f\,d\pi<\infty$. \item[(ii)] There is a closed set $C$ satisfying $\psi(C)>0$ that is ``self $f$-regular.'' \item There is a function $V\colon{\sf X} \to (0,\infty]$ that is finite on at least one point in ${\sf X}$, for which the following Lyapunov drift condition is satisfied, \[ {\cal D} V\leq - f+b\field{I}_C\, , \eqno{\hbox{(V3)}} \] where $C$ is a closed small set and ${\cal D}$ is the extended generator of the process. \end{enumerate} For discrete-time chains the result is well-known. Moreover, in that case, the ergodicity of $\bfPhi$ under a suitable norm is also obtained: For each initial condition $x\in{\sf X}$ satisfying $V(x)<\infty$, and any function $g\colon{\sf X}\to\Re$ for which $|g|$ is bounded by $f$, \[ \lim_{t\to\infty} {\sf E}_x[g(\Phi(t))] = \int g\,d\pi. \] Possible approaches are explored for establishing appropriate versions of corresponding results in continuous time, under appropriate assumptions on the process $\{\Phi(t)\}$ or on the function $g$.

The focus of this work is on the analysis of transmit beamforming schemes with a low-rate feedback link in wireless sensor/relay networks, where nodes in the network need to implement beamforming in a distributed manner. Specifically, the problem of distributed phase alignment is considered, where neither the transmitters nor the receiver has perfect channel state information, but there is a low-rate feedback link from the receiver to the transmitters. In this setting, a framework is proposed for systematically analyzing the performance of distributed beamforming schemes. To illustrate the advantage of this framework, a simple adaptive distributed beamforming scheme that was recently proposed by Mudambai et al. is studied. Two important properties for the received signal magnitude function are derived. Using these properties and the systematic framework, it is shown that the adaptive distributed beamforming scheme converges both in probability and in mean. Furthermore, it is established that the time required for the adaptive scheme to converge in mean scales linearly with respect to the number of sensor/relay nodes., Comment: 8 pages, 3 figures, presented partially at ITA '08 and PSU School of Info. Theory '08

We continue the investigation of the spectral theory and exponential asymptotics of Markov processes, following Kontoyiannis and Meyn (2003). We introduce a new family of nonlinear Lyapunov drift criteria, characterizing distinct subclasses of geometrically ergodic Markov processes in terms of inequalities for the nonlinear generator. We concentrate on the class of "multiplicatively regular" Markov processes, characterized via conditions similar to (but weaker than) those of Donsker-Varadhan. For any such process {Phi(t)} with transition kernel P on a general state space, the following are obtained. 1. SPECTRAL THEORY: For a large class of functionals F, the kernel Phat(x,dy) = e^{F(x)}P(x,dy) has a discrete spectrum in an appropriately defined Banach space. There exists a "maximal" solution to the "multiplicative Poisson equation," defined as the eigenvalue problem for Phat. Regularity properties are established for \Lambda(F) = \log(\lambda), where \lambda is the maximal eigenvalue, and for its convex dual. 2. MULTIPLICATIVE MEAN ERGODIC THEOREM: The normalized mean E_x[\exp(S_t)] of the exponential of the partial sums {S_t} of the process with respect to any one of the above functionals F, converges to the maximal eigenfunction. 3. MULTIPLICATIVE REGULARITY: The drift criterion under which our results are derived is equivalent to the existence of regeneration times with finite exponential moments for {S_t}. 4. LARGE DEVIATIONS: The sequence of empirical measures of {Phi(t)} satisfies an LDP in a topology finer than the \tau-topology. The rate function is \Lambda^* and it coincides with the Donsker-Varadhan rate function. 5. EXACTR LARGE DEVIATIONS: The partial sums {S_t} satisfy an exact LD expansion, analogous to that obtained for independent random variables., Comment: 63 pages

We give a development of the ODE method for the analysis of recursive algorithms described by a stochastic recursion. With variability modelled via an underlying Markov process, and under general assumptions, the following results are obtained: 1. Stability of an associated ODE implies that the stochastic recursion is stable in a strong sense when a gain parameter is small. 2. The range of gain-values is quantified through a spectral analysis of an associated linear operator, providing a non-local theory. 3. A second-order analysis shows precisely how variability leads to sensitivity of the algorithm with respect to the gain parameter. All results are obtained within the natural operator-theoretic framework of geometrically ergodic Markov processes., Comment: 19 pages, 4 figures