The main theme of this thesis is to develop de Finetti type theorems in noncommutative probability. In noncommutative area, there are independence relations other than classi- cal independence, e.g. Voiculescu’s free independence, Boolean independence and Muraki’s monotone independence. Free analogues of de Finetti type theorems were discovered by Ko ̈stler and Speicher and were developed by Banica, Curran and Speicher. Here, we will define noncommutative distributional symmetries for Boolean and monotone independence and we will prove de Finetti type theorems for them. These distributional symmetries are defined via coactions of quantum structures including Woronowicz C∗-algebra and So ltan’s quantum families of maps. We show that the joint distribution of an infinite sequence of noncommutative random variables satisfies boolean exchangeability is equivalent to the fact that the sequence of the random variables is identically distributed and boolean independent with respect to the conditional expectation onto its tail algebra. Then, we define noncom- mutative versions of spreadability and show Ryll-Nardzewski type theorems for monotone independence and boolean independence. We will show that, roughly speaking, an infinite bilateral sequence of random variables is monotonically(boolean) spreadable if and only if the variables are identically distributed and monotone(boolean) with respect to the conditional expectation onto its tail algebra. In the end of this thesis, we will prove general de Finetti theorems for classical, free and boolean independence. Our general de Finetti theorems work for non-easy quantum groups, which generalizes a recent work of Banica, Curran and Spe- icher. For infinite sequences, we determine maximal distributional symmetries which means the corresponding de Finetti theorem fails if the sequence satisfies more symmetries other than the maximal one.

The framework of this thesis is Voiculescu's free probability theory. The main theme is the application of bialgebras, particularly Woronowicz-Kac compact quantum groups, in free probability. A large part of this thesis is concerned with the class of ``easy'' compact quantum groups, introduced by Banica and Speicher. After a brief background section, we construct two new "hyperoctahedral" series of easy quantum groups and establish some classification results. In Chapter 4, we present a unified approach to de Finetti type results for the class of easy quantum groups. In this way we recover the classical results of de Finetti and Freedman on exchangeable and rotatable sequences, and the recent free probability analogues of Koestler-Speicher and Curran for quantum exchangeable and quantum rotatable sequences, within a common framework. In Chapter 5 we introduce a notion of quantum spreadability, defined as invariance under certain objects which we call quantum increasing sequence spaces, and establish a free analogue of a famous theorem of Ryll-Nardzewski. We then consider some well-known results of Diaconis-Shahshahani on the limiting distribution of the trace of the k-th power of U, where U is uniformly chosen from O(N) or S(N), within the context of easy quantum groups. We recover their results and establish some surprising free analogues. In Chapter 7 we prove asymptotic freeness results for Haar quantum unitary random matrices. In the final chapter we use (non-coassociative) infinitesimal bialgebras to prove analytic subordination results in free probability.

This thesis compiles several results under the general theme of noncommutative generalized Brownian motion with multiple processes.

In our introduction, Chapter 1, we motivate our results with some background material. Specifically, we provide brief introductions to classical Brownian motion and noncommutative probability theory, and then we connect these two subjects with a discussion of noncommutative Brownian motions.

In Chapter 2, we expand upon the framework for generalized Brownian motions with multiple processes established by Guta. In particular, we discuss symmetric Fock spaces, colored pair partitions, and colored broken pair partitions. We then prove multidimensional generalizations of some results which were proven by Guta and Maassen in the case of a single process.

In Chapter 3, we review Thoma’s Theorem on characters of the infinite symmetric group and Vershik and Kerov’s factor representations of symmetric groups. We then recall Bozejko and Guta's work on generalized Brownian motions with one process associated to the infinite symmetric group, focusing on their formula for the joint moments associated to these generalized Brownian motions. We then proceed to consider generalized Brownian motions indexed by a two-element set arise from tensor products of factor rep- resentations of the infinite symmetric group, providing a simple formula for the joint moments in this context.

In Chapter 4, we consider generalized Brownian motions connected to spherical representations of a pair of infinite symmetric groups. By defining a directed graph associated to a two-colored pair partition, we state and prove a formula for the joint moments connected with these generalized Brownian motion.

In Chapter 5, we continue the study of the generalized Brownian motions related to spherical functions of infinite symmetric groups, specializing to a one-parameter family of the spherical representations. In this setting, we show that the generalized Brownian motions give bounded operators, and we investigate related von Neumann algebras.

Finally, in Chapter 6, we generalize Guta’s q-product and prove a central limit theorem in the spirit of that of Guta.

We rigorously analyze numerical methods for (approximately) computing the eigenvalues and eigenvectors of a matrix. Our main results are the following:\begin{itemize} \item \emph{Spectral bisection.} We show that a backward-stable solution to the eigenvalue problem can be obtained by a randomized algorithm in nearly matrix-multiplication time on any input. More specifically, we show that for every $\delta>0$, there is a randomized version of the spectral bisection algorithm that, on any input $A\in \bC$, with probability $1-O(1/n)$, finds matrices $V, D\in \bC^{n\times n}$ with $V$ invertible and $D$ diagonal such that $\|A-VDV^{-1}\|\leq \delta \|A\|$, using $O(T_\MM(n)\log^2(n/\delta))$ arithmetic operations, in finite arithmetic with $O(\log^4(n/\delta)\log n)$ bits of precision. Here $T_\MM(n)$ is the number of arithmetic operations required to multiply two $n\times n$ complex matrices numerically stably, known to satisfy $T_\MM(n)=O(n^{\omega+\eta})$ for every $\eta>0$ where $\omega$ is the exponent of matrix multiplication. \item \emph{The Hessenberg shifted QR algorithm.} We introduce a randomized shifting strategy for the Hessenberg QR algorithm, for which we prove (in the finite precision arithmetic model) rapid global convergence. It follows from our results, that for any $\delta , \phi>0$, a randomized version of the shifted Hessenberg QR algorithm can be used to compute, on any input $A\in \bC^{n\times n}$, with probability at least $1-\phi$, matrices $U, T\in \bC^{n\times n}$ with $U$ unitary and $T$ upper triangular, such that $\|A-UTU^*\|\leq \delta \|A\|,$ using $O(n^3\log(n/(\delta\phi))^2 \log \log (n/(\delta\phi)) )$ arithmetic operations performed using $O(\log^2(n/(\delta \phi))\log \log (n/(\delta\phi)))$ bits of precision. This provides the first rapidly globally convergent shifting strategy in the nonsymmetric case, which was an open problem even under the assumption of exact arithmetic. \iffalse The key ideas in the analysis are: (1) to use certain higher degree shifts to dampen transient effects due to nonnormality (2) to characterize and detect slowly converging trajectories with respect to such shifts in terms of certain symmetry considerations, and to break this symmetry explicitly in the shifting strategy (3) to introduce a criteria for early deflation to deal with potential numerical stabilities that arise from using high degree shifts. \fi \item \emph{The Lanczos algorithm.} We analyze the Lanczos algorithm where the initial vector $u$ is sampled uniformly at random from the unit sphere $\mathbb{S}^{n-1}$, and show that when run on a Hermitian input $A\in \bC^{n\times n}$ for $c_1\log n$ iterations (where $c_1$ depends on some coarse global property of the spectrum of $A$ but not on $n$) its outputs (both the Jacobi coefficients and the Ritz values) are exponentially concentrated around their medians. Our techniques also allow us to understand the location of the output in the regime of $k= O(\log n)$ iterations, and in particular we use them to show that the Lanczos algorithm can fail to identify outlying eigenvalues when run for less than $c_2\log n$, where $c_2$ depends again on the same global property of the spectrum of $A$ used to determine $c_1$. \end{itemize}

A key ingredient in showing the first two results is a smoothed analysis of the eigenvector condition number and minimum eigenvalue gap of a matrix. In this direction we show a general result that might be of independent interest in random matrix theory: if one adds independent (absolutely continuous with respect to the Lebesgue measure) random variables of small variance to the entries of an arbitrary matrix $A \in \mathbb{C}^{n\times n}$, with high probability, the resulting matrix $A' $ will have (relatively) stable eigenvenvalues and eigenvectors.