In this thesis, we study the exact eigenvalue distribution of product of independent rectangular complex Gaussian matrices and also that of product of independent truncated Haar unitary matrices and inverses of truncated Haar unitary matrices. The eigenvalues of these random matrices form determinantal point processes on the complex plane. We also study the limiting expected empirical distribution of appropriately scaled eigenvalues of those matrices as the size of matrices go to infinity. We give the first example of a random matrix whose eigenvalues form a non-rotation invariant determinantal point process on the plane. The second theme of this thesis is infinite products of random matrices. We study the asymptotic behaviour of singular values and absolute values of eigenvalues of product of i .i .d matrices of fixed size, as the number of matrices in the product in-creases to infinity. In the special case of isotropic random matrices, We derive the asymptotic joint probability density of the singular values and also that of the absolute values of eigenvalues of product of right isotropic random matrices and show them to be equal. As a corollary of these results, we show probability that all the eigenvalues of product of certain i .i .d real random matrices of fixed size converges to one, as the number of matrices in the product increases to infinity.

No description available.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第25436号 / 情博第874号 / 京都大学大学院情報学研究科先端数理科学専攻 / (主査)准教授 白石 大典, 教授 磯 祐介, 教授 木上 淳 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

In this thesis, we study the existence of random periodic solutions of random dynamical systems (RDS) by geometric and topological approach. We employed an extension of ergodic theory to random setting to prove that a random invariant set with some kind of dissipative structure, can be expressed as union of random periodic curves. We extensively characterize the dissipative structure by random invariant measures and Lyapunov exponents. For stochastic flows induced by stochastic differential equations (SDEs), we studied the dissipative structure by two point motion of the SDE and prove the existence exponential stable random periodic solutions.

<p>This thesis studies non-nearest-neighbor random walks in random environments (RWRE) on the integers and on the d-dimensional integer lattic that are drawn in an i.i.d. way according to a Dirichlet distribution. We complete a characterization of recurrence and transience in a given direction for random walks in Dirichlet environments (RWDE) by proving directional recurrence in the case where the Dirichlet parameters are balanced and the annealed drift is zero. As a step toward this, we prove a 0-1 law for directional transience of i.i.d. RWRE on the 2-dimensional integer lattice with bounded jumps. Such a 0-1 law was proven by Zerner and Merkl for nearest-neighbor RWRE in 2001, and Zerner gave a simpler proof in 2007. We modify the latter argument to allow for bounded jumps. We then characterize ballisticity, or nonzero liiting velocity, of transienct RWDE on the integers. It turns out that ballisticity is controlled by two parameters, kappa0 and kappa1. The parameter kappa0, which controls finite traps, is known to characterize ballisticity for nearest-neighbor RWDE on the d-dimensional integer lattice for dimension d at least 3, where transient walks are ballistic if and only if kappa0 is greater than 1. The parameter kappa1, which controls large-scale backtracking, is known to characterize ballisticity for nearest-neighbor RWDE on the one-dimensional integer lattice, where transient walks are ballistic if and only if the absolute value of kappa1 is greater than 1. We show that in our model, transient walks are ballistic if and only if both parameters are greater than 1. Our characterization is thus a mixture of known characterizations of ballisticity for nearest-neighbor one-dimensional and higher-dimensional cases. We also prove more detailed theorems that help us better understand the phenomena affecting ballisticity.</p>

In this dissertation, we study the complicated dynamics of two classes of systems: Anosov systems driven by an external force and partially hyperbolic systems driven by an external force. For smooth Anosov systems driven by an external force, we first study the random specification property, which is on the approximation of an N−spaced arbitrary long finite random orbit segments within given precision by a random periodic point. We prove that if such system is topological mixing on fibers, then it has the random specification property. Furthermore, we prove that the homeomorphism induced by such a system on the space of random probability measures also has the specification property. We note that the random specification property implies the positivity of topological fiber entropy. Secondly, we show that if the system is topological mixing on fibers, then its past and future random correlation for Hölder observable functions decay exponentially with respect to the system and the unique random SRB measure. For smooth partially hyperbolic systems driven by an external force, we prove the existence of the random Gibbs u−state, which has absolutely continuous conditional measure on the strong unstable manifolds.

Recently, there has been a renewed interest in code based cryptosystems. Amongst the reasons for this interest is that they have shown to be resistant to quantum at- tacks, making them candidates for post-quantum cryptosystems. In fact, the National Institute of Standards and Technology is currently considering candidates for secure communication in the post-quantum era. Three of the proposals are code based cryp- tosystems. Other reasons for this renewed interest include e cient encryption and decryption. In this dissertation, new code based cryptosystems (symmetric key and public key) are presented that use high rate codes and have small key sizes. Hence they overcome the drawbacks of code based cryptosystems (low information rate and very large key size). The techniques used in designing these cryptosystems include random bit/block deletions, random bit insertions, random interleaving, and random bit ipping. An advantage of the proposed cryptosystems over other code based cryp- tosystems is that the code can be/is not secret. These cryptosystems are among the rst with this advantage. Having a public code eliminates the need for permutation and scrambling matrices. The absence of permutation and scrambling matrices results in a signi cant reduction in the key size. In fact, it is shown that with simple random bit ipping and interleaving the key size is comparable to well known symmetric key cryptosystems in use today such as Advanced Encryption Standard (AES). The security of the new cryptosystems are analysed. It is shown that they are immune against previously proposed attacks for code based cryptosystems. This is because scrambling or permutation matrices are not used and the random bit ipping is beyond the error correcting capability of the code. It is also shown that having a public code still provides a good level of security. This is proved in two ways, by nding the probability of an adversary being able to break the cryptosystem and showing that this probability is extremely small, and showing that the cryptosystem has indistinguishability against a chosen plaintext attack (i.e. is IND-CPA secure). IND-CPA security is among the primary necessities for a cryptosystem to be practical. This means that a ciphertext reveals no information about the corresponding plaintext other than its length. It is also shown that having a public code results in smaller key sizes. / Graduate

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

The paper is dedicated to the modeling and the simulation of random processes and fields. Using the concept and the theory of weakly correlated functions a consistent representation of sufficiently smooth random processes will be derived. Special applications will be given with respect to the simulation of road surfaces in vehicle dynamics and to the confirmation of theoretical results with respect to the zeros of random polynomials.