Search

This paper introduces a novel and general algorithm for approximately counting the number of orbits under group actions. The method is based on combining the Burnside process and importance sampling. Specializing to unitriangular groups yields an efficient algorithm for estimating the number of conjugacy classes of such groups., Comment: 20 pages, 2 figures

P\'olya trees are rooted, unlabeled trees on $n$ vertices. This paper gives an efficient, new way to generate P\'olya trees. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with `reality'. Along the way, we give a product formula for the number of rooted labeled trees preserved by a given automorphism; this refines Cayley's formula.

Let $G_{k,n}$ be a group of permutations of $kn$ objects which permutes things independently in disjoint blocks of size $k$ and then permutes the blocks. We investigate the probabilistic and/or enumerative aspects of random elements of $G_{k,n}$. This includes novel limit theorems for fixed points, cycles of various lengths, number of cycles and inversions. The limits are compound Poisson distributions with interesting dependence structure., Comment: 24 pages, no figures

Let $G_{n,k}$ be the group of permutations of $\{1,2,\ldots, kn\}$ that permutes the first $k$ symbols arbitrarily, then the next $k$ symbols and so on through the last $k$ symbols. Finally the $n$ blocks of size $k$ are permuted in an arbitrary way. For $\sigma$ chosen uniformly in $G_{n,k}$, let $L_{n,k}$ be the length of the longest increasing subsequence in $\sigma$. For $k,n$ growing, we determine that the limiting mean of $L_{n,k}$ is asymptotic to $4\sqrt{nk}$. This is different from parallel variations of the Vershik-Kerov theorem for colored permutations., Comment: 8 pages

The Tsetlin library is a well-studied Markov chain on the symmetric group $S_n$. It has stationary distribution $\pi(\sigma)$ the Luce model, a nonuniform distribution on $S_n$, which appears in psychology, horse race betting, and tournament poker. Simple enumerative questions, such as ``what is the distribution of the top $k$ cards?'' or ``what is the distribution of the bottom $k$ cards?'' are long open. We settle these questions and draw attention to a host of parallel questions on the extension to the chambers of a hyperplane arrangement., Comment: 23 pages, 1 figure

For $N\in\mathbb{N}$, let $\pi_N$ be the law of the number of fixed points of a random permutation of $\{1, 2, ..., N\}$. Let $\mathcal{P}$ be a Poisson law of parameter 1.A classical result shows that $\pi_N$ converges to $\mathcal{P}$ for large $N$ and indeed in total variation $$\left\Vert \pi_N-\mathcal{P}\right\Vert_{\mathrm{tv}} \leq \frac{2^N}{(N+1)!}$$ This implies that $\pi_N$ and $\mathcal{P}$ can be coupled to at least this accuracy. This paper constructs such a coupling (a long open problem) using the machinery of intertwining of two Markov chains. This method shows promise for related problems of random matrix theory.

Let $G$ be a finite group. Let $H, K$ be subgroups of $G$ and $H \backslash G / K$ the double coset space. Let $Q$ be a probability on $G$ which is constant on conjugacy classes ($Q(s^{-1} t s) = Q(t)$). The random walk driven by $Q$ on $G$ projects to a Markov chain on $H \backslash G /K$. This allows analysis of the lumped chain using the representation theory of $G$. Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $GL_n(q)$ onto a Markov chain on $S_n$ via the Bruhat decomposition. The chain on $S_n$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets. Some extensions and examples of double coset Markov chains with $G$ a compact group are discussed., Comment: working draft, comments welcome!

The Rado graph, also known as the random graph $G(\infty, p)$, is a classical limit object for finite graphs. We study natural ball walks as a way of understanding the geometry of this graph. For the walk started at $i$, we show that order $\log_2^*i$ steps are sufficient, and for infinitely many $i$, necessary for convergence to stationarity. The proof involves an application of Hardy's inequality for trees., Comment: 43 pages

The two of us have shared a fascination with James Victor Uspensky's 1937 textbook $Introduction \, to \, Mathematical \, Probability$ ever since our graduate student days: it contains many interesting results not found in other books on the same subject in the English language, together with many non-trivial examples, all clearly stated with careful proofs. We present some of Uspensky's gems to a modern audience hoping to tempt others to read Uspensky for themselves, as well as report on a few of the other mathematical topics he also wrote about (for example, his book on number theory contains early results about perfect shuffles). Uspensky led an interesting life: a member of the Russian Academy of Sciences, he spoke at the 1924 International Congress of Mathematicians in Toronto before leaving Russia in 1929 and coming to the US and Stanford. Comparatively little has been written about him in English; the second half of this paper attempts to remedy this., Comment: 49 pages

Consider two independent Erd\H{o}s-R\'enyi $G(N,1/2)$ graphs. We show that with probability tending to $1$ as $N\to\infty$, the largest induced isomorphic subgraph has size either $\lfloor x_N-\varepsilon_N\rfloor$ or $\lfloor x_N+\varepsilon_N \rfloor$, where $x_N=4\log_2 N -2 \log_2 \log_2 N - 2\log_2(4/e)+1$ and $\varepsilon_N = (4\log_2 N)^{-1/2}$. Using similar techniques, we also show that if $\Gamma_1$ and $\Gamma_2$ are independent $G(n,1/2)$ and $G(N,1/2)$ random graphs, then $\Gamma_2$ contains an isomorphic copy of $\Gamma_1$ as an induced subgraph with high probability if $n\le \lfloor y_N - \varepsilon_N \rfloor$ and does not contain an isomorphic copy of $\Gamma_1$ as an induced subgraph with high probability if $n>\lfloor y_N+\varepsilon_N \rfloor$, where $y_N=2\log_2 N+1$ and $\varepsilon_N$ is as above., Comment: 17 pages. To appear in J. Combin. Theory B

By studying the commuting graphs of conjugacy classes of the sequence of Heisenberg groups $H_{2n+1}(p)$ and their limit $H_\infty(p)$ we find pseudo-random behavior (and the random graph in the limiting case). This makes a nice case study for transfer of information between finite and infinite objects. Some of this behavior transfers to the problem of understanding what makes understanding the character theory of the uni-upper-triangular group (mod p) "wild". Our investigations in this paper may be seen as a meditation on the question: is randomness simple or is it complicated?

This paper makes three contributions to estimating the number of perfect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm works in polynomial time for dense bipartite graphs. More carefully, our algorithm gives a $(1\pm\epsilon)$-approximation for the number of perfect matchings of a $\lambda$-dense bipartite graph, using $O(n^{\frac{1-2\lambda}{\lambda}\epsilon^{-2}})$ samples. With size $n$ on each side and for $\frac{1}{2}>\lambda>0$, a $\lambda$-dense bipartite graph has all degrees greater than $(\lambda+\frac{1}{2})n$. Second, practical applications of the algorithm require many calls to matching algorithms. A novel preprocessing step is provided which makes significant improvements. Third, three applications are provided. The first is for counting Latin squares, the second is a practical way of computing the greedy algorithm for a card-guessing game with feedback, and the third is for stochastic block models. In all three examples, sequential importance sampling allows treating practical problems of reasonably large sizes., Comment: To appear in Annals of Applied Probability

This is a contribution for the discussion on "A Gibbs sampler for a class of random convex polytopes" by Pierre E. Jacob, Ruobin Gong, Paul T. Edlefsen and Arthur P. Dempster to appear in the Journal of American Statistical Association., Comment: 5 pages

Let $H$ and $K$ be subgroups of a finite group $G$. Pick $g \in G$ uniformly at random. We study the distribution induced on double cosets. Three examples are treated in detail: 1) $H = K = $ the Borel subgroup in $GL_n(\mathbb{F}_q)$. This leads to new theorems for Mallows measure on permutations and new insights into the LU matrix factorization. 2) The double cosets of the hyperoctahedral group inside $S_{2n}$, which leads to new applications of the Ewens's sampling formula of mathematical genetics. 3) Finally, if $H$ and $K$ are parabolic subgroups of $S_n$, the double cosets are `contingency tables', studied by statisticians for the past 100 years., Comment: 46 pages, 1 figure; minor edits

We study a natural Markov chain on $\{0,1,\cdots,n\}$ with eigenvectors the Hahn polynomials. This explicit diagonalization makes it possible to get sharp rates of convergence to stationarity. The process, the Burnside process, is a special case of the celebrated `Swendsen-Wang' or `data augmentation' algorithm. The description involves the beta-binomial distribution and Mallows model on permutations. It introduces a useful generalization of the Burnside process., Comment: 29 pages; added Section 6 on a continuous limit of the Burnside process; improved the range of the parameter in Theorem 5.2; minor edits

In simple card games, cards are dealt one at a time and the player guesses each card sequentially. We study problems where feedback (e.g. correct/incorrect) is given after each guess. For decks with repeated values (as in blackjack where suits do not matter) the optimal strategy differs from the "greedy strategy" (of guessing a most likely card each round). Further, both optimal and greedy strategies are far too complicated for real time use by human players. Our main results show that simple heuristics perform close to optimal., Comment: 20 pages, minor typos corrected, to appear in the American Mathematical Monthly excluding Section 6

Consider gambler's ruin with three players, 1, 2, and 3, having initial capitals $A$, $B$, and $C$ units. At each round a pair of players is chosen (uniformly at random) and a fair coin flip is made resulting in the transfer of one unit between these two players. Eventually, one of the players is eliminated and play continues with the remaining two. Let $\sigma\in S_3$ be the elimination order (e.g., $\sigma=132$ means player 1 is eliminated first and player 3 is eliminated second, leaving player 2 with $A+B+C$ units). We seek approximations (and exact formulas) for the elimination order probabilities $P_{A,B,C}(\sigma)$. Exact, as well as arbitrarily precise, computation of these probabilities is possible when $N:=A+B+C$ is not too large. Linear interpolation can then give reasonable approximations for large $N$. One frequently used approximation, the independent chip model (ICM), is shown to be inadequate. A regression adjustment is proposed, which seems to give good approximations to the elimination order probabilities., Comment: 32 pages, 5 figure files

Consider the following experiment: a deck with $m$ copies of $n$ different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn. Each time a guess is made, some amount of "feedback" is given. For example, one could tell the guesser the true identity of the card they just guessed (the complete feedback model) or they could be told nothing at all (the no feedback model). In this paper we explore a partial feedback model, where upon guessing a card, the guesser is only told whether or not their guess was correct. We show in this setting that, uniformly in $n$, at most $m+O(m^{3/4}\log m)$ cards can be guessed correctly in expectation. This resolves a question of Diaconis and Graham from 1981, where even the $m=2$ case was open., Comment: 24 pages; minor errors corrected

Squaring and adding $\pm 1$ mod p generates a curiously intractable random walk. A similar process over the finite field $\mathbf{F}_q$ (with $q=2^d$) leads to novel connections between elementary Galois theory and probability., Comment: 16 pages. Comments are welcome!

IRAS 12272-6240 is a complex star forming region with a compact massive dense clump and several associated masers, located at a well-determined distance of $d=9.3$ kpc from the Sun. For this study, we obtained sub-arcsec broad- and narrow-band near-IR imaging and low-resolution spectroscopy with the Baade/Magellan telescope and its camera PANIC. Mosaics of size $2 \times 2$ square arcmin in the $JHK_s$ bands and with narrow-band filters centred in the 2.12 $\mu$m H$_2$ and 2.17 $\mu$m Br$\gamma$ lines were analysed in combination with HI-GAL/{\sl Herschel} and archive IRAC/{\sl Spitzer} and {\sl WISE} observations. We found that the compact dense clump houses two Class~I YSOs that probably form a 21 kAU-wide binary system. Its combined 1 to 1200 $\mu$m SED is consistent with an O9V central star with a $10^{-2} M_\odot$ disc and a $1.3 \times 10^4 M_\odot$ dust envelope. Its total luminosity is $8.5 \times 10^4 L_\odot$. A series of shocked H$_2$ emission knots are found in its close vicinity, confirming the presence of outflows. IRAS 12272-6240 is at the centre of an embedded cluster with a mean age of 1 Myr and 2.6 pc in size that contains more than 150 stars. At its nucleus, we found a more compact and considerably younger sub-cluster containing the YSOs. We also identified and classified the O-type central stars of two dusty radio/IR HII regions flanking the protostars. Our results confirm that these elements form a single giant young complex where massive star formation processes started some 1 million years ago and is still active., Comment: 14 pages, 13 figures, Accepted by MNRAS

We show that the convergence of finite state space Markov chains to stationarity can often be considerably speeded up by alternating every step of the chain with a deterministic move. Under fairly general conditions, we show that not only do such schemes exist, they are numerous., Comment: 22 pages. To appear in Probab. Theory Related Fields, special issue in honor of Harry Kesten. This revision has some minor corrections and a new proposition due to Jimmy He in the section on open problems

Let $x_1,\ldots,x_n$ be a fixed sequence of real numbers. At each stage, pick two indices $I$ and $J$ uniformly at random and replace $x_I$, $x_J$ by $(x_I+x_J)/2$, $(x_I+x_J)/2$. Clearly all the coordinates converge to $(x_1+\cdots+x_n)/n$. We determine the rate of convergence, establishing a sharp "cutoff" transition, answering a question of Jean Bourgain., Comment: 21 pages, 2 figures. Final version. To appear in Ann. Probab

We introduce and study randomized sequential importance sampling algorithms for estimating the number of perfect matchings in bipartite graphs. In analyzing their performance, we establish various non-standard central limit theorems. We expect our methods to be useful for other applied problems., Comment: v2: minor improvements

Gambler's ruin estimates can be viewed as harmonic measure estimates for finite Markov chains which are absorbed (or killed) at boundary points. We relate such estimates to properties of the underlying chain and its Doob transform. Precisely, we show that gambler's ruin estimates reduce to a good understanding of the Perron-Frobenius eigenfunction and eigenvalue whenever the underlying chain and its Doob transform are Harnack Markov chains. Finite inner-uniform domains (say, in the square grid $\mathbb Z^n$) provide a large class of examples where these ideas apply and lead to detailed estimates. In general, understanding the behavior of the Perron-Frobenius eigenfunction remains a challenge.

For a relatively large class of well-behaved absorbing (or killed) finite Markov chains, we give detailed quantitative estimates regarding the behavior of the chain before it is absorbed (or killed). Typical examples are random walks on box-like finite subsets of the square lattice $\mathbb Z^d$ absorbed (or killed) at the boundary. The analysis is based on Poincar\'e, Nash, and Harnack inequalities, moderate growth, and on the notions of John and inner-uniform domains.

We analyze families of Markov chains that arise from decomposing tensor products of irreducible representations. This illuminates the Burnside-Brauer Theorem for building irreducible representations, the McKay Correspondence, and Pitman's 2M-X Theorem. The chains are explicitly diagonalizable, and we use the eigenvalues/eigenvectors to give sharp rates of convergence for the associated random walks. For modular representations, the chains are not reversible, and the analytical details are surprisingly intricate. In the quantum group case, the chains fail to be diagonalizable, but a novel analysis using generalized eigenvectors proves successful.

The problem of making practical, useful goodness of fit tests in the Bayesian paradigm is largely open. We introduce a class of special cases (testing for uniformity: have the cards been shuffled enough; does my random generator work) and a class of sensible Bayes tests inspired by Mumford, Wu and Zhu. Calculating these tests presents the challenge of 'doubly intractable distributions'. In present circumstances, modern MCMC techniques are up to the challenge. But many other problems remain. Our paper is didactic, we hope to induce the reader to help take it further., Comment: 22 pages, 5 figures; added references

Diaconis and Griffiths (2014) study the multivariate Krawtchouk polynomials orthogonal on the multinomial distribution. In this paper we derive the reproducing kernel orthogonal polynomials Q_n(x,y};N,p) on the multinomial distribution which are sums of products of orthonormal polynomials in x and y of fixed total degree n=0,1,.., N. sum_{n=0}^N rho^nQ_n(x,y);N,p) arises naturally from a probabilistic argument. An application to a multinomial goodness of fit test is developed, where the chi-squared test statistic is decomposed into orthogonal components which test the order of fit. A new duplication formula for the reproducing kernel polynomials in terms of the 1-dimensional Krawtchouk polynomials is derived. The duplication formula allows a Lancaster characterization of all reversible Markov chains with a multinomial stationary distribution whose eigenvectors are multivariate Krawtchouk polynomials and where eigenvalues are repeated within the same total degree. The \chi^2 cutoff time, and total variation cutoff time is investigated in such chains. Emphasis throughout the paper is on a probabilistic understanding of the polynomials and their applications, particularly to Markov chains.

We propose a model of card shuffling where a pack of cards, spread as points on a square table, are repeatedly gathered locally at random spots and then spread towards a random direction. A shuffling of the cards is then obtained by arranging the cards by their increasing $x$-coordinate values. When there are $m$ cards on the table we show that this random ordering gets mixed in time $O\left(\log m\right)$. Explicit constants are evaluated in a diffusion limit when the position of $m$ cards evolves as an interesting $2m$-dimensional non-reversible reflected jump diffusion in time. Our main technique involves the use of multidimensional Skorokhod maps for double reflections in $[0,1]^2$ in taking the discrete to continuous limit. The limiting computations are then based on the planar Brownian motion and properties of Bessel processes., Comment: 27 pages, 2 figures

To constrain models of high-mass star formation, the Herschel/HOBYS KP aims at discovering massive dense cores (MDCs) able to host the high-mass analogs of low-mass prestellar cores, which have been searched for over the past decade. We here focus on NGC6334, one of the best-studied HOBYS molecular cloud complexes. We used Herschel PACS and SPIRE 70-500mu images of the NGC6334 complex complemented with (sub)millimeter and mid-infrared data. We built a complete procedure to extract ~0.1 pc dense cores with the getsources software, which simultaneously measures their far-infrared to millimeter fluxes. We carefully estimated the temperatures and masses of these dense cores from their SEDs. A cross-correlation with high-mass star formation signposts suggests a mass threshold of 75Msun for MDCs in NGC6334. MDCs have temperatures of 9.5-40K, masses of 75-1000Msun, and densities of 10^5-10^8cm-3. Their mid-IR emission is used to separate 6 IR-bright and 10 IR-quiet protostellar MDCs while their 70mu emission strength, with respect to fitted SEDs, helps identify 16 starless MDC candidates. The ability of the latter to host high-mass prestellar cores is investigated here and remains questionable. An increase in mass and density from the starless to the IR-quiet and IR-bright phases suggests that the protostars and MDCs simultaneously grow in mass. The statistical lifetimes of the high-mass prestellar and protostellar core phases, estimated to be 1-7x10^4yr and at most 3x10^5yr respectively, suggest a dynamical scenario of high-mass star formation. The present study provides good mass estimates for a statistically significant sample, covering the earliest phases of high-mass star formation. High-mass prestellar cores may not exist in NGC6334, favoring a scenario presented here, which simultaneously forms clouds and high-mass protostars., Comment: 36 pages, 14 figures, accepted by A&A. Complete appendix could be requested to F. Motte

We explore the link between combinatorics and probability generated by the question "What does a random parking function look like?" This gives rise to novel probabilistic interpretations of some elegant, known generating functions. It leads to new combinatorics: how many parking functions begin with $i$? We classify features (e.g., the full descent pattern) of parking functions that have exactly the same distribution among parking functions as among all functions. Finally, we develop the link between parking functions and Brownian excursion theory to give examples where the two ensembles differ., Comment: 40 pages

This paper does three things: It proves a central limit theorem for novel permutation statistics (for example, the number of descents plus the number of descents in the inverse). It provides a clear illustration of a new approach to proving central limit theorems more generally. It gives us an opportunity to acknowledge the work of our teacher and friend B. V. Rao., Comment: 10 pages. To appear in a special issue of the Indian Journal of Pure and Applied Mathematics in honor of Professor B. V. Rao

The accretion mechanism producing the short flares observed from the Supergiant Fast X-ray Transients (SFXT) is still highly debated and forms a major part in our attempts to place these X-ray binaries in the wider context of the High Mass X-ray Binaries. We report on a 216 ks INTEGRAL observation of the SFXT IGR J16328-4726 (August 24-27, 2014) simultaneous with two fixed-time observations with XMM Newton (33ks and 20ks) performed around the putative periastron passage, in order to investigate the accretion regime and the wind properties during this orbital phase. During these observations, the source has shown luminosity variations, from 4x10^{34} erg/s to 10^{36} erg/s, linked to spectral properties changes. The soft X-ray continuum is well modeled by a power law with a photon index varying from 1.2 up to 1.7 and with high values of the column density in the range 2-4x10^{23}/cm^2. We report on the presence of iron lines at 6.8-7.1 keV suggesting that the X-ray flux is produced by accretion of matter from the companion wind characterized by density and temperature inhomogeneities.

The purpose of this article is to put forward the claim that Hurwitz's paper "Uber die Erzeugung der Invarianten durch Integration." [Gott. Nachrichten (1897), 71-90] should be regarded as the origin of random matrix theory in mathematics. Here Hurwitz introduced and developed the notion of an invariant measure for the matrix groups $SO(N)$ and $U(N)$. He also specified a calculus from which the explicit form of these measures could be computed in terms of an appropriate parametrisation - Hurwitz chose to use Euler angles. This enabled him to define and compute invariant group integrals over $SO(N)$ and $U(N)$. His main result can be interpreted probabilistically: the Euler angles of a uniformly distributed matrix are independent with beta distributions (and conversely). We use this interpretation to give some new probability results. How Hurwitz's ideas and methods show themselves in the subsequent work of Weyl, Dyson and others on foundational studies in random matrix theory is detailed., Comment: 22 pages; V2 updates references, makes minor corrections

We introduce a new method for proving central limit theorems for random walk on nilpotent groups. The method is illustrated in a local central limit theorem on the Heisenberg group, weakening the necessary conditions on the driving measure. As a second illustration, the method is used to study walks on the $n\times n$ uni-upper triangular group with entries taken modulo $p$. The method allows sharp answers to the behavior of individual coordinates: coordinates immediately above the diagonal require order $p^2$ steps for randomness, coordinates on the second diagonal require order $p$ steps; coordinates on the $k$th diagonal require order $p^{\frac{2}{k}}$ steps., Comment: Minor corrections

The goal of importance sampling is to estimate the expected value of a given function with respect to a probability measure $\nu$ using a random sample of size $n$ drawn from a different probability measure $\mu$. If the two measures $\mu$ and $\nu$ are nearly singular with respect to each other, which is often the case in practice, the sample size required for accurate estimation is large. In this article it is shown that in a fairly general setting, a sample of size approximately $\exp(D(\nu||\mu))$ is necessary and sufficient for accurate estimation by importance sampling, where $D(\nu||\mu)$ is the Kullback-Leibler divergence of $\mu$ from $\nu$. In particular, the required sample size exhibits a kind of cut-off in the logarithmic scale. The theory is applied to obtain a general formula for the sample size required in importance sampling for one-parameter exponential families (Gibbs measures)., Comment: 37 pages, 4 figures. To appear in Ann. App. Probab

In analyzing a simple random walk on the Heisenberg group we encounter the problem of bounding the extreme eigenvalues of an $n\times n$ matrix of the form $M=C+D$ where $C$ is a circulant and $D$ a diagonal matrix. The discrete Schr\"odinger operators are an interesting special case. The Weyl and Horn bounds are not useful here. This paper develops three different approaches to getting good bounds. The first uses the geometry of the eigenspaces of $C$ and $D$, applying a discrete version of the uncertainty principle. The second shows that, in a useful limit, the matrix $M$ tends to the harmonic oscillator on $L^2(\mathbb{R})$ and the known eigenstructure can be transferred back. The third approach is purely probabilistic, extending $M$ to an absorbing Markov chain and using hitting time arguments to bound the Dirichlet eigenvalues. The approaches allow generalization to other walks on other groups.

Consider a finite absorbing Markov generator, irreducible on the non-absorbing states. Perron-Frobenius theory ensures the existence of a corresponding positive eigenvector $\varphi$. The goal of the paper is to give bounds on the amplitude $\max \varphi/\min\varphi$. Two approaches are proposed: one using a path method and the other one, restricted to the reversible situation, based on spectral estimates. The latter approach is extended to denumerable birth and death processes absorbing at 0 for which infinity is an entrance boundary. The interest of estimating the ratio is the reduction of the quantitative study of convergence to quasi-stationarity to the convergence to equilibrium of related ergodic processes, as seen in [7].

Let H(n) be the group of 3x3 uni-uppertriangular matrices with entries in Z/nZ, the integers mod n. We show that the simple random walk converges to the uniform distribution in order n^2 steps. The argument uses Fourier analysis and is surprisingly challenging. It introduces novel techniques for bounding the spectrum which are useful for a variety of walks on a variety of groups., Comment: 24 pages, 6 figures

We prove the conjectured limiting normality for the number of crossings of a uniformly chosen set partition of [n] = {1,2,...,n}. The arguments use a novel stochastic representation and are also used to prove central limit theorems for the dimension index and the number of levels.

We consider new types of perfect shuffles wherein a deck is split in half, one half of the deck is "reversed", and then the cards are interlaced. Flip shuffles are when the reversal comes from flipping the half over so that we also need to account for face-up/face-down configurations while horseshoe shuffles are when the order of the cards are reversed but all cards still face the same direction. We show that these shuffles are closely related to faro shuffling and determine the order of the associated shuffling groups.

The quantitative long time behavior of absorbing, finite, irreducible Markov processes is considered. Via Doob transforms, it is shown that only the knowledge of the ratio of the values of the underlying first Dirichlet eigenvector is necessary to come back to the well-investigated situation of the convergence to equilibrium of ergodic finite Markov processes. This leads to explicit estimates on the convergence to quasi-stationarity, in particular via functional inequalities. When the process is reversible, the optimal exponential rate consisting of the spectral gap between the two first Dirichlet eigenvalues is recovered. Several simple examples are provided to illustrate the bounds obtained.

The star V2282 Sgr is positionally consistent with a strong Chandra X-ray and a Spitzer/IRAC MIR source. We derived its long term $I$-band light curve from the photographic archives of the Asiago and Catania Observatories, covering the years from 1965 to 1984. CCD $R_C$ photometry in Summer 2009 was re-analyzed. Optical spectra were secured at Loiano Observatory in 2011 and 2012. J H K photometry, obtained from several experiments in different epochs was compared and the Spitzer images were re-analyzed. V2282 Sgr was found to be irregular variable in all wavelengths. Spectroscopically, it shows strong emission features (H Balmer lines, [NII]6584 AA and [OIII]5007/4959 AA) while the Na D doublet is very strong, indicating a circumstellar envelope. A single thermal energy distribution cannot reproduce the observed SED, while it can be explained as the sum of a G-type star plus a variable circumstellar disc, which mimics a class 0/I object. Most likely, V2282 Sgr is a 1-2 $M_{sun}$ mass pre main sequence star with an accretion disk., Comment: 13 pages, 7 figure, in press on Baltic Astronomy

Contributed discussion and rejoinder to "Geodesic Monte Carlo on Embedded Manifolds" (arXiv:1301.6064), Comment: Discussion of arXiv:1301.6064. To appear in the Scandinavian Journal of Statistics. 18 pages

How does one search for a needle in a multi-dimensional haystack without knowing what a needle is and without knowing if there is one in the haystack? This kind of problem requires a paradigm shift - away from hypothesis driven searches of the data - towards a methodology that lets the data speak for itself. Dynamic Quantum Clustering (DQC) is such a methodology. DQC is a powerful visual method that works with big, high-dimensional data. It exploits variations of the density of the data (in feature space) and unearths subsets of the data that exhibit correlations among all the measured variables. The outcome of a DQC analysis is a movie that shows how and why sets of data-points are eventually classified as members of simple clusters or as members of - what we call - extended structures. This allows DQC to be successfully used in a non-conventional exploratory mode where one searches data for unexpected information without the need to model the data. We show how this works for big, complex, real-world datasets that come from five distinct fields: i.e., x-ray nano-chemistry, condensed matter, biology, seismology and finance. These studies show how DQC excels at uncovering unexpected, small - but meaningful - subsets of the data that contain important information. We also establish an important new result: namely, that big, complex datasets often contain interesting structures that will be missed by many conventional clustering techniques. Experience shows that these structures appear frequently enough that it is crucial to know they can exist, and that when they do, they encode important hidden information. In short, we not only demonstrate that DQC can be flexibly applied to datasets that present significantly different challenges, we also show how a simple analysis can be used to look for the needle in the haystack, determine what it is, and find what this means., Comment: 37 pages, 22 figures, 1 Table

This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?). It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a Normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of colors. This result holds for any graph sequence, deterministic or random. On the other hand, when the number of colors is fixed, a necessary and sufficient condition for asymptotic normality is determined. Finally, using some results from the emerging theory of dense graph limits, the asymptotic (non-normal) distribution is characterized for any converging sequence of dense graphs. The proofs are based on moment calculations which relate to the results of Erd\H os and Alon on extremal subgraph counts. As a consequence, a simpler proof of a result of Alon, estimating the number of isomorphic copies of a cycle of given length in graphs with a fixed number of edges, is presented., Comment: New results added that give limit theorems for the number of monochromatic edges when the number of colors is fixed. 40 pages, 2 figures

This paper offers a personal review of some things we've learned about rates of convergence of Markov chains to their stationary distributions. The main topic is ways of speeding up diffusive behavior. It also points to open problems and how much more there is to do., Comment: Published in at http://dx.doi.org/10.3150/12-BEJSP09 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

We study the combinatorics of addition using balanced digits, deriving an analog of Holte's "amazing matrix" for carries in usual addition. The eigenvalues of this matrix for base b balanced addition of n numbers are found to be 1,1/b,...,1/b^n, and formulas are given for its left and right eigenvectors. It is shown that the left eigenvectors can be identified with hyperoctahedral Foulkes characters, and that the right eigenvectors can be identified with hyperoctahedral Eulerian idempotents. We also examine the carries that occur when a column of balanced digits is added, showing this process to be determinantal. The transfer matrix method and a serendipitous diagonalization are used to study this determinantal process., Comment: 18 pages

Given a group G and a normal subgroup H we study the problem of choosing coset representatives with few carries.

Orthogonal polynomials for the multinomial distribution m(x, p) of N balls dropped into d boxes (box i has probability p(i)) are called multivariate Krawtchouk polynomials. This paper gives an introduction to their properties, collections of natural Markov chains which they explicitly diagonalize and associated bivariate multinomial distributions., Comment: 26 pages