Archive

Archive for the ‘Probability Theory’ Category

Malliavin-Stein Method for Muti-dimensional U-statistics of Poisson point processes

November 17, 2011 Leave a comment

Here is my new manuscript submitted to ARXIV [math.PR]. The preprint version can be found here.

 

MALLIAVIN-STEIN METHOD FOR MULTI-DIMENSIONAL
U-STATISTICS OF POISSON POINT PROCESSES

 

Abstract. In this paper, we give an upper bound for a probabilistic distance between a Gaussian vector and a vector of U-statistics of Poisson point processes by applying Malliavin-Stein inequality on the Poisson space.

I – Introduction

The theory of Malliavin calculus on the Poisson space was firstly studied by Nualart and Vives in their excellent paper of Strasbourg’s seminars [Nualart1990]. For some important contributions and applications for Poisson point processes, we refer to [Houdre1995, Wu2000, Peccati2011, Last2011]. The combination of Stein’s method and Malliavin calculus on the Poisson space related to the normal approximations of Poisson functionals has been considered by Peccati, Solé, Taqqu, Utzet and Zheng in their recent papers [Peccati2010a, Peccati2010b].

The basic theory of U-statistics was introduced by Hoeffding [Hoeffding1948] as a class of statistics that is especially important in estimation theory. Further applications are widely regarded in theory of random graphs, spatial statistics, theory of communication and stochastic geometry, see e.g. [Lee1990, Koroljuk1994, Borovskikh1996].

Recently, the idea of central limit theorems for U-statistics of Poisson point processes by using Malliavin calculus and Stein’s method has been given by Reitzner and Schulte in [Reitzner2011]. Our main work in the current paper is to extend their results to vectors of U-statistics by applying the muti-dimensional Malliavin-Stein inequality, that was proved by Peccati and Zheng in [Peccati2010b]. Some preliminaries of Malliavin calculus on the Poisson space and U-statistic will be introduced in Section 2. An upper bound for a probabilistic distance between a Gaussian vector and a square integrable random variable with finite Wiener-Itô chaos expansions will be shown in Section 3 and its application for multi-dimensional U-statistics of Poisson point processes will be given in Section 4.

II – Malliavin Calculus on the Poisson space

Let (E, \mathcal A, \mu) be some measure space with \sigma-finite measure \mu. The Poisson point process or Poisson measure with intensity measure \mu is a family of random variables \{{N}(A)\}_{A\in\mathcal{A}} defined on some probability space (\Omega, \mathcal F, \mathrm{P}) such that
1. \forall A\in\mathcal{A}, N(A) is a Poisson random variable with rate \mu(A).
2. If sets A_1,A_2,\ldots,A_n\in\mathcal{A} don’t intersect then the corresponding random variables {N}(.) from i) are mutually independent.
3. \forall\omega\in\Omega, {N}(.,\omega) is a measure on (E, \mathcal A).

Note that, for some \sigma-finite measure space (E, \mathcal A, \mu), we can always set

\Omega=\{\omega =\sum_{j=1}^n\delta_{z_j}, \ n\in\mathbb{N}\cup\{\infty\}, z_j\in E \},

where \delta_z denotes the Dirac mass at z, and for each A\in \mathcal{A}, we give the mapping {N} such that

\omega\mapsto {N}(A,\omega)=\omega(A).

Moreover, the \sigma-field \mathcal{F} is supposed to be the \text{P}-completion of the \sigma-field generated by {N}.

Let \mathcal{M}(E) denote the space of all integer-valued \sigma-finite measures on E, which can be equipped with the smallest \sigma-algebra \Sigma such that for each A\in\mathcal{A} then the mapping \eta\in\mathcal{M}(E)\mapsto \eta(A) is measurable. We can give on (\mathcal{M}(E),\Sigma) the probability measure P_{N} induced by the Poisson measure N and denote L^p(P_{N}) as the set of all measurable functions F:\mathcal{M}(E)\to \overline{\mathbb R} such that \mathbf{E}[|F|^p]<\infty, where the expectation takes w.r.t. the probability measure P_{N}.

Let L^p(\mu^n) be the space of all measurable functions f: E^n \to\overline{\mathbb{R}} such that

\|f\|=\int\limits_{E^k}|f(z_1,\hdots,z_n)|^p \, \mu^n(dz_1, \dots ,dz_n)<\infty.

Note that L^2(\mu^n) becomes a Hilbert space when we define on it the scalar product

\langle f, g\rangle =\int\limits_{E^k}f(z_1,\hdots,z_n) g(z_1,\hdots,z_n)\, \mu^n(dz_1, \dots ,dz_n).

We denote L^p_{\text{sym}}(\mu^n) as the subset of symmetric functions in L^p(\mu^n), in the sense that the functions are invariant under all permutations of the arguments. Now, for each A\in\mathcal{A}, we define the random variable \widehat{N}(A)=N(A)-\mu(A), which is also known as a compensated Poisson measure.
For each symmetric function f\in L^2_{\text{sym}}(\mu^n), one can define the multiple Wiener-It\^o integral I_n(f) w.r.t the compensated Poisson measure \widehat{N} denoted by

I_n(f)=\int_{E^n}f(z_1,\hdots, z_n) \widehat{N}^n(dz_1, \dots ,dz_n). \ \ \ (1)

At first, let \mathcal{S}_n be the class of simple functions f, which takes the form

f(z_1,z_2,....,z_n)=\sum_{k=1}^m\lambda_k \mathbf{1}_{A_{1}^{(k)}\times\ldots \times A_{n}^{(k)}}(z_1,z_2,....,z_n), \ \ (2)

where A_{i}^{(k)}\in\mathcal{A}, \lambda_k\in \mathbb{R} and the sets A_{1}^{(k)}\times\ldots \times A_{n}^{(k)} are pairwise disjoint such that f is symmetric and vanishes on diagonals, that means f(z_1, \ldots , z_n) = 0 if z_i = z_j for some i\neq j. The multiple Wiener-It\^o integral for a simple function f in the form (2) with respect to the compensated Poisson measure \widehat{N} is defined by

I_n(f)=\sum_{k=1}^m\lambda_k\widehat{N}(A_1)\ldots\widehat{N}(A_n).

Since the class \mathcal{S}_n is dense in L^2_{\rm sym}(\mu^n) then for every f\in L^2_{\rm sym}(\mu^n), there exists a sequence \{f_l\}_{l\ge0}\subset\mathcal{S}_n such that f_l\to f in L^2_{\rm sym}(\mu^n). Moreover, one can show that \mathbf{E}[I_n(f_l)^2] = k!\|f_l\|^2. Hence, the the multiple Wiener-It\^o integral I_n(f) for a symmetric function f\in L^2_{\rm sym}(\mu^n) can be defined as the limit of the sequence \{I_n(f_l)\}_{l\ge 0} in L^2(P_N) and we denote it as (1).

Proposition 2.1. For n,m\geq 1 and f\in L_{\rm sym}^2(\mu^n), g\in L_{\rm sym}^2(\mu^m), then
1. \mathbf{E}[I_n(f)]=0,
2. \mathbf{E}[I_n(f) I_m(g)]= \delta_{n,m} n!\langle f,g \rangle_{L^2(\mu^n)}
where \delta_{n,m} is the Kronecker delta.

For a measurable function F:\mathcal{M}(E)\to\overline{\mathbb R} and z\in E we define the difference operator as

D_zF(\eta)=F(\eta+\delta_z)-F(\eta),

where \delta_z is the Dirac measure at the point z. The iterated difference operator is given by

D_{z_1,\hdots,z_n}F=D_{z_1}D_{z_2,\hdots,z_n}F.

We define the kernels of F as functions f_n: E^n\to \overline{\mathbb R} given by

f_n(z_1,\hdots,z_n)=\frac{1}{n!}\mathbf{E}[D_{z_1,\hdots,z_n}F], n \geq 1,

Note that f_n is a symmetric function.

We define the Ornstein-Uhlenbeck generator as

LF(\eta) = \int\limits_E (F( \eta - \delta_z) - F(\eta)) \eta(dz) - \int\limits_E (F(\eta) - F(\eta + \delta _z))\, \mu(dz).

Proposition 2.2. For each F\in L^2(P_N), then the kernels f_n are elements of L^2(\mu^n), n\ge 1 and uniquely admit the Wiener-It\^o chaos expansion in the form

F=\mathbf{E}[F]+\sum_{n=1}^{\infty}I_n(f_n),


where the sum converges in L^2(P_N). Furthermore, for F,G\in L^2(P_N)

{\rm Cov}(F,G)=\mathbf{E}[FG]- \mathbf{E}[F]\mathbf{E}[G]=\sum_{n=1}^\infty n!\langle f_n, g_n \rangle_{L^2(\mu^n)}.

Proposition 2.3. Let F\in L^2(P_N), and assume that

\sum_{n=1}^\infty n \, n!\|f_n\|^2<\infty.


Then the difference of F at z\in E is given by

D_zF=\sum_{n=1}^\infty n I_{n-1}(f_n(y,\cdot)).


Proposition 2.4. For each random variable F\in L^2(P_N) such that

\sum_{n=1}^\infty i^2i!\|f_n\|^2<\infty,


then the Ornstein-Uhlenbeck generator L is calculated as

LF=-\sum_{n=1}^{\infty}n I_n(f_n).


Moreover, its inverse operator is calculated as

L^{-1}F=-\sum_{n=1}^\infty\frac{1}{n}I_n(f_n).


for each F\in L^2(P_N) such that \mathbf{E}[F]=0.

For more details of the Malliavin calculus on Poisson space, we refer the reader to [Nualart1990].

III – Multi-dimensional Malliavin-Stein inequality

In the next sequence, we use the probabilistic distance of two d-dimensional random vectors X,Y such that \mathbf{E}(\|X\|_{\mathbb{R}^d}), \mathbf{E}(\|Y\|_{\mathbb{R}^d})<\infty, which is defined by

\Delta(X,Y)=\sup_{g\in \mathcal H}|\mathbf{E}(g(X))-\mathbf{E}(g(Y))|,

where \mathcal{H} is the family of all real-valued functions g\in C^2(\mathbb{R}^d) such that

\|g\|_{{\rm Lip}}=\sup_{x\neq y}\frac{|g(x)-g(y)|}{\|x-y\|_{\mathbb{R}^d}}\le 1, \sup_{x\in\mathbb{R}^d}\| {\rm Hess}( g(x))\|\le 1.

In the above inequality,

{\rm Hess}(g(z))=\left.\left(\frac{\partial^2 g}{\partial x_i\partial x_j}(z)\right)_{i,j=1}^d\right.

stands for the Hessian matrix of g evaluated at a point z and we use the notation of operator norm for a d\times d real matrix A given by

\|A \| = \sup_{\|x\|_{\mathbb{R}^d}=1} \|Ax\|_{\mathbb{R}^d}.


Theorem 3.1. [Multi-dimensional Malliavin-Stein inequality] Consider a random vector F=(F_1,\ldots,F_d)\subset L^2(P_N), d\ge2 such that for 1\leq i\leq d, F_i\in{\rm dom}(D), and \mathbf{E}(F_i)=0. Suppose that X\sim\mathcal{N}_d(0,C) , where C=\{C(i,j): i,j= 1,\ldots,d \} is a d\times d positive definite symmetric matrix. Then,

\begin{array}{ll}\displaystyle\Delta(F,X) \leq \|C^{-1}\| \|C\|^{1/2} \sqrt{\sum_{i,j=1}^{d} \mathbf{E}[(C(i,j) - \langle DF_i,-DL^{-1}F_j \rangle_{L^2(\mu)} )^2 ] } \\\displaystyle+ \cfrac{\sqrt{2\pi}}{8} \|C^{-1}\|^{3/2} \|C\| \int_E \mu(dz)\mathbf{E}\left[\left(\sum_{i=1}^d|D_z F_i | \right)^2 \left(\sum_{i=1}^d|D_z L^{-1} F_i | \right) \right].\end{array}

For the proof, we refer to [Peccati2010b].

Now we consider a d-dimensional random vector F=(F_1,\ldots,F_d) \subset L^2(P_N) with the covariance matrix \Sigma=\{\Sigma(i,j): i,j= 1,\ldots,d \} such that each component F_i has finite Wiener-It\^o chaos expansions with kernels f_{i}^{(n)}, which vanishes if n>k. Let give the centered random vector

G=\sqrt{C\Sigma^{-1}}\left(F-\mathbf{E}[F]\right),

where \sqrt{A} stands for the square root of a positive definite matrix A, i.e if A has the eigenvalues decomposition A= P^{-1}{\rm diag}({\lambda_1},\ldots,{\lambda_d})P
then

\sqrt{A}=P^{-1}{\rm diag}(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_d})P.

Let us use vector notations

\nabla_zF=(D_zF_1,\ldots,D_zF_d), \ \nabla_z L F=(D_z LF_1,\ldots ,D_z LF_d)

and note that the inequality

{\rm trace}(AB)\le {\rm trace}(A) {\rm trace}(B)

holds for all positive definite matrices A,B.
Therefore, by the properties matrix trace {\rm trace}(AB)={\rm trace}(BA) and using the inequality (3), we have

\sum_{i,j=1}^{d}(C(i,j) - \langle DG_i,-DL^{-1}G_j \rangle_{L^2(\mu)} )^2 ={\rm trace}\left[\left(C- \int_E\mu(dz) \nabla_z G(-\nabla_z L G)^T\right)^2\right]
={\rm trace}\left[\left(\sqrt{C\Sigma^{-1}}\left( \Sigma - \int_E\mu(dz) \nabla_z [F-\mathbf{E}(F)](-\nabla_z L [F-\mathbf{E}(F)])^T\right)\sqrt{C\Sigma^{-1}}^T\right)^2\right]
={\rm trace}\left[ (C\Sigma^{-1})^2 \left( \Sigma - \int_E\mu(dz) \nabla_z [F-\mathbf{E}(F)](-\nabla_z L [F-\mathbf{E}(F)])^T\right)^2\right]
\le {\rm trace} [(C\Sigma^{-1})^2]{\rm trace} \left[\left( \Sigma - \int_E\mu(dz) \nabla_z [F-\mathbf{E}(F)](-\nabla_z L [F-\mathbf{E}(F)])^T\right)^2\right]
=\|C\Sigma^{-1}\|_{F}^2 \sum_{i,j=1}^{d}\left(\Sigma(i,j) - \langle D[F_i-\mathbf{E}(F)],-DL^{-1}[F_j-\mathbf{E}(F)] \rangle_{L^2(\mu)} \right)^2,

where

\|A\|_F=\sqrt{{\rm trace}(A^TA)}

denotes the Frobenius norm of matrix A.
Note that

\Sigma(i,j)={\rm Cov}(F_i,F_j)=\sum_{n=1}^{k}n!\left\langle f_i^{(n)}, f_j^{(n)} \right\rangle_{L^2(\mu^n)},

and

\langle D[F_i-\mathbf{E}(F_i)],-DL^{-1}[F_j-\mathbf{E}(F_j)] \rangle_{L^2(\mu)}=\left \langle \sum_{n=1}^knI_{n-1}(f_i^{(n)}(z,\cdot)),\sum_{n=1}^k I_{n-1}(f_j^{(n)}(z,\cdot))\right\rangle_{L^2(\mu)}.

Hence,

\begin{array}{l} \displaystyle\mathbf{E}[(\Sigma(i,j) - \langle D[F_i-\mathbf{E}(F_i)],-DL^{-1}[F_j-\mathbf{E}(F_j)] \rangle_{L^2(\mu)} )^2]\\ \displaystyle\le k^2\left( \sum_{n=1}^{k}\mathbf{E}\left[\left(n!\left\langle f_i^{(n)}, f_j^{(n)} \right\rangle_{L^2(\mu^n)}-n\left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{n-1}(f_j^{(n)}(z,\cdot)) \right\rangle_{L^2(\mu)}\right)^2 \right]\right.\\ \displaystyle +\left. \sum_{n,m=1,\, n \neq m}^k \mathbf{E} \left[n^2 \left\langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{m-1}(f_j^{(m)}(z,\cdot))\right\rangle_{L^2(\mu)}^2\right]\right)\\ \displaystyle =\ k^2 \sum_{1\le n,m\le k}n^2{\rm Var}\left( \left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{m-1}(f_j^{(m)}(z,\cdot)) \right\rangle_{L^2(\mu)} \right).\end{array}

It follows that

\sqrt{\sum_{i,j=1}^{d} \mathbf{E}[(C(i,j) - \langle DG_i,-DL^{-1}G_j \rangle_{L^2(\mu)} )^2 ] }
\le k^2 \|C\Sigma^{-1}\|_{F} \sqrt{\sum_{i,j=1}^{d}\sum_{n,m=1}^{k} {\rm Var}\left( \left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{m-1}(f_j^{(m)}(z,\cdot)) \right \rangle_{L^2(\mu)} \right) }. \ \ (4)

Moreover, by using Holder inequality and the property of matrix norm, we have

\int_E \mu(dz)\mathbf{E}\left[\left(\sum_{i=1}^d|D_z G_i | \right)^2 \left(\sum_{i=1}^d|D_z L^{-1} G_i | \right) \right]\le d^{3/2}\int_E \mu(dz)\mathbf{E}\left[\|\nabla_z G \|_{\mathbb{R}^d}^2\|\nabla_zL^{-1} G \|_{\mathbb{R}^d} \right]
=d^{3/2}\int_E \mu(dz)\mathbf{E}\left[\| \sqrt{C\Sigma^{-1}} \nabla_z [F-\mathbf{E}(F)]\|_{\mathbb{R}^d}^2\|\sqrt{C\Sigma^{-1}} \nabla_zL^{-1}[F-\mathbf{E}(F)] \|_{\mathbb{R}^d} \right]
\le d^{3/2}\|\sqrt{C\Sigma^{-1}}\|^3\int_E \mu(dz)\mathbf{E}\left[\| \nabla_z [F-\mathbf{E}(F)]\|_{\mathbb{R}^d}^2\| \nabla_zL^{-1} [F-\mathbf{E}(F)] \|_{\mathbb{R}^d} \right]
\le d^{3/2}\|\sqrt{C\Sigma^{-1}}\|^3 \left( \int_E \mu(dz) \mathbf{E}\left[\left(\sum_{i=1}^d|D_z [F_i-\mathbf{E}(F_i)] |^2\right)^2\right] \right)^{1/2}
\times \left( \int_E \mu(dz) \mathbf{E}\left[ \sum_{i=1}^d|D_z L^{-1} [F_i-\mathbf{E}(F_i)] |^2 \right] \right)^{1/2}

\le d^2 \|\sqrt{C\Sigma^{-1}}\|^3 \left( \sum_{i=1}^d \int_E \mu(dz) E\left[|D_z [F_i-\mathbf{E}(F_i)] |^4\right] \right)^{1/2}

\times \left( \sum_{i=1}^d \int_E \mu(dz) \mathbf{E}\left[|D_z L^{-1} [F_i-\mathbf{E}(F_i)] |^2\right] \right)^{1/2}

\le d^2 \|\sqrt{C\Sigma^{-1}}\|^3 \left( \sum_{i=1}^d \int\limits_E\mu(dz) k^3 \sum_{n=1}^k n^4 \mathbf{E}[I_{n-1}(f_i^{(n)}(z,\cdot))^4] \right)^{1/2}

\times \left( \sum_{i=1}^d \int\limits_E\mu(dz)\sum_{n=1}^k \mathbf{E}[I_{n-1}(f_i^{(n)}(z,\cdot))^2]\right)^{1/2}

= d^2 \|\sqrt{C\Sigma^{-1}}\|^3 \left( \sum_{i=1}^d k^3 \sum_{n=1}^k n^4 \mathbf{E}[\|I_{n-1}(f_i^{(n)}(z,\cdot))^2 \|^2] \right)^{1/2} \left( \sum_{i=1}^d \sum_{n=1}^k (n-1)!\|f_i^{(n)}\|^2 \right)^{1/2}

\le d^{2} k^{7/2} \|\sqrt{C\Sigma^{-1}}\|^3({\rm trace}(\Sigma))^{1/2} \sqrt{\sum_{i=1}^d\sum_{n=1}^k \mathbf{E}\left[\|I_{n-1}(f_i^{(n)}(z,\cdot))^2 \|^2\right]}. \ \ (5)
Substituting (4) and (5) to the inequality in Theorem 3.1 for G, we obtain that

Theorem 3.2. Let give a d-dimensional Gaussian random variable X\sim \mathcal{N}_d(0,C). Assume that F=(F_1,\ldots,F_d) \subset L^2(P_N) such that {\rm Cov}(F_i,F_j)=\Sigma(i,j), \ i,j=1,d and F_i has finite Wiener-It\^o chaos expansions with kernels f_{i}^{(n)}, which vanishes if n>k. Then

\begin{array}{lll}\displaystyle\Delta\left(\sqrt{C\Sigma^{-1}}\left(F-\mathbf{E}(F)\right),X\right) \leq \\ \displaystyle \cfrac{ \sqrt{2\pi}}{8}d^{2} k^{7/2} \|\sqrt{C\Sigma^{-1}}\|^3 \|C^{-1}\|^{3/2} \|C\| ({\rm trace}(\Sigma))^{1/2} \sqrt{\sum_{i=1}^d\sum_{n=1}^k \mathbf{E}\left[\|I_{n-1}(f_i^{(n)}(z,\cdot))^2 \|^2\right]}\\ \displaystyle + k^2\|C\Sigma^{-1}\|_{F} \|C^{-1}\| \|C\|^{1/2}\sqrt{\sum_{i,j=1}^{d}\sum_{n,m=1}^{k} {\rm Var}\left( \left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{n-1}(f_j^{(m)}(z,\cdot)) \right \rangle_{L^2(\mu)} \right) }.\end{array}
IV – Application for multi-dimensional U-statistics

In this section we consider the d-dimensional vector of U-statistics of the Poisson point process N

F = \left(\sum_{({z}_1,\ldots,{z}_{k_1}) \in S_{k_1}(N)} \phi_1({z}_1,\dots,{z}_{k_1}),\ldots,\sum_{({z}_1,\dots,{z}_{k_d}) \in S_{k_d}(N)} \phi_d({z}_1,\dots,{z}_{k_d}) \right), \ \ (6)

where \phi_i\in L^1_{\rm sym}(\mu^{k_i}), and S_{k_i}(N) denotes the set of all k_i-tuples of distinct points of N. This means that each component

F_i=\sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} \phi_i({z}_1,\dots,{z}_{k_i})

is an U-statistic of order k_i with respect to the Poisson point process N, i=1,d.

The following properties of (one-dimensional) U-statistics are obtained by Reitzner and Schulte in [Reitzner2011]

Proposition 4.1. Let F\in L^2(P_N) be a U-statistic of order k in the form

F=\sum_{({z}_1,\dots,{z}_{k})\in S_k(N)} \phi({z}_1,\dots,{z}_k)


Then the kernels of the Wiener-It\^o chaos expansion of F have the form

f_n(z_1,\hdots,z_n)= \begin{cases}\displaystyle \binom{k}{n}\int\limits_{E^{k-n}}\phi(z_1,\hdots,z_n,x_1,\hdots,x_{k-n})\, \mu^{k-n}(dx_1,\dots,dx_{k-n}), &n\leq k\\ 0, & n>k. \end{cases}

Proposition 4.2. Assume F\in L^2(P_N), then
1. If F is a U-statistic, then F has a finite Wiener-It\^o chaos expansion with kernels f_n\in L^1(\mu^n)\cap L^2(\mu^n) , n=1,\hdots,k.
2. If F has a finite Wiener-Itô chaos expansion with kernels f_n\in L^1(\mu^n) \cap L^ 2 (\mu^n), n=1,\hdots,k, then F is a finite sum of U-statistics and a constant.

Proposition 4.3. Let f_i\in \mathcal{S}_{k_i}, \ i=1,\hdots,m and \Pi be the set of all partitions of Z=\{z_1^{(1)},\dots,z_{n_1}^{(1)},\dots,z_{1}^{(m)} ,\dots, z_{n_m}^{(m)}\}, n_i\le k_i such that for each \pi \in \Pi,
1. z^{(i)}_{l}, z^{(i)}_{h}\in Z, l\neq h are always in different subsets of \pi, and such that
2. every subset of \pi has at least two elements.
For every partition \pi\in\Pi we define an operator R^{\pi} that replaces all elements of Z in \prod_{i=1}^m f_i(z_1^{(i)},\hdots,z_{n_i}^{(i)}) that belong to the same subset of \pi by a new variable x_j, j =1, \hdots,{|\pi|}, where |\pi| denotes the number of subsets of the partition \pi. Then

\mathbf{E} \left[\prod_{i=1}^m I_{n_i}(f_i)\right]=\sum_{\pi\in\Pi}\int\limits_{E^{|\pi|}}R^{\pi}(\prod_{i=1}^m f_i(\cdot))(x_1,\hdots,x_{|\pi|})\, \mu^{|\pi|}(dx_1,\dots,dx_{|\pi|}).

Using the Proposition 4.3 and the same technique in [Reitzner2011] (Lemma 4.6), we also obtain that if F=(F_1,F_2,...,F_d)\subset L^2(P_N) is a vector of U-statistics in the form (6) such that \phi_i, i=1,d are simple functions, then all kernels f_i^{(n)} are also simple functions and

{\rm Var}\left( \left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{m-1}(f_j^{(m)}(z,\cdot)) \right \rangle_{L^2(\mu)} \right)
= \mathbf{E}\left[ \left \langle I_{n-1}(f_i^{(n)}(z,\cdot)),I_{m-1}(f_j^{(m)}(z,\cdot)) \right \rangle_{L^2(\mu)}^2\right]- \delta_{n,m}\left((n-1)!\left\langle f_i^{(n)}, f_j^{(m)} \right\rangle_{L^2(\mu^n)}\right)^2
= \int_{E^2}\mathbf{E}\left[ I_{n-1}(f_i^{(n)}(z,\cdot))^2 I_{m-1}(f_j^{(m)}(y,\cdot))^2 \right] \mu^2(dy,dz)
-\delta_{n,m}\left((n-1)!\left\langle f_i^{(n)}, f_j^{(m)} \right\rangle_{L^2(\mu^n)}\right)^2
\le \sum_{\pi\in \overline{\Pi}_{n,m}}\int_{E^{|\pi|}}R^{\pi}\left( \left|f^{(n)}_i(.)f^{(n)}_i(.)f^{(m)}_j(.)f^{(m)}_j(.)\right|\right)(x_1,\ldots, x_{|\pi|})\mu^{|\pi|}(dx_1,\ldots, dx_{|\pi|}),

and

\mathbf{E}\left[\|I_{n-1}(f_i^{(n)}(z,\cdot))^2 \|^2\right]=\int_{E}\mathbf{E}\left[I_{n-1}(f_i^{(n)}(z,\cdot))^4\right]\mu(dz)

\le \sum_{\pi\in \overline{\Pi}_{n,m}}\int_{E^{|\pi|}}R^{\pi}\left( \left|f^{(n)}_i(.)f^{(n)}_i(.)f^{(n)}_i(.)f^{(n)}_i(.)\right|\right)(x_1,\ldots, x_{|\pi|})\mu^{|\pi|}(dx_1,\ldots, dx_{|\pi|}),
where \Pi_{n,n} stands for the set of partitions satisfying the conditions in Proposition 4.3 with Z_{n,m}=\{z_{1}^{(1)}\ldots z_{n-1}^{(1)},z_{1}^{(2)}\ldots z_{n-1}^{(2)},z_{1}^{(3)}\ldots z_{m-1}^{(3)},z_{1}^{(4)}\ldots z_{m-1}^{(4)}\} and \overline{\Pi}_{n,m} \subset \Pi_{n,m} denotes the set of all partitions in \Pi_{n,m} of such that for any \pi \in \overline{\Pi}_{n,m} and any decomposition of \{ 1, 2,3,4\} into two disjoint sets M_1, M_2 there are i \in M_1, j \in M_2 and two variables z_l^{(i)}, z_h^{(j)} which are in the same subset of \pi.
By the formula of kernels in Proposition 4.1., we note that

\sum_{\pi\in \overline{\Pi}}\int_{E^{|\pi|}}R^{\pi}\left( \left|f^{(n)}_i(.)f^{(n)}_i(.)f^{(m)}_j(.)f^{(m)}_j(.)\right|\right)(x_1,\ldots, x_{|\pi|})\mu^{|\pi|}(dx_1,\ldots, dx_{|\pi|})
\le M_{n,m}(i,j) = \mathbf{1}_{n\le k_i, m\le k_j} \binom{k_i}{n}^2\binom{k_j}{m}^2 \sum_{\pi \in \overline{\Pi}_{n,m}}\int\limits_{E^{|\pi|}} \int\limits_{E^{2(k_i-m)}} \int\limits_{E^{2(k_j-n)}}
R^{\pi} \left( |\prod_{l=1}^2 \phi_i(\cdot , x^{(l)}_1,\hdots,x^{(l)}_{k_i-n})\prod_{l=3}^4 \phi_j(\cdot , x^{(l)}_1,\hdots,x^{(l)}_{k_j-m})| \right)(y_1,\hdots,y_{|\pi|}),
\mu^{|\pi|+2(k_i+k_j-j-i)}(dx_1^{(1)},\hdots,dx_{k_i-n}^{(2)},dx_{1}^{(3)} \ldots dx_{k_j-m}^{(4)}, dy_1, \dots dy_{|\pi|}). \ \ (7)

This fact follows that

Theorem 4.1. Assume that F=(F_1,F_2,...,F_d)\subset L^2(P_N) is a vector of U-statistics in the form (\ref{ustat}) such that \phi_i, i=1,d are simple functions. Then

\begin{array}{lll}\displaystyle\Delta\left(\sqrt{C\Sigma^{-1}}\left(F-\mathbf{E}(F)\right),X\right) \leq \\ \displaystyle \cfrac{ \sqrt{2\pi}}{8}d^{2} k^{7/2} \|\sqrt{C\Sigma^{-1}}\|^3 \|C^{-1}\|^{3/2} \|C\| ({\rm trace}(\Sigma))^{1/2} \sqrt{\sum_{i=1}^d\sum_{n=1}^k M_{n,n}(i,i)}\\ \displaystyle + k^2\|C\Sigma^{-1}\|_{F} \|C^{-1}\| \|C\|^{1/2}\sqrt{\sum_{i,j=1}^{d}\sum_{n,m=1}^{k} M_{n,m}(i,j) },\end{array}


where k=\max\{k_i, 1\le i\le,d\} and M_{n,m}(i,j), 1\le i,j\le d, 1\le n,m\le k are defined in (7).

Now, we consider that F=(F_1,F_2,....,F_d)\subset L^2(P_N) a vector of U-statistics in the form (6) such that

\sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} |\phi_i({z}_1,\dots,{z}_{k_i})|\in L^2(P_N).

Then, for each i=1,2,\ldots,d there exists a sequence \{\phi_{i,l}\}_{l\ge 0}\subset \mathcal{S}_{k_i} such that |\phi_{i,l}|\le |\phi_i| and \phi_{i,l} converges to \phi_i \mu^{k_i}-almost everywhere. Let give the vector of U-statistics F^{(l)}=(F_{1,l},\ldots,F_{d,l}), where

F_{i,l}=\sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} \phi_{i,l}({z}_1,\dots,{z}_{k_i}).

Hence,

|F_{i,l}|\le \sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} |\phi_{i,l}({z}_1,\dots,{z}_{k_i})|\le \sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} |\phi_i({z}_1,\dots,{z}_{k_i})|\in L^2(P_N).

Its follow that F_{i,l}\in L^2(P_N), F_{i,l} converges to F_i almost surely and all kernels f_{i,l}^{(n)} in the Wiener-It\^o chaos expansion of F_{i,l} are simple functions.
Note that

\Sigma(i,j)={\rm Cov}(F_i,F_j)= =\sum_{n=1}^{\infty}n!\binom{k_i}{n}\binom{k_j}{n}\int\limits_{E^n}\ \int\limits_{E^{k_i-n}} \phi_i(z_1,\hdots,z_n,x_1,\hdots,x_{k_i-n})\mu^{k_i-n}(dx_1, \dots dx_{k_i-n}) \times \int\limits_{E^{k_j-n}}\phi_j(z_1,\hdots,z_n,x_1,\hdots,x_{k_j-n})\, \mu^{k_j-n}(dx_1, \dots dx_{k_j-n}) \mu^n(dz_1, \dots, dz_n).

Moreover, the integrals

\int\limits_{E^n}\ \int\limits_{E^{k_i-n}} |\phi_i(z_1,\hdots,z_n,x_1,\hdots,x_{k_i-n})|\mu^{k_i-n}(dx_1, \dots dx_{k_i-n}) \times \int\limits_{E^{k_j-n}}|\phi_j(z_1,\hdots,z_n,x_1,\hdots,x_{k_j-n})|\, \mu^{k_j-n}(dx_1, \dots dx_{k_j-n}) \mu^n(dz_1, \dots, dz_n)

always exist for 1\le n\le k_i, 1\le i,j\le d.
Therefore, by applying the Lebesgue dominated convergence theorem, we obtain that \Sigma^{(l)}(i,j)\to \Sigma(i,j) and \mathbf{E}(F_{i,l})\to\mathbf{E}(F_{i}) for l\to\infty. Hence,

\sqrt{C(\Sigma^{(l)})^{-1}}\left(F^{(l)}-\mathbf{E}(F^{(l)})\right)\to \sqrt{C\Sigma^{-1}}\left(F-\mathbf{E}(F)\right)

almost surely for l\to\infty.
Note that, the almost sure convergence implies the convergence in the probabilistic distance \Delta and |M^{(l)}_{n,m}(i,j)|\le |M_{n,m}(i,j)| , where M^{(l)}_{n,m}(i,j) is defined when we replace \phi_{i},\phi_{j} by \phi_{i}^{(l)},\phi_{j}^{(l)} in (7). Therefore, by using Theorem 4.1 and applying the triangular inequality, we conclude that

Theorem 4.2. Assume that F=(F_1,\ldots,F_d)\subset L^2(P_N) is a vector of U-statistics in the form (6) such that

\sum_{({z}_1,\dots,{z}_{k_i})\in S_{k_i}(N)} |\phi_i({z}_1,\dots,{z}_{k_i})|\in L^2(P_N).


Then

\begin{array}{lll}\displaystyle\Delta\left(\sqrt{C\Sigma^{-1}}\left(F-\mathbf{E}(F)\right),X\right) \leq \\ \displaystyle \cfrac{ \sqrt{2\pi}}{8}d^{2} k^{7/2} \|\sqrt{C\Sigma^{-1}}\|^3 \|C^{-1}\|^{3/2} \|C\| ({\rm trace}(\Sigma))^{1/2} \sqrt{\sum_{i=1}^d\sum_{n=1}^k M_{n,n}(i,i)}\\ \displaystyle + k^2\|C\Sigma^{-1}\|_{F} \|C^{-1}\| \|C\|^{1/2}\sqrt{\sum_{i,j=1}^{d}\sum_{n,m=1}^{k} M_{n,m}(i,j) }, \end{array}


where k=\max\{k_i, 1\le i\le,d\} and M_{n,m}(i,j), 1\le i,j\le d, 1\le n,m\le k are defined in (7).

Corollary 4.3. Assume that \{F^{(l)}\}_{l\ge 0} is a sequence of vectors of U-statistics, which are defined as in Theorem 4.2, such that

\max_{1\le i,j\le d, 1\le n,m\le k}M_{n,m}^{(l)}(i,j)\to 0


for l\to\infty, then the law of \sqrt{C(\Sigma^{(l)})^{-1}}\left(F^{(l)}-\mathbf{E}(F^{(l)})\right) converges to the multivariate Gaussian law \mathcal{N}_d(0,C).

References

[Bor96] Yu. V. Borovskikh, U-statistics in Banach spaces, VSP, Utrecht, 1996. MR1419498
[Hoe48] W. Hoeffding, A class of statistics with asymptotically normal distribution, Ann. Math. Statistics 19 (1948), 293–325. MR0026294
[HPA95] C. Houdr´e and V. P´erez-Abreu, Covariance identities and inequalities for functionals on Wiener and Poisson spaces, Ann. Probab. 23 (1995), no. 1, 400–419. MR1330776
[KB94] V. S. Koroljuk and Yu. V. Borovskich, Theory of U-statistics, Mathematics and its Applications, vol. 273, Kluwer Academic Publishers Group, Dordrecht, 1994. MR1472486
[Lee90] A. J. Lee, U-statistics, theory and practice, Statistics: Textbooks and Monographs, vol. 110, Marcel Dekker Inc., New York, 1990. MR1075417
[LP11] G. Last and M. Penrose, Poisson process fock space representation, chaos expansion and covariance inequalities, Probability Theory and Related Fields 150 (2011), 663–690.
[NV90] D. Nualart and J. Vives, Anticipative calculus for the Poisson process based on the Fock space, S´eminaire de Probabilit´es, XXIV, 1988/89, Lecture Notes in Math., vol. 1426, Springer, Berlin, 1990, pp. 154–165. MR1071538
[PSTU10] G. Peccati, J. L. Sol´e, M. S. Taqqu, and F. Utzet, Stein’s method and normal approximation of Poisson functionals, Ann. Probab. 38 (2010), no. 2, 443–478. MR2642882
[PT11] G. Peccati and M. S. Taqqu, Wiener chaos: moments, cumulants and diagrams, Bocconi & Springer Series, vol. 1, Springer, Milan, 2011. MR2791919
[PZ10] G. Peccati and C. Zheng, Multi-dimensional Gaussian fluctuations on the Poisson space, Electron. J. Probab. 15 (2010), no. 48, 1487–1527. MR2727319
[RS11] M. Reitzner and M. Schulte, Central Limit Theorems for U-Statistics of Poisson Point Processes, ArXiv e-prints (2011).
[Wu00] L. Wu, A new modified logarithmic Sobolev inequality for Poisson point processes and several applications, Probab. Theory Related Fields 118 (2000), no. 3, 427–438.

Categories: Probability Theory, Stochastic Calculus of Variations

CSIST’ 2011

November 1, 2011 Leave a comment

“International congress on Computer Science:  Information Systems and Technologies” (CSIST’2011) will start on November 1st at the Lyceum of Belarusian State University. Organizers of the congress – Belarusian State University, Joint Institute of Informatics Problems of National Academy of Sciences of Belarus and the Scientific and Technological Association “Infopark”.

The forum program includes plenary sessions and the work of 11 sections:

Information Security and Computer Data Analysis
Intellectual Information Systems
Information and Communication Infrastructure
Information Systems and Technologies of Support of the Scientifically-Educational Environment
Computer-Focused Instrumentation and Measuring Systems
Optimization and Reliability of Information Systems
Parallel and Distributed Data Processing,
Software Engineering
Pattern Recognition, Information Management Systems
Theoretical Computer Science
Digital Media Technologies

The discussion will bring together scientists from Belarus, Russia, Moldova, Lithuania, Poland, Germany, France, Spain, USA, Vietnam, and UNESCO.

Link: http://www.csist.bsu.by/en/main.aspx

My talk entitled “Queueing system GI/M/1 with randomized threshold admission control” is a part of the section “Optimization and Reliability of Information Systems”.  The presentation is available here.

Categories: Conferences, Queueing Theory Tags: , ,

Lý thuyết phục vụ đám đông I

June 11, 2011 Leave a comment

Có bạn nào từng nghe nói đến một ngành Toán học thú vị có tên “Lý thuyết phục vụ đám đông” với ứng dụng vô cùng mạnh mẽ trong công nghệ thông tin, viễn thông, kinh tế…. Người nghiên cứu đầu tiên về nó là kỹ sư A.K. Erlang với bài báo vào năm 1909. Nó được hệ thống hóa thành lý thuyết vào khoảng những năm 1920s-1930s với những người đi tiên phong là những nhà Toán học O’Dell, Fry, Pollaczek, Kolmogorov, Khinchin… Đến những năm 1950s-1960s, Lý thuyết phục vụ đám đông hầu như được hoàn thiện về hình hài của nó như một bộ phận liên của Lý thuyết xác suất và Vận Trù học cho hệ thống ngẫu nhiên với những công trình quan trọng của Kendall, Lindley, Morse, Jackson, Gordon, Little, Takacs,…. Từ những năm 1980s-1990s, thì xu hướng áp dụng các công cụ của Giải tích ma trận được khởi xướng bởi Neuts, Lucantoni,… phát triển mạnh mẽ nhằm nghiên cứu các hệ phục vụ đám đông với những điều kiện điều khiển phức tạp.

www.sfu.ca/~pbastani/queue.jpg
Lý thuyết phục vụ đám đông hay lý thuyết hàng đợi – Queueing Theory, nghiên cứu các tính chất đặc trưng của mô hình toán liên quan đến hệ thống ngẫu nhiên như sau: có một hệ thống phục vụ và dòng khách hàng đến, trong đo các khách hàng tới hệ thống phải xếp hàng để đợi được phục vụ, khoảng thời gian đến của khách hàng, và khoảng thời gian phục vụ là những đại lượng ngẫu nhiên.
Có thể thấy những hệ thống như vậy trong thực tế, ví dụ: mạng điện thoại, mạng máy tính, hệ thống tính toán,…
Hệ thống phục vụ đám đông đặc trưng bởi:
+ Luồng khách hàng vào: theo quy luật phân phối nào đó, đi riêng lẻ hoặc theo nhóm,…
+ Thái độ của khách hàng: kiên nhẫn chờ hoặc không kiên nhẫn và bỏ đi với xác suất nào đó,…
+ Thời gian phục vụ: tuân theo quy luật phân phối nào đó
+ Khả năng phục vụ của hệ thống: phục vụ từng người một hoặc theo nhóm
+ Phương pháp phục vụ
- FCFS – First Come First Served.
- LCFS – Last Come First Served.
- SIRO – Service In Random Order.
- PS – Processor shared.
- IS – Infinitive server.
- Static priorities.
- Dynamic priorities.
- Preemption…
+ Phòng đợi: có thể giới hạn hoặc không giới hạn số lượng khách chờ.

Mục đích nghiên cứu của chuyên ngành:
+ Đánh giá tham số hệ thống bằng phương pháp thống kê.
+ Tìm điều kiện dừng của hệ thống.
+ Nghiên cứu các tính chất của hệ thống: xác suất được phục vụ, phân phối của số các yêu cầu ở trong hệ thống, phân phối của thời gian chờ, thời gian lưu trú của khách hàng,…
+ Bài toán điều khiển tối ưu của hệ thống khi sự thất lạc và lưu trú của khác hàng tương ứng với một hàm giá thành nào đó…

Hệ thống có thể được ký hiệu theo Kendall: A|B|m|n. Trong đó
A: Phân phối của thời gian vào.
B: Phân phối thời gian phục vụ.
m: Số máy phục vụ.
n: Số chỗ trong hàng đợi.
Trong đó A, B có thể nhận một trong các phân phối sau
M – phân phối mũ có hàm phân phối F(x)=1-e^{-\lambda x}
E_k – phân phối Erlang k pha có hàm phân phối:
F(x) = 1-\sum_{j=0}^{k-1}\frac{e^{-\lambda x}(\lambda x)^{j}}{j!}.
H_k – phân phối siêu lũy thừa có hàm phân phối  F(x) = \sum\limits_{j = 1}^k {q_j (1 - e^{ - \mu _j x} )} ,x \ge 0
D – phân phối tất định, có hàm phân phối   F(x)=\left\{\begin{matrix} 1, & \mbox{if }x\ge x_0 \\ 0, & \mbox{if }x<x_0 \end{matrix}\right. .
PH – phân phối pha
G – phân phối tổng quát
GI – phân phối tổng quát, của các khoảng thời gian vào hoặc phục vụ độc lập nhau.
Xin bắt đầu bằng vài khái niệm cơ bản
1. Phân phối mũ

Đại lượng ngẫu nhiên có phân phối mũ, nếu nó có hàm phân phối F(x) = P\{ \xi < x= 1 - e^{-ax} \} ,\ x \ge 0. Khi đó:
- Kỳ vọng toán học
M\xi = \int\limits_0^\infty {xdF(x)} = \int\limits_0^\infty {xf(x)dx} =a^{ - 1}
- Moment bậc i:
M\xi ^i = \int\limits_0^\infty {x^i dF(x) = \frac{{i!}}{{a^i }}.}

-Tính mất trí nhớ của phân phối mũ:
P{{\{ }}\xi \ge {{x + b|}}\xi \ge {{b\} = P\{ }}\xi \ge{{x\} }}

Cho \xi _{{1}} ,\xi _{{2}} ,...,\xi_{{n}} đại lượng ngẫu nhiên độc lập có phân phối mũ với tham số a_1 ,...,a_n tương ứng. Khi đó đại lượng ngẫu nhiên \xi = \min {{\{ }}\xi _1 {{,}}...{{,}}\xi _n {{\} }} có phân phối mũ với tham số {{a = a}}_{{1}} + {{a}}_{{2}} + ... +{{a}}_{{n}} .

Theo tính chất trên ta có

P{{\{ }}\xi = \xi _i {{\} =}}\frac{{{{a}}_{{i}}}}{{{a}}}Nếu đại lượng ngẫu nhiên \xi có phân phối mũ với tham số a, thì
http://latex.codecogs.com/gif.latex?F(\Delta%20t)%20=%20P\{%20\xi%20%3C%20\Delta%20t%20\}%20=%20a%20\Delta%20t+o(\Delta%20t)
2.  Phép biến đổi Laplace-Stieltjes
Phép biến đổi Laplace – Stieltjes của hàm phân phối A(t) của đại lượng ngẫu nhiên \xi là hàm
\alpha (q) = Ee^{ - q\xi } = \int\limits_0^\infty {e^{ - qt} dA(t),}
trong đó q – biến phức, {\mathop{\rm Re}\nolimits} q \ge 0. Hàm \alpha (q) gọi là phép biến đổi Laplace – Stieltjes của đại lượng ngẫu nhiên \xi .

Mối quan hệ của nó và phép biên đổi Laplace
\alpha (q) = \int\limits_0^\infty {e^{ - qt} dA(t) = q\int\limits_0^\infty{e^{ - qt} A(t)dt} }

Đối với hàm phân phối liên tục A(t) trên {\rm{[0;}}\infty {\rm{)}} có
i. \int\limits_0^\infty {e^{ - qt} dA'(t) = q\alpha (q) - qA(0).}
trong đó \alpha (q) là phép biến đổi Laplace – Stieltjes của hàm phân phối A(t).
ii. \alpha _i = E\xi ^i = ( - 1)^i \alpha ^{(i)} (q)|_{q = 0}
iii. \text{Var}(\xi) = E\xi ^2 - (E\xi )^2 = \alpha_2 - (\alpha_1 )^2 = \alpha''(0) - (\alpha' (0))^2 .

3. Xích Markov
Xích Markov là dạng đặc biệt có không quá đếm được trạng thái của quá trình Markov. Ta gọi quá trình ngẫu nhiên \{X_t, t\in I\} nhận giá trị thuộc tập hợp không quá đếm được E là xích Markov nếu với bất kì dãy t_0<t_1<...<t_n<t_{n+1} thuộc I thì
P(X_{t_{n+1}}=j\ | \ X_{t_0}=i_0,....,X_{t_{n}}=i_n) = P(X_{t_{n+1}}=j\ | X_{t_{n}}=i_n) với mọi i_0,...,i_{n},j\in E.

Như thế, một xích Markov được xác định hoàn toàn bằng \eta_i= P(X_0=i) gọi là phân phối ban đầu và các xác suất chuyển p_{ij}(s,t)=P(X_t=j|X_s=i).

Nếu p_{ij}(s,t)= p_{ij}(s+h,t+h) với mọi h thì ta gọi là \{X_t\} là xích Markov thuần nhất, và từ này trở về sau ta ngầm hiểu một chuỗi Markov thì thuần nhất.

Khi đó ta chỉ cần quan tâm tới p_{ij}(t)= P(X_t=j|X_0=i). Ma trận P(t)=(p_{ij}(t))_{i,j\in E} gọi là ma trận xác suất chuyển tại thời điểm t.

Như vậy khi nói đến xích Markov (thuần nhất) \{X_t, t\in I\} nghĩa là ta nói đến bộ đôi \{\eta, P(t)\}.

Trong trường hợp I là tập rời rạc, có thể thay P(t) bằng ma trận một bước chuyển P=(p_{i,j}), trong đó p_{i,j}=P(X_{n+1}=j|X_n=i) Nghĩa là xích Markov rời rạc \{X_n\} xác định bởi \{\eta, P\}.

Một kết quả quan trọng của xích Markov thuần nhất đó là phương trình Chapman-Kolmogorov

P(t+\Delta)=P(t)P(\Delta)
Trong trường hợp rời rạc ta còn có chú ý P(n)=P^n.
Từ phương trình Chapman-Kolmogorov suy ra
\frac{P(t+\Delta)-P(t)}{\Delta}=P(t)\frac{(P(\Delta)-I)}{\Delta}cho \Delta\downarrow 0 ta được P'(t)=P(t)Q, hay P(t)=e^{Qt}=\sum_{n=0}^{\infty} \frac{t^n}{n!}Q^n
Trong đó Q=(q_{i,j})=\lim_{\Delta\downarrow 0} \frac{P(\Delta)-I}{\Delta}, gọi là infinitesimal generator (hay ma trận cường độ chuyển) của chuỗi Markov (X_t)_{t\ge 0}.
Khi đó
q_{ij}=\lim_{\Delta\downarrow 0} \frac{p_{ij}(\Delta)}{\Delta}, i\neq j
q_{ii}=\lim_{\Delta\downarrow 0} \frac{p_{ii}(\Delta)-1}{\Delta}
q_{ij} gọi là cường độ chuyển từ trạng thái i sang trạng j. Chú ý rằng
\sum_{j\in E}q_{ij}=0
tức tổng các phần tử mỗi dòng của Q bằng 0.
4.  Renewal theory
Renewal Theory thực ra đã phát triển thành nhánh lý thuyết riêng trong ngành Xác suất. Ở đây không có tham vọng đi sâu xa mà chỉ là nói qua vài tư tưởng có liên quan.

Cho (Z_n)_{n\ge 0} là dãy các biến ngẫu nhiên dương độc lập, giả sử (Z_n)_{n\ge 1} cùng phân phối.
Ta đặt (T_n)_{n\ge 1} sao cho Z_0=T_1, Z_n=T_{n+1}-T_n hay T_{n}=\sum_{i=0}^{n-1}Z_{k}.
T_n gọi là thời điểm renewal thứ n, Z_n gọi là khoảng renewal thứ n

Ta đặt \nu_t=\text{max}\{n\in \mathbb{N}\ :\ T_n\le t\}, t\ge 0, khi đó (\nu_t)_{t\ge0} gọi là quá trình renewal từ (Z_n)
Khoảng ban đầu Z_0 gọi là delay. Nếu giả sử Z_0 cũng cùng phân phối với Z_k, k\ge 1 thì (\nu_t)_{t\ge 0} gọi là ordinary.

i152.photobucket.com/albums/s165/dumb_boy1988/renewal.png
Renewal Theorem.
Cho (\nu_t)_{t\ge 0} là quá trình renewal từ dãy các khoảng renewal (Z_n)_{n\ge1}. Giả sử rằng  E(X_0)<\infty, E(Z_k)=\lambda>0, k\ge 1
Thế thì
\lim_{t\to\infty}\frac{E(\nu_t)}{t}=\frac{1}{\lambda}
Tích chập của một hàm phân phối F xác định trên \mathbb{R}_+ với một hàm đo được Lebesgue g:\mathbb{R}_+\to\mathbb{R}_+ bị chặn trên mọi khoảng [0,t], t\ge 0 được kí hiệu bởi
F*g(t)=\int_{[0,t]} g(t-u)dF(u)
Ta đưa ra định nghĩa lũy thừa chập (convolutional power) bằng quy nạp với F^{*1}=F, F^{*n+1}=F^{*}*F.
Giả sử (\nu_t)_{t\ge 0} là một ordinary renewal process, với F(t) là hàm phân phối của khoảng renewal Z_k, k\ge 0 . R(t)=\sum_{n=1}^{\infty}F^{*n}(t) gọi là hàm renewal của (\nu_t)_{t\ge 0}.
Khi đó lấy biến biến đổi Laplace–Stieltjes, ta có \widehat{F}(s)=\frac{\widehat{R}(s)}{1+\widehat{R}(s)}. Điều này có nghĩa là (\nu_t)_{t\ge 0} hoàn toàn có thể xác định một cách duy nhất bởi hàm renewal của nó.
Xét (\nu_t)_{t\ge 0} là một ordinary renewal process, với F(t) là hàm phân phối của khoảng renewal Z_k, k\ge 0 và các thời điểm renewal tương ứng (T_k)_{k\ge 1}. Ta đặt
\mu(t)=\lim_{\Delta\downarrow 0}\frac{P\{ \nu_{t+\Delta}-\nu_t\ge 1\ | \ \nu_t-\nu_0=0 \}}{\Delta}
gọi là cường độ tức thời của (\nu_t)_{t\ge 0}
Khi đó P\{ \nu_{t+\Delta}-\nu_t\ge 1\ | \ \nu_t-\nu_0=0 \}=\mu(t)\Delta+o(\Delta) khi \Delta\downarrow 0.Ta có
F(\tau)=P\{Z_k\le \tau \}=P\{T_{k+1}-T_k\le \tau \}=P\{\nu_{T_k+\tau}-\nu_{T_k}\ge 1\}
F(\tau+\Delta)=P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1\}
=P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1, \nu_{T_k+\tau}-\nu_{T_k}\ge 1 \} +P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1, \nu_{T_k+\tau}-\nu_{T_k}=0 \}
=P\{ \nu_{T_k+\tau}-\nu_{T_k}\ge 1 \} +P\{ \nu_{T_k+\tau}-\nu_{T_k}=0 \}P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1\ |\ \nu_{T_k+\tau}-\nu_{T_k}=0 \}
=F(\tau)+(1-F(\tau))\left( \mu(\tau)\Delta+o(\Delta) \right)
Cho \Delta\to 0, ta có
F'(\tau)=(1-F(\tau))\mu(\tau)
Giải phương trình vi phân một biến này ta dễ dàng thu được mối quan liên hệ giữa cường độ tức thời của ordinary renewal process hàm phân phối của renewal interval tương ứng
F(t)=1-e^{-\int_0^t \mu(\tau)d\tau}
Categories: Probability Theory, Queueing Theory

Chiều Hausdorff và năng lượng Bessel–Riesz

April 6, 2011 Leave a comment

Chiều Haudorff của một tập được định nghĩa là infimum của tập các giá trị d không âm sao cho độ đo Hausdorff d-chiều của tập đó bằng 0. Công việc tính chiều Haudorff của tập nào đó không phải lúc nào cũng thuận lợi, tuy nhiên với tập compact E trong \mathbb R^n ta có thể ước lượng chận trên bằng các chiều hộp Minkowski

\dim(E)\le \dim_{\text{lower box}}(E) \leq \dim_{\text{upper box}} (E)

Câu hỏi nảy sinh cho chận dưới được trả lời trong PhD thesis năm 1935 của Otto Frostman

Định lý 1. Giả sử tổn tại một độ đo xác suất \mu trên tập compact E\subset \mathbb R^d thỏa mãn: có các hằng số \alpha, C sao cho với r\in(0,1) thì

\mu(B_{\infty}(y,r))\le Cr^{\alpha}với \mu-hầu khắp các giá trị của y \in\mathbb R^d. Khi đó
\dim(E)\ge \alpha

Định lý 2. Nếu chiều của tập compact E không bé hơn \alpha thế thì với \beta<\alpha luôn tồn tại độ đo xác suất \mu trên E sao cho

\sup_{x\in\mathbb R^d}\sup_{r\in(0,1)}\frac{\mu(B_{\infty}(y,r))}{r^{\beta}}<\infty

Chúng ta gọi năng lượng Bessel–Riesz \alpha-chiều của độ đo xác suất \mu trên tập compact E\subset \mathbb R^d là đại lượng

\text{Energy}_{\alpha}(\mu)=\int_{\mathbb R^d}\int_{\mathbb R^d}|x-y|^{-\alpha}\mu(dx)\mu(dy)Capacity của E sẽ là đại lượng
\text{Cap}_{\alpha}(E)=(\inf_{\mu \in \mathcal{P}(E)} \text{Energy}_{\alpha}(\mu))^{-1}

Giả sử với giá trị nào đó của \alpha>0 thì \text{Cap}_{\alpha}(E)>0. Theo tính chất của inf, tồn tại dãy độ đo xác suất \mu_n trên E sao cho chúng có năng lượng hữu hạn và

(1+1/n)(\text{Cap}_{\alpha}(E))^{-1}\ge \text{Energy}_{\alpha}(\mu_n)\ge (\text{Cap}_{\alpha}(E))^{-1}
Giả sử \mu là giới hạn riêng của (\mu_n), thế thì \mu cũng là độ đo xác suất trên E hơn nữa \text{Energy}_{\alpha}(\mu_n)\ge (\text{Cap}_{\alpha}(E))^{-1}

Tồn tại dãy con (\mu_{n_k}) hội tụ yếu về \mu nên với r>0 ta có
\iint_{|x-y|\ge r}|x-y|^{-\alpha}\mu(dx)\mu(dy)=\lim_{k\to\infty}\iint_{|x-y|\ge r}|x-y|^{-\alpha}\mu_{n_k}(dx)\mu_{n_k}(dy)\le (\text{Cap}_{\alpha}(E))^{-1}

Khi r\to 0, áp dụng Lebesgue’s dominated convergence theorem ta suy ra

\text{Energy}_{\alpha}(\mu)= (\text{Cap}_{\alpha}(E))^{-1}

Độ đo xác suất \mu như vậy gọi là equilibrium measure.

Frostman cũng chỉ ra được rằng

Định lý 3
Nếu \mu như vậy gọi là equilibrium measure trên tập compact E, thế thì với \mu hầu khắp nơi x\in\mathbb R^d thế thì

\text{Energy}_{\alpha}(\mu)=\int_{\mathbb R^d}|x-y|^{-\alpha}\mu(dy)

Chúng ta định nghĩa capacitary dimension của một tập compact E\subset \mathbb R^d là chận trên đúng của giá trị \alpha sao cho \text{Cap}_{\alpha}(E)>0, kí hiệu là \dim_{\mathcal C}(E)

Điều rất thú vị là Capacitary dimension và Hausdorff dimension trùng nhau, điều này giúp ta có thể đánh giá chiều Hausdorff thông qua việc đánh giá sự hữu hạn của năng lượng Bessel–Riesz \alpha-chiều ứng với equilibrium measure.

Định lý 4.
Với tập compact E\subset \mathbb R^d thế thì

\dim(E)=\dim_{\mathcal C}(E)

Thật vậy, giả sử \mu như vậy gọi là equilibrium measure trên tập compact E, thế thì
\mu(B_{\infty}(x,r)\le r^{\alpha}\int_{\mathbb R^d}|x-y|^{-\alpha}\mu(dy)=\text{Energy}_{\alpha}(\mu) r^{\alpha}
Theo định lý 2 thì \dim(E)\ge \alpha, điều này suy ra \dim(E)\ge \dim_{\mathcal C}(E). (*)

Thep định lý 3, nếu \beta<\dim(E) thế thì tồn tại độ đo xác suất \mu trên E sao cho

\mu(B_{\infty}(x,r))\le C r^{\beta}, \forall x\in \mathbb R^d, r\in(0,1)

Khi đó
\text{Energy}_{\gamma}(\mu)=\sum_{i=0}^{\infty}\iint_{\frac{\text{diam}(E)}{2^{i+1}}\le|x-y|\le \frac{\text{diam}(E)}{2^{i}}}|x-y|^{-\gamma}\mu(dx)\mu(dy)
\le \sum_{i=0}^{\infty} \frac{2^{\gamma(i+1)}}{(\text{diam}(E))^{\gamma}} \sup_{x\in\mathbb R^d}\mu(B_{\infty}(x,\frac{\text{diam}(E)}{2^{i}}))
\le C 2^{\gamma}(\text{diam}(E))^{\beta-\gamma} \sum_{i=0}^{\infty} 2^{(\gamma-\beta)i}
hội tụ khi \gamma<\beta. Khi đó \text{Cap}_{\gamma}(E)>0 với mọi \gamma< \dim(E) hay \dim_{\mathcal C}(E)\ge \gamma với mọi \gamma< \dim(E), suy ra \dim_{\mathcal C}(E)\ge \dim(E). (**)
Từ (*),(**) ta được điều phải chứng minh.

Categories: Probability Theory, Real Analysis Tags: , ,

Xác suất thuộc vào của chuyển động Brownian d-chiều

April 5, 2011 Leave a comment

Để bắt đầu, bạn hãy thử chứng minh  bổ đề đơn giản liên quan đến chận trên và chặn dưới của xác suất thuộc vào hình lập phương đóng B_{\infty}(a,\epsilon)\subset \mathbb R^d của chuyển động Brownian d-chiều (B(t))_{t\ge 0} trên một đoạn thời gian đóng

Bổ đề. Với \epsilon>0, a\in R^d, thế thì với mọi t\in [0,T], tồn tại các hằng số dương C_1,C_2 chỉ phụ thuộc vào T, a sao cho

C_1 \left(\min\{ \frac{\epsilon}{\sqrt{t}}, 1 \}\right)^d\le P(|B(t)-a|\le \epsilon)\le C_2 \left(\min\{ \frac{\epsilon}{\sqrt{t}}, 1 \} \right)^d

(ở đây |x|=||x||_{\infty}=\max_{1\le 1\le d}\{|x_i|\})
Gợi ý: sử dụng hàm phân phối và chặn các tích phân.
Bây giờ xét với lọc \sigma-đại số (\mathcal{F}_t)_{t\ge 0} phù hợp với (B(t))_{t\ge 0}, và quá trình ngẫu nhiên

M_t=E(\int_{\alpha}^{\alpha+\beta}\mathbf{1}_{\{|B(s)-a|\le 2\epsilon\}}ds | \mathcal{F}_t)

là martingale phù hợp với lọc (\mathcal{F}_t)_{t\ge 0}. Rõ ràng rằng
M_t\ge \int_t^{\alpha+\beta}P(|B(s)-a|\le 2\epsilon|\mathcal{F}_t)ds
\ge \mathbf{1}_{\{|B(t)-a|\le \epsilon\}} \int_t^{\alpha+\beta}P(|B(s)-a|\le 2\epsilon|\mathcal{F}_t)ds
\ge \mathbf{1}_{\{|B(t)-a|\le \epsilon\}} \int_t^{\alpha+\beta}P(|B(s)-B(t)|\le \epsilon|\mathcal{F}_t)ds
= \mathbf{1}_{\{|B(t)-a|\le \epsilon\}} \int_t^{\alpha+\beta}P(|B(s-t)|\le \epsilon)ds
\ge \mathbf{1}_{\{|B(t)-a|\le \epsilon\}} \int_0^{\beta}P(|B(u)|\le \epsilon)du
với mọi t\in[\alpha, \beta]

Áp dụng Bổ đề, ta có

M_t\ge C \kappa_0(\epsilon) \mathbf{1}_{\{|B(t)-a|\le \epsilon\}}
, với mọi t\in(\alpha, \beta)

trong đó

\kappa_0(\epsilon)=\left\{\begin{matrix} \epsilon,\ \ d=1\\ \epsilon^2 \ln_+(\epsilon^{-1}),\ \ d=2\\ \epsilon^{d+2},\ \ d\ge 3 \end{matrix}\right.

Bây giờ ta đặt \tau=\inf\{ t\in[\alpha, \beta]\ :\ |B(t)-a|\le\epsilon \}, là hitting time của chuyển động Brownian trên [\alpha, \beta] với hình lập phương đóng B_{\infty}(a,\epsilon)

Khi đó

E(M_{\tau}\mathbf{1}_{\{\tau < \infty\}})\ge C \kappa_0(\epsilon) P(\inf_{t\in[\alpha,\beta]}\{|B(t)-a|\le \epsilon\})

Từ tính bị chặn của M_t và áp dụng Optional stopping theorem ta thu được kết quả đẹp về ước lượng chặn trên của hitting probability

Định lý. Tồn tại hằng số C sao cho

P(\inf_{t\in[\alpha,\beta]}\{|B(t)-a|\le \epsilon\})\le C \kappa(\epsilon)

trong đó \kappa(\epsilon)=\left\{\begin{matrix} 1,\ \ d=1\\ \frac{1}{\ln_+(1/\epsilon)},\ \ d=2\\ \epsilon^{d-2},\ \ d\ge 3 \end{matrix}\right.

Categories: Probability Theory Tags: ,
Follow

Get every new post delivered to your Inbox.