A colleague writes (extract):

I have an assessment with 4 sections in it A,B,C and D.

I have a question bank for each section. The number of questions in each bank is A-10, B-10, C-5, D-5.

In my assessment I will print out randomly a fixed number of questions from each bank. Section A will have 5 questions, B-5, C-2, D-2. 14 questions in total appear on the exam.

I can figure out how many different exam papers (order doesn’t matter) can be generated (I think!).

\displaystyle \binom{10}{5}\cdot \binom{10}{5}\cdot \binom{5}{2}\cdot \binom{5}{2}=6350400

But my question is: what is the uniqueness of each exam, or what overlap between exams can be expected.?

I am not trying to get unique exams for everyone (unique as in no identical questions) but would kinda like to know what is the overlap.

Following the same argument as here we can establish that:

Fact 1

The expected number of students to share an exam is \approx 0.00006.

Let the number of exams \alpha:=6350400.

This is an approach that takes advantage of the fact that expectation is linear, and the probability of an event E not happening is

\displaystyle\mathbb{P}[\text{not-}E]=1-\mathbb{P}[E].

Label the 20 students by i=1,\dots,20 and define a random variable S_i by

\displaystyle S_i=\left\{\begin{array}{cc}1&\text{ if student i has the same exam as someone elese} \\ 0 & \text{ if student i has a unique exam}\end{array}\right.

Then X, the number of students who share an exam, is given by:

\displaystyle X=S_1+S_2+\cdots+S_{20},

and we can calculate, using the linearity of expectation.

\mathbb{E}[X]=\mathbb{E}[S_1]+\cdots \mathbb{E}[S_{20}].

The S_i are not independent but the linearity of expectation holds even when the addend random variables are not independent… and each of the S_i has the same expectation. Let p be the probability that student i does not share an exam with anyone else; then

\displaystyle\mathbb{E}[S_i]=0\times\mathbb{P}[S_i=0]+1\times \mathbb{P}[S_i=1],

but \displaystyle\mathbb{P}[S_i=0]=\mathbb{P}[\text{ student i does not share an exam}]=p, and

\displaystyle \mathbb{P}[S_i=1]=\mathbb{P}[\text{not-}(S_i=0)]=1-\mathbb{P}[S_i=0]=1-p,

and so

\displaystyle\mathbb{E}[S_i]=1-p.

All of the 20 S_i have this same expectation and so

\displaystyle\mathbb{E}[X]=20\cdot (1-p).

Now, what is the probability that nobody shares student i‘s exam?

We need students 1\rightarrow i-1 and i+1\rightarrow 20 — 19 students — to have different exams to student i, and for each there is \alpha-1 ways of this happening, and we do have independence here (student 1 not sharing student i‘s exam doesn’t change the probability of student 2 not sharing student i‘s exam), and so \mathbb{P}[\text{(student j not sharing) AND (student k not sharing)}] is the product of the probabilities.

So we have that

\displaystyle p=\left(\frac{\alpha-1}{\alpha}\right)^{19},

and so the answer to the question is:

\displaystyle\mathbb{E}[X]=20\cdot \left(1-\left(\frac{\alpha-1}{\alpha}\right)^{19}\right)\approx 0.00005985\approx 0.00006.

We can get an estimate for the probability that two or more students share an exam using Markov’s Inequality:

\displaystyle\mathbb{P}[X\geq 2]\leq \frac{\mathbb{E}[X]}{2}\approx 0.00003=0.003\%

Fact 2

This estimate is tight: the probability that two or more students (out of 20) share an exam is about 0.003%.

This tallies very well with the exact probability which can be found using a standard Birthday Problem argument (see the solution to Q. 7 here) to be:

\mathbb{P}[X\geq 2]\approx 0.0000299191\approx 0.003\%

The probability that two given students share an exam is 1/\alpha\approx 0.00001575\%

Fact 3

The expected number of shared questions between two students is 6.6

Take students 1 and 2. The questions are in four bins: two of ten, two of five. Let B_i be the number of questions in bin i that students 1 and 2 share. The expected number of shared questions, Q, is:

\displaystyle \mathbb{E}[Q]=\sum_{i=1}^4\mathbb{E}[B_i],

and the numbers are small enough to calculate the probabilities exactly using the hypergeometric distribution.

The calculations for bins 1 and 2, and bins 3 and 4 are the same. The expectation

\displaystyle\mathbb{E}[B_1]=\sum_{j=0}^5j\mathbb{P}[B_1=j].

Writing briefly p_j=\mathbb{P}[B_1=j], looking at the referenced hypergeometric distribution we find:

\displaystyle p_j=\frac{\binom{5}{j}\binom{5}{5-j}}{\binom{10}{5}}

and we find:

\displaystyle\mathbb{E}[B_1]=\mathbb{E}[B_2]=\frac52

Similarly we see that

\displaystyle\mathbb{E}[B_3]=\mathbb{E}[B_4]=\frac{4}{5}

and so, using linearity:

\displaystyle\mathbb{E}[Q]=\frac52+\frac52+\frac45+\frac45=6.6

This suggests that on average students share about 50% of the question paper. Markov’s Inequality gives:

\displaystyle\mathbb{P}[Q\geq 7]\underset{\approx}{\leq} 0.9429,

but I do not believe this is tight.

Calculating this probability exactly is tricky because there are many different ways that students can share a certain number of questions. We would be looking at something like “multiple hypergeometric”, and I would calculate it as the event not-(0 or 1 or 2 or 3 or 4 or 5 or 6).

I think the \mathbb{E}[Q]=6.6 result is striking enough at this time!

In May 2017, shortly after completing my PhD and giving a talk on it at a conference in Seoul, I wrote a post describing the outlook for my research.

I can go through that post paragraph-by-paragraph and thankfully most of the issues have been ironed out. In May 2018 I visited Adam Skalski at IMPAN and on that visit I developed a new example (4.2) of a random walk (with trivial n-dependence) on the Sekine quantum groups Y_n with upper and lower bounds sharp enough to prove the non-existence of the cutoff phenomenon. The question of developing a walk on Y_n showing cutoff… I now think this is unlikely considering the study of Isabelle Baraquin and my intuitions about the ‘growth’ of Y_n (perhaps if cutoff doesn’t arise in somewhat ‘natural’ examples best not try and force the issue?). With the help of Amaury Freslon, I was able to improve to presentation of the walk (Ex 4.1) on the dual quantum group \widehat{S_n}. With the help of others, it was seen that the quantum total variation distance is equal to the projection distance (Prop. 2.1). Thankfully I have recently proved the Ergodic Theorem for Random Walks on Finite Quantum Groups. This did involve a study of subgroups (and quasi-subgroups) of quantum groups but normal subgroups of quantum groups did not play so much of a role as I expected. Amaury Freslon extended the upper bound lemma to compact Kac algebras. Finally I put the PhD on the arXiv and also wrote a paper based on it.

Many of these questions, other questions in the PhD, as well as other questions that arose around the time I visited Seoul (e.g. what about random transpositions in S_n^+?) were answered by Amaury Freslon in this paper. Following an email conversation with Amaury, and some communication with Uwe Franz, I was able to write another post outlining the state of play.

This put some of the problems I had been considering into the categories of Solved, to be Improved, More Questions, and Further Work. Most of these have now been addressed. That February 2018 post gave some direction, led me to visit Adam, and I got my first paper published.

After that paper, my interest turned to the problem of the Ergodic Theorem, and in May I visited Uwe in Besancon, where I gave a talk outlining some problems that I wanted to solve. The main focus was on proving this Ergodic Theorem for Finite Quantum Groups, and thankfully that has been achieved.

What I am currently doing is learning my compact quantum groups. This work is progressing (albeit slowly), and the focus is on delivering a series of classes on the topic to the functional analysts in the UCC School of Mathematical Sciences. The best way to learn, of course, is to teach. This of course isn’t new, so here I list some problems I might look at in short to medium term. Some of the following require me to know my compact quantum groups, and even non-Kac quantum groups, so this study is not at all futile in terms of furthering my own study.

I don’t really know where to start. Perhaps I should focus on learning my compact quantum groups for a number of months before tackling these in this order?

  1. My proof of the Ergodic Theorem leans heavily on the finiteness assumption but a lot of the stuff in that paper (and there are many partial results in that paper also) should be true in the compact case too. How much of the proof/results carry into the compact case? A full Ergodic Theorem for Random Walks on Compact Quantum Groups is probably quite far away at this point, but perhaps partial results under assumptions such as (co?)amenability might be possible. OR try and prove ergodic theorems for specific compact quantum groups.
  2. Look at random walks on quantum homogeneous spaces, possibly using Gelfand Pair theory. Start in finite and move into Kac?
  3. Following Urban, study convolution factorisations of the Haar state.
  4. Examples of non-central random walks on compact groups.
  5. Extending the Upper Bound Lemma to the non-Kac case. As I speak, this is beyond what I am capable of. This also requires work on the projection and quantum total variation distances (i.e. show they are equal in this larger category)

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Week 12/13

11:00 Tuesday 28 April, Week 12: Assessment Based on Lab 7

Students can submit work — VBA or Theory, catch-up or revision — based on Week 9 Lab 7 VBA/Theory Catch-up/Revision II assignment by today, Saturday 25 April.

If you have any further questions, I am answering emails seven days a week. Email before midnight Monday 27 April to be guaranteed a response Tuesday 28 April. I cannot guarantee that I answer emails sent on Tuesday morning (although of course I will try).

Catch Up/Revision of Lab 8 Material

If you have not yet done so, you will undertake the learning described in Week 10.

If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 10.

If you have already conducted this learning, and submitted a Lab 8 either back before 6 April, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback.

Students will be able submit work — VBA or Theory, catch-up or revision — based on Week 10 to a Lab 8 VBA/Theory Catch-up/Revision assignment on Canvas (due dates 3 May and 9 May).

Week 14

11:00 Tuesday 12 May, Week 14: Assessment Based on Lab 8

This assessment will ask you to do the following:

Consider:

\displaystyle k\cdot \frac{\partial^2 T}{\partial x^2}=\frac{\partial T}{\partial t}      (1)

For one (i.e. x_1 or x_2 or x_3) or all (i.e. general x_i), use equations (2) and (3) to write (1) in the form:

T^{\ell+1}_i=f(T_j^\ell),

i.e. find the temperature at node i at time \ell+1\equiv(\ell+1)\cdot \Delta t in terms of the temperatures at the previous time \ell\equiv \ell\cdot \Delta t. You may take \Delta t=0.5.

\begin{aligned} \left.\frac{dy}{dx}\right|_{x_i}&\approx \frac{y(x_{i+1})-y(x_i)}{\Delta x}\qquad(2) \\ \left.\frac{d^2y}{dx^2}\right|_{x_i}&\approx \frac{y(x_{i+1})-2y(x_i)+y(x_{i-1})}{(\Delta x)^2}\qquad(3) \end{aligned}

 

 

It is my advice to try and find 7 hours per week for MATH6040, and spend that time on it, working your way down through the learning in this announcement.

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Read the rest of this entry »

I hope to have Assignment 2 corrected and the marks communicated to you within 48 hours. That is a hope not a promise.

Many of you only submitted Assignment 2 late in the day and need to find at least (in my opinion) 7 hours per week to catch up on the other material.

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Week 12 to Sunday 3 May

Catch Up

ASAP you need to catch up on Week 10, Easter Week 1, and Easter Week 2 (lectures and tutorial).

This learning is directed towards the 40% Test (based on Chapter 2, Section 3.6, and Chapter 4). Here is tutorial video for this test.

Chapter 2 Exercises that you should be looking at include:

  • p.86, Q. 1-4
  • p.91, Q. 1-7
  • p.86, Q. 5-6 (harder)

I have developed the following for you to practise your differentiation which you need for Chapter 2 here:

Any exercises you do can be submitted to Week 12 Exercises by midnight Sunday 3 May.

If possible, submit the images as a single pdf file. To do this, select all the images in a folder, right-click and press print. It will say something like How do you want to print your pictures? Press (Microsoft?) Print to PDF. If possible choose an orientation that has all the images in portrait.

Week 13 to 10 May

You will be invited to catch up on the Week 10, Easter Week 1, and Easter Week 2 learning, as well as do revision on Chapter 2. You will be asked to submit work for feedback by midnight Friday 8 May.

Week 14 to 17 May

Provisionally, the 40% Test on Chapters 2, 4, and Section 3.6 will take place Monday 11 May.

In the form of the Test 1 trust pledge, instructions, and tables, practical information for Test 1 may be found here.

After this you will be invited to do revision on Linear Systems. Here is video based on Q. 1 from the Summer 2019 paper on the back of your manual.

Week 15 to 24 May

Provisionally, the 20% Linear Systems Test will take place Thursday 21 May.

 

 

Some notes on this paper.

1. Introduction and Main Results

A tree has no symmetry if its automorphism group is trivial. Erdos and Rényi showed that the probability that a random tree on n vertices has no symmetry goes to zero as n\rightarrow \infty.

Banica (after Bichon) wrote down with clarity the quantum automorphism group of a graph. It contains the usual automorphism group. When it is larger, the graph is said to have quantum symmetry.

Lupini, Mancinska, and Roberson show that almost all graphs are quantum antisymmetric. I am fairly sure this means that almost all graphs have no quantum symmetry, and furthermore for almost all (as n\rightarrow \infty) graphs the automorphism group is trivial.

The paper in question hopes to show that almost all trees have quantum symmetry — but at this point I am not sure if this is saying that the quantum automorphism group is larger than the classical.

2. Preliminaries

2.1 Graphs and Trees

Standard definitions. No multi-edges. Undirected if the edge relation is symmetric. As it is dealing with trees, this paper is concerned with undirected graphs without loops, and identify V=\{v_1,\dots,v_n\}\cong \{1,2,\dots,n\}. A path is a sequence of edges. We will not see cycles if we are discussing trees. Neither will we talk about disconnected graphs: a tree is a connected graph without cycles (this throws out loops actually.

The adjacency matrix of a graph is a matrix A=(a_{ik})_{i,j\in V} with a_{ij}=1 iff there is an edge connected i and j. The adjacency matrix is symmetric.

2.2 Symmetries of Graphs

An automorphism of a graph \Gamma is a permutation of V that preserves adjacency and non-adjacency. The set of all such automorphisms, \text{Aut }\Gamma, is a group where the group law is composition. It is a subgroup of S_n, and S_n itself can be embedded as permutation matrices in M_n(\mathbb{C}). We then have

\text{Aut }\Gamma=\{\sigma\in S_n\,:\,\sigma A=A\sigma\}\subseteq S_n.

If \text{Aut }\Gamma=\{e\}, it is asymmetric. Otherwise it is or rather has symmetry.

2.3 Compact Matrix Quantum Groups

compact matrix quantum group is a pair (C(G),u), where C(G) is a unital \mathrm{C}^\ast-algebra, and u=(u_{ij})_{i,j=1}^n\in M_n(C(G)) is such that:

  • C(G) is generated by the u_{ij},
  • There exists a morphism \Delta:C(G)\rightarrow C(G)\otimes C(G), such that \Delta(u_{ij})=\sum_{k=1}^n u_{ik}\otimes u_{kj}
  • u and u^T are invertible (Timmermann only asks that \overline{u}=(u_{ij}^\ast) be invertible)

The classic example (indeed commutative examples all take this form) is a compact matrix group G\subseteq U_n(\mathbb{C}) and u_{ij}:G\rightarrow \mathbb{C} the coordinates of G.

Example 2.3

The algebra of continuous functions on the quantum permutation group S_n^+ is generated by n^2 projections u_{ij} such that the row sums and column sums of u=(u_{ij}) both equal \mathbf{1}_{S_n^+}.

The map \varphi:C(S_{n}^+)\rightarrow C(S_n), u_{ij}\mapsto \mathbf{1}_{\{\sigma\in S_n\,|\,\sigma(j)=i\}} is a surjective morphism that is an isomorphism for n=1,2,3, so that the sets \{1\},\,\{1,2\},\,\{1,2,3\} have no quantum symmetries.

2.4 Quantum Symmetries of Graphs

Definition 2.4 (Banica after Bichon)

Let \Gamma=(V,E) be a graph on n vertices without multiple edges not loops, and let A be its adjacency matrix. The quantum automorphism group \text{QAut }\Gamma is defined as the compact matrix group with \mathrm{C}^\ast-algebra:

\displaystyle C(\text{QAut }\Gamma)=C(S_n^+)/\langle uA=Au\rangle

For me, not the authors, this requires some work. Banica says that \langle uA=Au\rangle is a Hopf ideal.

Hopf ideal is a closed *-ideal I\subset C(G) such that

\Delta(I)\subset C(G)\otimes I+I\otimes C(G).

Classically, I the set of functions vanishing on a distinguished subgroup. The quotient map is f\mapsto f+I, and f+I=g+I if their difference is in I, that is if they agree on the subgroup.

The classical version of Au=uA ends up as a_{ij}=a_{\sigma(i)\sigma(j)}… the group in question the classical \text{Aut }\Gamma. In that sense perhaps Au=uA might be better given as fA=Af.

Easiest thing first, is it a *-ideal? Well, take the adjoint of fA=Af\Rightarrow A^*f^*=f^*A^* and A=A^* so I is *closed. Suppose f\in I and g\in C(S_n^+)… I cannot prove that this is an ideal! But time to move on.

3. The Existence of Two Cherries

In this section the authors will show that almost all trees have two cherries. Definition 3.4 says with clarity what a cherry is, here I use an image [credit: www-math.ucdenver.edu]:

cherry

(3,5,4) and (7,9,8) are cherries

Remark 3.2

If a graph admits a cherry (u_1,u_2,v), the transposition (u_1\quad u_2) is a non-trivial automorphism.

Theorem 3.3 (Erdos, Réyni)

Almost all trees contains at least one cherry in the sense that

\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}[C_n\geq 1]=1,

where C_n is #cherries in a (uniformly chosen) random tree on n vertices.

Corollary 4.3

Almost all trees have symmetry. 

The paper claims in fact that almost all trees have at least two cherries. This will allow some S_4^+ action to take place. This can be seen in this paper which is the next point of interest.

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Week 11

20% VBA Assessment Based on Lab 6

Thank you to everyone for completing the assignment.

Catch Up/Revision

You are advised to catch-up on the learning described in Week 9.

If you have already conducted this learning, and submitted a Lab 7 either back before 30 March, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback. If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 9.

Students can submit work — VBA or Theory, catch-up or revision — based on Week 9 to the Lab 7 VBA/Theory Catch-up/Revision I assignment on Canvas (by Sunday 19 April), or Lab 7 VBA/Theory Catch-up/Revision II assignment by Saturday 25 April.

Week 12/13

PROVISIONAL: Tuesday 28 April, Week 12: Assessment Based on Lab 7

Catch Up/Revision

If you have not yet done so, you will undertake the learning described in Week 10.

If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 10.

If you have already conducted this learning, and submitted a Lab 8 either back before 6 April, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback.

Students will be able submit work — VBA or Theory, catch-up or revision — based on Week 10 to a Lab 8 VBA/Theory Catch-up/Revision assignment on Canvas.

I may have two due dates. Perhaps Sunday 3 May and Saturday 9 May.

PROVISIONAL: Tuesday 12 May, Week 14: Assessment Based on Lab 8

This assessment will ask you to do the following:

Consider:

\displaystyle k\cdot \frac{\partial^2 T}{\partial x^2}=\frac{\partial T}{\partial t}      (1)

For one (i.e. x_1 or x_2 or x_3) or all (i.e. general x_i), use equations (2) and (3) to write (1) in the form:

T^{\ell+1}_i=f(T_j^\ell),

i.e. find the temperature at node i at time \ell+1\equiv(\ell+1)\cdot \Delta t in terms of the temperatures at the previous time \ell\equiv \ell\cdot \Delta t. You may take \Delta t=0.5.

\begin{aligned} \left.\frac{dy}{dx}\right|_{x_i}&\approx \frac{y(x_{i+1})-y(x_i)}{\Delta x}\qquad(2) \\ \left.\frac{d^2y}{dx^2}\right|_{x_i}&\approx \frac{y(x_{i+1})-2y(x_i)+y(x_{i-1})}{(\Delta x)^2}\qquad(3) \end{aligned}

 

 

It is my advice to try and find 7 hours per week for MATH6040, and spend that time on it, working your way down through the learning in this announcement.

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Read the rest of this entry »

Although I have extended the Assignment 2 deadline by a week to Friday 24 April, it is my strong advice to finish and submit Assignment 2 ASAP, and then try and find 7 hours more hours on top of that for MATH7021, and spend that time on it before Sunday 16 April.

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Week 11 to Sunday 26 April

Finish Assignment 2: Laplace Transforms

As outlined in the assignment section:

As per p.167-175 in the manual.

You may email any questions about the assignment and you will receive a response the next day, and I will be responding to emails seven days a week.

When it comes to submission, think about the following:

  • Review photo. If you cannot see, we cannot mark it.
  • Be careful of shadows
  • Take A4 pages out of pad.
  • Have A4 page flat on a surface.
  • Take picture directly over page.
  • Lighting
  • Use sharp black or blue pen. No pencil. No red pen?
  • Picture of one a page at a time.
  • Clearly label page with page numbers and labels

If possible, submit the images as a single pdf file. To do this, select all the images in a folder, right-click and press print. It will say something like How do you want to print your pictures? Press (Microsoft?) Print to PDF. If possible choose an orientation that has all the images in portrait.

Here is video (30 minutes) of me doing (parts (a) to (c) of) the Laplace Transform exam question on p. 228 of the manual.

If you haven’t yet, go back and do the Week 8 learning tasks, and watch

You may email any questions about the assignment and you will receive a response the next day, and I will be responding to emails seven days a week.

If possible, submit the images as a single pdf file. To do this, select all the images in a folder, right-click and press print. It will say something like How do you want to print your pictures? Press (Microsoft?) Print to PDF. If possible choose an orientation that has all the images in portrait.

I will start correcting Assignment 2 Saturday 25 April.

Read the rest of this entry »

In your Canvas announcements you will see that I have laid out a provisional plan for the remaining assessment.

There is a lot of information and tasks in this announcement but that is to account for the fact that people have got more or less work done on MATH6040 up to now. Work your way down through this announcement. It is my advice to try and find 7 hours per week for MATH6040, and spend that time on it. You may want to put extra time into the Matrices Test.

Now that all the material is covered, I am focusing on supporting your learning.

The first assessment will take place 19:30 Tuesday 14 April 2020 and is based on Chapter 2: Matrices. More information below. The other assessments are provisionally set for 28 April (Chapter 3), 12 May (Chapter 4), and 19 May (Chapter 1). The following plan is designed around these. 

Keep in mind at all times:

“Any and all work, submitted at any time, will receive feedback.”

“Do not hesitate to contact me with questions at any time. My usual modus operandi is to answer all queries in the morning but sometimes I may respond sooner.”

Read the rest of this entry »

%d bloggers like this: