Tensor products of M random unitary matrices of size N from the circular
unitary ensemble are investigated. We show that the spectral statistics of the
tensor product of random matrices becomes Poissonian if M=2, N become large or
M become large and N=2.
We study the maximal displacement of branching random walks in a class of
time inhomogeneous environments. Specifically, binary branching random walks
with Gaussian increments will be considered, where the variances of the
increments change over time macroscopically. We find the asymptotics of the
maximum up to an $O_P(1)$ (stochastically bounded) error, and focus on the
following phenomena: the profile of the variance matters, both to the leading
(velocity) term and to the logarithmic correction term, and the latter exhibits
a phase transition.
Let S_n be the permutation group on n elements, and consider a random walk on
S_n whose step distribution is uniform on k-cycles. We prove a well-known
conjecture that the mixing time of this process is (1/k) n \log n, with
threshold of width linear in n. Our proofs are elementary and purely
probabilistic, and do not appeal to the representation theory of S_n.
Let $\mathbb{T}$ denote a rooted $b$-ary tree and let $\{S_v\}_{v\in
\mathbb{T}}$ denote a branching random walk indexed by the vertices of the
tree, where the increments are i.i.d. and possess a logarithmic moment
generating function $\Lambda(\cdot)$. Let $m_n$ denote the minimum of the
variables $S_v$ over all vertices at the $n$th generation, denoted by
$\mathbb{D}_n$. Under mild conditions, $m_n/n$ converges almost surely to a
constant, which for convenience may be taken to be 0.
We consider the quenched and averaged (or annealed) large deviation rate
functions $I_q$ and $I_a$ for space-time and (the usual) space-only RWRE on
$\mathbb{Z}^d$. By Jensen's inequality, $I_a\leq I_q$.
In the space-time case, when $d\geq3+1$, $I_q$ and $I_a$ are known to be
equal on an open set containing the typical velocity $\xi_o$. When $d=1+1$, we
prove that $I_q$ and $I_a$ are equal only at $\xi_o$. Similarly, when $d=2+1$,
we show that $I_a<I_q$ on a punctured neighborhood of $\xi_o$.
We present a deterministic algorithm that given a tree T with n vertices, a
starting vertex v and a slackness parameter epsilon > 0, estimates within an
additive error of epsilon the cover and return time, namely, the expected time
it takes a simple random walk that starts at v to visit all vertices of T and
return to v. The running time of our algorithm is polynomial in n/epsilon, and
hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how
the algorithm can be extended to estimate the expected cover (without return)
time on trees.