For the.
Average American All right thank you and
thank you guys for sticking around for
the end to the organizers for inviting
me to talk I may be talking today about.
A result and I had last year and a recent
improvement showing cut off with a window.
Improving I'll just cut off for
the random to random shuffle so
we're going to start by defining what the
random during them shuffle is we're going
to start with a deck of cards and whatever
order you would like we're going to pick
a card uniformly at random and remove it
from the deck if I take five cards and
I remove one I now have five spots
above between and below my cards and so
I'm going again pick one of the and spots
between those cards and insert that card
back into the deck and so those are my
moves and I'm going to keep doing this and
I want to know how long should I do
this before I'm random So first we're
going to introduce some formalities
that we're going to use to solve this so
the first one is what is a random walk
on the group so it's described by
a probability distribution by the group
on the group of my generators for
the walk I'm a start at the identity
because the walk is transitive so
it doesn't matter where I start.
So a time zero I'm at the identity at
time one I've picked one generator and
appended to the identity so
that's my distribution and
at time zero two I met PA If I
had to go somewhere and
then a time one I have to pick the exact
unique element that will undo Sigma and
give me so there's one way to do that for
each Sigma and
I can sum this up and this is convolution
and so I can get further steps
of the walk by looking at convolution
powers of my generating distribution
as long as I'm my generators are actually
generating my group and I don't have any
period history problems which I can solve
by having some probability of not doing.
Anything each step that I'm going to
converge to the uniform distribution which
sense I'm doing this on the center
group is uniform on the permutations so
this is an example of a market
chain on the metric group and
I can get the transition matrix which
I'm going to call throughout the talk A.
Well we already described how to get
from Sigma to pod you have to pick that
permutation that we saw up
here that gives me pause and
so I can write down my
matrix in terms of P.
which we'll see later.
OK So the good news you don't have to
remember this for the rest we'll just
point out some features about what
this distribution is for this walk so
how do I get an identity how do I not do
anything why I have to pull out a card and
put it back where I was I can do this for
each card I've been won over and
square chance for
each card etc etc I can transpose two
adjacent cards by pulling either one
of them out and putting it below or
above and so there's two ways for
each pair and I can get any adjacent J.
cycle.
Either in the positive direction
pulling out and inserting J.
below or the inverse of that
pulling out and inserting above.
And I can't get anything else all right so
what do we need to know about this what's
important in terms of analyzing this walk
two things first of which
this is a symmetric walk.
These are their own inverses and
these are each others in vs which means
my generators are symmetric and
my transition matrix is going to be
a symmetric matrix that's nice
in terms of spectral theory.
The other thing to notice which is a
little more subtle is I have the adjacent
transpositions but I don't have the rest
of the transpositions I have some of
the long cycles by only have the Jackson
ones so it's not a consciously FOS
walk I don't have all of the consciously
costs for each of the consciously classes.
And that's going to have ramifications for
us as well.
OK so we're going to be asking
how many times should I do
the shuffle before I'm shuffled so
we now get to define all of this
I'll do this very quickly redoing total
variation distance the mixing time if
I give you Absalom is the first
time the distances of most epsilon.
And we're going to be looking for
a cutoff so
we want to very short window such that
going this many stops in either direction.
Makes the mixing time either sorry
makes the total ration distance
either very large or very small.
OK So the way we're going to go about.
Studying this is through
representation theory so
I want to give you a primer on just
some of the basics that have to show
up in how we analyze this so
please ask questions if you have them and
the should be fairly gentle so
representation has a map
from the symmetric group
to a group of major cities.
That is compatible with the group
multiplication so if I look at
the Matrix multiplying for poly and sigma
it should be the same matrix I get for
the product before I go OK So the big and
factorial dimensional representation that
captures all the possible information you
could have in the group gives each element
of the group its own basis vector and
defines multiplication exactly
the way you should that.
Makes that can model of things huge.
The good news is it decomposes into lots
of little baby pieces that we
understand very well to some extent.
And the number of times each possible
irreducible representation appears
is the same as its dimension and
so I'll be using Delia
throughout the talk to refer to.
This dimension.
For the symmetric group.
Representations are indexed as the by
the same things as the consciously classes
the consciously classes for
the symmetric group are given by
all the permutations with the same
cycle structure so for example and S.
three all the two cycles
have one two cycle and
one fixed point here they are writing this
as one goes to two to goes to one and
three stands alone cetera and so
we came to know these as partitions
where this is a part of size for a part
of size three of size one if cetera.
And these are indexing my or two small
representations and so whenever I'm
talking about eigenvalues there
multiplicities we're going to be using.
Structures having to do with partitions
to talk about them because third letting
us get into this representation theory.
OK So the big and factorial
dimensional permutation representation
is a bit unknowable in the large and so
I'm going to give you a more concrete
favorite smaller representation you should
be thinking of throughout the talk and
it's what we form a lot of conjectures
using And so this is a tool for
you if you want to play with this sort
of thing of where you should start.
So this is the end dimensional
representation called the permutation
representation.
And.
If I want to act by Piet
on the basis factor by
I just then that basis
factor to part of I.
And so this is and by and.
Matrix with one one in every row and
column that's the permutation
matrix you've probably major
linear algebra students mess with
to a fair extent at least a half.
That's not quite an irreducible
representation unfortunately but
it's just the direct sum of
two of them it's got some.
Every row adds to one there's a trivial
one dimensional representation
tacked onto the interesting and
minus one dimensional representation.
And so your mind you it appears
it's dimension times and
the regular representation and so
will have and minus one copies of the sky
floating around in that
regular big representation.
OK Just to briefly illustrate what
the heck these things look like and
don't need to hold on to this the regular
representation for as three for
each permutation it gets
a six by six matrix big.
At the permutation representation
is only an dimensional so
I get a three by three matrix which
decomposes into the direct sum of a one by
one matrix and this slightly more
interesting two by two major X..
Alright the question you should be asking
yourself now is Why am I telling you this
what the heck does this have to do with
the markup check and the answer is that
if I can use the four you transform by
which I sum over the probability of G.
being a generator times the matrix Rigi.
I get a nice single matrix for
each probability distribution and
the slight miracle is that
this is the transpose of.
The market chain matrix the transition
matrix for that market chain.
For the random walk generated
by that distribution P.
since our P.
is symmetric K.
is a metric and so this is straight
up just for transition which are X.
So we want to study the eigenvalues
of a matrix and we can do that
by starting the I can use of this for
you transform and we can further do that
by reducing to studying the eigenvalues of
each of these irreducible representations.
OK so to illustrate again for us three.
This is my big transition matrix and I can
decompose that into two copies of the two
dimensional representation a trivial
representation and assign representation.
The first and last are very boring and
all the interesting stuff is contained in
the middle guy hopefully you can tell this
is an upper triangular trick matrix in
the middle and so I can always are on
the diagonal the two copies of it and so
I get to four ninth's three zeros and the
trivial one which we always have from our.
OK So this is going to be
our general strategy try to.
Each of these little You're do small guys
the happy case the case that's been most
studied is that if you have
a contest to class walk then each
of these little miniature C.S.
is a constant times the identity matrix.
You can pretty clearly say
we don't have that here.
So in each of those cases you get a single
eigenvalue from each of these irreducible
representations and
you can find that by taking traces traces
play nice and representation theory
they have a special name the character.
And their well understood or
well studied and
there's a general upper bound in terms
of how to turn total variation into L.
two and how to extend the L.
two in terms of those eigenvalues.
So the classic example of this.
One honey studied
the transposition walk where
which is generated by the transpositions
in the identity left hand you know
normally at random right hand uniformly
random transpose those two cards.
Because this is a consciously class walk.
They could get all the eigenvalues
by taking characters and
there are nice exact formulas for
what those characters were going to be.
And they had some really nice properties.
Most important here is the monitor to stay
as I move boxes down into the left and
my partition the eigenvalues reduce we're
trying to do estimates to control those
eigenvalues to high powers and so
being able to say I can study all
the guys with a certain row of the first
length first row of a certain length.
Together makes that
estimate much easier to do.
And so will be looking for and
around them for features like that
in order to be able to study it.
OK.
To other shuffles that we want to be
thinking about in light of random to
random or the similarly named
top to random and random to top.
Illustrated here is random just hop
where I've picked the same grey card I
did on the first slide but now I only have
one choice of where to put it on top of
the deck so that is random to top if you
let that but the weights of which card you
pick have arbitrary weights this is that
one library which is also much studied.
These are inverses of each other
in the sense that the generators
are inverses of each other for
these two walks.
And they both mix with cut
off after analog and steps.
And we're going to briefly very
briefly talk about two techniques
you can use to study these.
So the first is the strong stationary
of time completely probabilistic.
Every Time for
top ten random I insert a card before my
original bottom card it's going to
be inserted into a you know for
certain uniformly random order of the spec
to the other cards below that card and so
soon as all the cards are inserted below
that original random card so at that
original bottom card my deck is uniformly
random and so I can bound when that.
Happens in get a bound on my next time.
OK So another way to study this
looking at now random just
hop it falls into a special class of
walks called hyperplane arrangement
walks I slice through in this
case are three four three cards.
With hyper planes and the chambers the
regions between these hyper planes you can
index with the permutations and
the walk is going to be that I'm
at say one two three over there you see
the plane or and I pick this yellow.
I'm going to move to the chamber next to
this right closest to where I started so
I'm to move over here.
I'm starting at one two three and
I'm moving to three one two three and
I moved it to the top so each of these
three rays corresponds to moving one of
those three cards to the top and so
there's a whole algebraic with studying it
they're all very easy to diagnose yet
multiplicities of Unfortunately
you can't use the original total
variation to L two bound but
there's a special opera found exactly for
these guys the algebra is gorgeous.
But random Duran them is a symmetry
of this it is not one of these and
we can't get its eigenvalues that way.
OK So there's a whole host
of prior spectral results.
We normally consciously class walks
there's broad classes in which things
are known.
They're special cases like the star
transpositions where you can
explicitly diagonalize the walk is
algebraically nice and some Why.
There's all these hyperplane arrangement
woks notably the inverse riffle shuffle
that we can diagnose this way.
And the upper bounds in this family are
generally the harder just do not waste.
Again we also have a whole.
Host of probabilistic techniques
you guys are all familiar with
highlighting just a few that
are random walks in the group.
But these are often very delicate and
very hard to do and
none of them seem to work for
a random DRAM as far as getting cut off.
OK some suggestions if you're
interested in working this
area of things where we don't know
cut off where things are developing.
Are consciously classes with few fixed
points these tend to be extremely rapidly
mixing walks so they're hard to
study just because they're so
pleasingly fast that it's
hard to get tied to bounce.
If you take any consciously
class walking perturb it
in a way that you wish to try
to show cut off very hard to do
none of the techniques really seem
robust to this in a nice way.
Take a few different consciously class
walks and say choose between them
with some probability distribution
try to show it still has cut off.
Take any other one of these
hyperplane arrangement walks
symmetries it in the same way.
Try to show that take any two permutations
with high probability they generate
the symmetric group we know
that it takes at worst and Q.
blog and stops for that random walk
to mix try to show that it makes
sense with cut off and figure out
what that coefficient is for power.
And think about ways that have to
do with the order of the cards
in your random has to do
with the order of cards.
There's a new result having to do
with doing this to the carts with
some sort of fluid result called
smooshing that is fun to read for
the title as well as the technique.
OK so
I've been saying this is a symmetry as
ation of the hyperplane arrangement walk.
How are we doing it is not symmetry is
ation in the sense of averaging the two
at some interest they show and
in the sense of we do.
You first run into top and
then top to random.
It's the more natural thing
to do with your hands.
Hopefully you somewhat believe that this
avoids the problem of the bottom card
slowly drifting to the top and
finds the bottom card and
more noise more effectively and so
this should mix faster than random to
top which we will see very shortly.
But it's really intractable for most
techniques especially the probabilistic
techniques and so it first shows up
when comparison was developed and
it could be studied in terms of
random to top and top to random.
And so you can also think about
if you want more problems any
of these hyperplane arrangement walks.
OK So this is the literature
on this walk we've got
two comparison results up at the top.
And J C I remember ran as a.
Graduate student of Perseus that improved
their original comparison found.
And his work also led Percy to conjecture
that three fourths on log on was the right
coefficient.
Continuous time comparison and a nice
really nice lower bound studying for
each card that hasn't been removed how far
has it drifted from where it started and
so you can show before
this much time you can still correlate
where it is to where it started.
And the noise has an overwhelmed it.
And this one's a non Markovian coupling so
yeah.
All right so this is my contribution
last March we showed that three
fourths on log on was an opera bound which
showed cut off and this winter I refined.
This had to match the log
log term from SU back so
this is now cut off with window and
it's the slightly weird two term.
Term mixing time.
So that's the picture.
Where.
It falls off a cliff within the window so
if I do three fourths of.
My mass and fourth and long.
Stops minus the constant times then I'm
up here plus the constant times and
stops I'm done here.
Yeah yeah with an up slot of one and zero.
So it's a C.
if epsilon.
So.
You.
Are basically yeah so it's that you're
losing the cards you haven't removed.
In the noise of where
the rest are drifting so
it's kind of like a random walk on
the hyperplane where you don't have
to touch all the verses to
get total variations mixing.
OK so what other results you get for
free along with this is that.
Separation distances of most twice total
variation distance there's a known lower
bound for separation distance of again so
this is probably the right time but
this narrows down the window a little
bit closer than it was before.
And if instead of always inserting at
a uniform place if I remove my uniform
card and then insert it in a deterministic
but perhaps time in a homogeneous
way lexically Clee first first place and
second place third place.
That again has at most twice.
What it was before because the.
Similar values are the same
as the eigenvalues and
so there are some nice results
that you can relate this to.
OK so how are we going to
go about showing this well
we saw before you can go from total
variation to two as long as you have some
nice properties in this case we're getting
that because for a symmetric Markov chain.
And more transitive from the L.
two you can then go to the sum over all
the non-trivial eigenvalues to the two
teeth powers who are going to be trying
to control the sizes and multiplicity is
there of OK I want to explain where
the conjecture of Percy's came from.
It came from this thesis work in which
the an dimensional permutation
representation we talked about.
Was diagnosed and so.
Indexing over K.
from cables one to and minus one I can
plug in and get an eigenvalue for walk
because it's in and minus one dimensional
representation each of those eigenvalues
occurs with multiplicity and minus one
because that's how many times that
irreducible representation sits inside
that larger space so I'm always going to
have high multiplicity for
any random walk on the symmetric group so.
Maybe you could show something
about always having cut off.
In the face the it was
conjectured that all
the eigenvalues would have the common
denominator squared so for
any quills two three four five he fully
diagonalize and saw this pattern.
And how do you get the conjecture
Well they plugged into this distance.
Just these eigenvalues and
showed that these terms aren't
small until three fourths of
logon time with some fluctuation.
And so this gives you an L.
to blow or bound but
it doesn't give you an L.
to upper bound or total variation upper
bound or lower bout So that's where
the conjecture comes from and that's where
things stood for a really long time.
And so in two thousand and eighteen a full
dime illustration of random Turin and
was published was actually
diagnosed in about two thousand and
fourteen which is why we could
do it before it was published.
And so indeed these are some of
the largest eigenvalues of the walk but
slightly weird It also includes
the smallest eigenvalue the walk.
Because of the symmetry.
The smallest eigenvalue is zero and
so plugging in the last K.
we get a zero sum things
to notice plugging in K.
minus one I get a spectral
gap of order one over and.
But what's really unusual
about this walk is the gap to
the next largest eigenvalue is of
smaller order than the spectral gap
if this gap was of the same order the
mixing time would be one half and logon.
If this full multiplicity
occurred at that I can value
mixing time would be analog on.
So it's this weird kind of comment
like on each other's heels effect
that leads to the sudden usual
coefficient of three fourths.
And so would be interesting to see whether
more walks of this type could be developed
and studied were some weird usual ones.
So again that conjecture about all
the eigenvalues have in common
was indeed correct.
We'll talk more about this later.
I want to give you a feel for how the
three fourths versus that extra log log
term was accomplished so the kind of
obvious way to go about this is you.
If you go root and
out you have one minus two N.
because of the case squared.
And so you can lump the first group and
together and then the rest together and
if you do that through for
some logon time is enough.
But if you want to do that extra
log log saving you have to look at
how things are decaying within
those first route and terms and so
you really have to pass to something kind
of continuous in order to approximate that
and amazingly not just for
this irreducible but
for all that you're do you suppose you
end up with a galaxy and then a girl
which we can handle and things are kind
of remarkably pretty in this way and
so if you do those terms just kind
of magically cancel each other
in exactly the right way and so you can
show that's the right order of everything.
OK so I said before conscious the class
walks are the happy case we have
a algorithmic way to get at the
eigenvalues even if it's not always pretty
eigenvalues But
this is not a conscious it class walk and.
So really this had to be done through
a construction of eigenvectors and
there's no real some systematic way
to do this so that the the way that.
One about this is they
first noticed that and
minus one dimensional representation we
saw how does your eye can value on it
you might think that
would make things harder.
But that was actually the key so
the cool part is that.
If I look at some of permutations and
I in all of them pick uniformly
random card and put it on top.
And it cancels out and gives me zero.
Taking that random card and
inserting it still going to get me as hero
what may not be obvious is that if it
didn't give me zero putting it on top
it won't get me zero inserting it and
so the zero I can space
the kernel of this walk is the same
as the kernel of random to top.
Because random to top is slightly less
spot of a walk to look at you can actually
write down what all those eigenvectors
are and some sort of algebraic fashion.
And so they use this as a basis to get
all the other eigenvalues it or to flee.
And so they needed some way to build
up I can factors and they decided since
random to random is all about random
insertion that they should do that so
the word to the wise is if you're doing
something like building a cryptosystem and
you need a random permutation don't come
up with a weird random walk on this much
your group and use that just do random
search and starting from no currents.
Uniformly random Yeah.
And so
the idea is they took a new card and
inserted it uniformly at random
into their eigenvectors.
And that gave them surprisingly perhaps
new eigenvectors of the walk
after a little correction so
I've hugely simplified this forty page
accomplishment that is quite marvelous.
But that kind of the just summarized
OK I just want to briefly give you
guys a flavor of what these eigenvalues
actually look like and how we play with.
The irreducible representations
are indexed by partitions
That's my big shape here.
And then we can index the eigenvalues
inside of each year it is full
representation by a smaller partition that
fits inside that big repartee partition so
that's my grade out partition
sitting inside of there
the extra restriction is we only want to
considered greyed out partitions that
leave you with the most one white box
per home of my original partition.
Well arbitrary that's what it is the rule
for the multiplicity of the dimension.
Is that it's the number of
standard young to have a lot.
So number of ways to insert one
through and so that all the rows and
columns are increasing.
The multiplicity of how many times each.
I can value appears inside each
irreducible representation is a subset of
these on the smaller shape called the DESA
range meant Tablo And basically I have to
increase in the first row up to a even
number increase consecutively Yep.
So.
So I have a list of all of
them there's more than this.
I didn't want to make the slide
quite as busy as it could have been.
Yeah so for the shapes we have up
here these are all the death and
range meant Tablo No that means
this one actually doesn't index and
eigenvalue because it's
multiplicity zero down here so
there are still some extra rules
you have to have going on.
One thing to note is all the ones where
mew equals lambda that's your kernel but
zero zero value.
And so these white boxes correspond
to that your iterative insertions
that they used to build things up.
OK just briefly how do you
get the eigenvalue formula
it's amazingly somewhat simple
in terms of the size of it and
the number of cards the number of
these great boxes you have and
then a diagonal index where I put numbers
in these boxes in a systematic way and
then some them up and so what we have
to do when we go about this is to
come up with some sort of slightly uniform
bound in terms of these two partitions.
In terms of the size of new and and
the length of the first row if lambda and
then come up with appropriate bounds for
the multiplicities some show that you can
do this using a Gaussian in a girl and
that things kind of are magically all
the right order and you can do for us.
OK So that's the walk some suggested open
problems you might consider are seqlock
to random transpositions or sick look to
random insertion can you dive all eyes and
find the appropriate constant
they're both order and
log and but probably with cut off but
can you show that.
Can you take any other
hyperplane arrangement walk
something like the inverse shuffle cement
tries it can you diagonalize that is there
a systematic way to do this insertion and
construction of eigenvectors.
And can you do any of
these other suggestions
of other random Oxalis not your group.
All right thank you thank you thank you.
Yeah.
So it was already done they looked at for
each card that hasn't been pulled out
the distribution of where in
the deck it's likely to be.
So it's a.
Yes and it's somewhat of
a challenge to read so we're hoping
to come up with a constructive way to
show that using the eigenvectors and
I can values but it it's kind of hard.
You know the lower bound is
not representation theory so
we'd love to come up with We'd like to see
how to use the representation theory to
construct a test function
that you could maybe
analyze using representation
theory to get a lower bound.
So none of this is done with Wilson's but
you might be able to do it things
part of the problem is that I can tend to
be constructed inside these little B.B.
or do suppose instead of the big space so
it's hard to go back and forth that's all.
Someone And
if if we just the largest eigenvector
are eigenvalue wasn't enough to give the
mixing time the right mixing time and so
is a single eigenvector enough to give you
the appropriate lower bound we don't know.
Thank you thank you.