Abstract:
We consider a problem of shuffling a deck of cards with ordered labels. Namely we split the deck of N=k^tq cards (where t>=1 is maximal) into k equally sized stacks and then take the top card off of each stack and sort them by the order of their labels and add them to the shuffled stack. We show how to find stacks of cards invariant and periodic under the shuffling. We also show when gcd(q,k)=1 the possible periods of this shuffling are all divisors of order_k(N-q).

Abstract:
The number of ``carries'' when $n$ random integers are added forms a Markov chain [23]. We show that this Markov chain has the same transition matrix as the descent process when a deck of $n$ cards is repeatedly riffle shuffled. This gives new results for the statistics of carries and shuffling.

Abstract:
We have studied shuffling in genes that are conserved between distantly related species. Specifically, we estimated the incidence of gene shuffling in ten organisms from the three domains of life: eukaryotes, eubacteria, and archaea, considering only genes showing significant sequence similarity in pairwise genome comparisons. We found that successful gene shuffling is very rare among such conserved genes. For example, we could detect only 48 successful gene-shuffling events in the genome of the fruit fly Drosophila melanogaster which have occurred since its common ancestor with the worm Caenorhabditis elegans more than half a billion years ago.The incidence of gene shuffling is roughly an order of magnitude smaller than the incidence of single-gene duplication in eukaryotes, but it can approach or even exceed the gene-duplication rate in prokaryotes. If true in general, this pattern suggests that gene shuffling may not be a major force in reshaping the core genomes of eukaryotes. Our results also cast doubt on the notion that introns facilitate gene shuffling, both because prokaryotes show an appreciable incidence of gene shuffling despite their lack of introns and because we find no statistical association between exon-intron boundaries and recombined domains in the two multicellular genomes we studied.How do genes with new functions originate? This remains one of the most intriguing open questions in evolutionary genetics. Three principal mechanisms can create genes of novel function: point mutations and small insertions or deletions in existing genes; duplication of entire genes or domains within genes, in combination with mutations that cause functional divergence of the duplicates [1-3]; and recombination between dissimilar genes to create new recombinant genes (see, for example [4,5]). We here choose to call only this kind of recombination gene shuffling, excluding, for example, duplication of domains within a gene. In such a gene shuffling event, the parenta

Abstract:
In this paper we introduce and study a new property of infinite words: An infinite word $x\in A^\mathbb{N}$, with values in a finite set $A$, is said to be $k$-self-shuffling $(k\geq 2)$ if $x$ admits factorizations: $x=\prod_{i=0}^\infty U_i^{(1)}\cdots U_i^{(k)}=\prod_{i=0}^\infty U_i^{(1)}=\cdots =\prod_{i=0}^\infty U_i^{(k)}$. In other words, there exists a shuffle of $k$-copies of $x$ which produces $x$. We are particularly interested in the case $k=2$, in which case we say $x$ is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept $0<\rho <1$ (while those of intercept $\rho=0$ are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {\it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

Abstract:
In this paper, we discuss a shuffling sequence problem: Given a DNA sequence, we generate a random sequence that preserves the frequencies of all mononucleotides, dinucleotides, trinucleotides or some high order base-compositions of the given sequence. Two quadratic running time algorithms, called Frequency-Counting algorithm and Decomposition- and-Reassemble algorithm, are presented for solving the problem. The first one is to count all frequencies of the mononucleotides, dinucleotides, trininucleotides, and any high order base-compositions in the given sequence. The second one is to generate a random DNA sequence that preserves the mononucleotides, dinucleotides, trinucleotides, or some high order base- compositions. The two algorithms are implemented into a program ShuffleSeq (in C) and is available at http://www.cs.iastate.edu/~ sqwu/ShuffleSeq.html.

Abstract:
We study the dynamics of a certain discrete model of interacting particles that comes from the so called shuffling algorithm for sampling a random tiling of an Aztec diamond. It turns out that the transition probabilities have a particularly convenient determinantal form. An analogous formula in a continuous setting has recently been obtained by Jon Warren studying certain model of interlacing Brownian motions which can be used to construct Dyson's non-intersecting Brownian motion. We conjecture that Warren's model can be recovered as a scaling limit of our discrete model and prove some partial results in this direction. As an application to one of these results we use it to rederive the known result that random tilings of an Aztec diamond, suitably rescaled near a turning point, converge to the GUE minor process.

Abstract:
Proteins are machines created by evolution, but it is unclear just how finely evolution has guided their sequence, structure, and function. It is undoubtedly true that individual mutations in a protein affect both its structure and its function and that such mutations can be fixed during evolutionary history, but it is also true that there are other elements of protein sequence that have been acted upon by evolution. For example, the genetic code appears to be laid out so that mutations and errors in translation are minimally damaging to protein structure and function [1]. Could the probability that a beneficial mutation is found and fixed in the population also have been manipulated during the course of evolution, so that the proteins we see today are more capable of change than the proteins that may have been cobbled together following the 'invention' of translation? Have proteins, in fact, evolved to evolve? There is already some evidence that bacteria are equipped to evolve phenotypes that are more capable of further adaptation (reviewed in [2,3,4]). For example, mutator [5] and hyper-recombinogenic [6] strains arise as a result of selection experiments. The development of DNA shuffling (reviewed in [7,8]) and the appearance of several recent papers using this technique [9,10,11] provide us with a surprising new opportunity to ask and answer these fundamental questions at the level of individual genes, and perhaps even genomes.DNA shuffling, a method for in vitro recombination, was developed as a technique to generate mutant genes that would encode proteins with improved or unique functionality [12,13]. It consists of a three-step process that begins with the enzymatic digestion of genes, yielding smaller fragments of DNA. The small fragments are then allowed to randomly hybridize and are filled in to create longer fragments. Ultimately, any full-length, recombined genes that are recreated are amplified via the polymerase chain reaction. If a series of alleles o

Abstract:
Let H be a subgroup of a finite group G. We use Markov chains to quantify how large r should be so that the decomposition of the r tensor power of the representation of G on cosets on H behaves (after renormalization) like the regular representation of G. For the case where G is a symmetric group and H a parabolic subgroup, we find that this question is precisely equivalent to the question of how large r should be so that r iterations of a shuffling method randomize the Robinson-Schensted-Knuth shape of a permutation. This equivalence is rather remarkable, if only because the representation theory problem is related to a reversible Markov chain on the set of representations of the symmetric group, whereas the card shuffling problem is related to a nonreversible Markov chain on the symmetric group. The equivalence is also useful, and results on card shuffling can be applied to yield sharp results about the decomposition of tensor powers.

Abstract:
Many casinos routinely use mechanical card shuffling machines. We were asked to evaluate a new product, a shelf shuffler. This leads to new probability, new combinatorics and to some practical advice which was adopted by the manufacturer. The interplay between theory, computing, and real-world application is developed.

Abstract:
The problem of counting tilings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an Aztec diamond graph A_n, or more generally calculating the sum of the weights of all the matchings, where the weight of a matching is equal to the product of the (pre-assigned) weights of the constituent edges (assumed to be non-negative). This article presents efficient algorithms that work in this context to solve three problems: finding the sum of the weights of the matchings of a weighted Aztec diamond graph A_n; computing the probability that a randomly-chosen matching of A_n will include a particular edge (where the probability of a matching is proportional to its weight); and generating a matching of A_n at random. The first of these algorithms is equivalent to a special case of Mihai Ciucu's cellular complementation algorithm and can be used to solve many of the same problems. The second of the three algorithms is a generalization of not-yet-published work of Alexandru Ionescu, and can be employed to prove an identity governing a three-variable generating function whose coefficients are all the edge-inclusion probabilities; this formula has been used as the basis for asymptotic formulas for these probabilities, but a proof of the generating function identity has not hitherto been published. The third of the three algorithms is a generalization of the domino-shuffling algorithm described by Elkies, Kuperberg, Larsen and Propp; it enables one to generate random ``diabolo-tilings of fortresses'' and thereby to make intriguing inferences about their asymptotic behavior.