Generating a random variable by coin tossing

1. Coin tossing

Suppose we are given a sequence of independent fair bits (meaning take and with probabily ) we want to produce with them a discrete random variable that takes the values with probabilities . The objective, of course, is to do this using the least possible number of bits.

Let us note that if we consider in binary, this variable is uniformly distributed in . The usual way to produce given a number uniform in is to consider the intervals and declare when . Of course, knowing whether or not, takes a few bits from . Indeed, having seen digits, the only thing we know is that . We denote the number of bits needed by .

1.1. Uniform distribution

The case of the uniform distribution is particularly interesting; it is indeed one of the most common distributions one might come across, but we claim that its study shows some interesting patterns too.

Experimental redundancy for . Algorithm 1 is the “wasteful algorithm”, while is the limit period for the redundancy.

Algorithm 1. We begin with a simplified version that is slightly wasteful.

The idea is that we stop only when is completely contained in one of the intervals .

Why is this wasteful? Well, the probability of the resulting being a dyadic number is 0, so we could directly stop when

thus neglecting the borders. This obviously improves the performance in cases like , in which we end up stopping after exactly steps. The analysis of the algorithm also gets more interesting as we shall see afterwards.

See the corresponding code for our first (and wasteful) algorithm. Here .

x = 0
l = 0
while (true) :
  x += reveal_bit() / 2^k
  while (I[l+1] <= x) :
   l += 1
  if (x + 1/2^k < I[l+1] or I[l+1] == 1) :
    return k
  k += 1

To start let us recall that

which simplifies the computation of , because telling whether we have to continue is easy: if there is a number of the form in , then we must conclude that . This is so because constitutes the border between two intervals and whenever .

For , it is obviously true that contains a number of the form with , that is not . Indeed, notice that . If then we observe that we may only stop if is , hence in this case .

Assume now that , then there is exactly one number of the form in the interval , which is given by

The set of numbers in starting with those exact first digits is

therefore we conclude that

Since each term of the union is disjoint and so

where denotes the fractional part.

Therefore

In all we deduce that the redundancy satisfies

where , where denotes the fractional part.

Algorithm 2. In our second algorithm we stop as soon as for some .

Experimental redundancy for Algorithm 2 with .

In this case we observe that the difference occurs when for some . Of course for some integers , with odd.

This never happens when is odd, therefore the expected value remains the same when is odd. Now assume where is odd. Then and since and are odd we must have and . Now given , what is the smallest for which occurs? Let us remark that, since , all of the digits cannot equal , therefore can be reduced to a number of the form with digits. It follows then that and that occurs as a right border for . Observe that , hence, in fact, this happens during the phase in which and the intervals are longer than the intervals , therefore once we get to the phase , all of the possible dyadics are already available.

Fixed there are choices for our odd (if we allow for the possibility of , whihc we have to discount anyway). Hence in all we can produce dyadics as a right-border.

Therefore

In all we deduce that the redundancy satisfies

where , where denotes the fractional part and is the greatest such that divides .

1.2. Generic distribution

Algorithm 1 for a generic . In this case we have to work with each individual right-border . As long as , all of the points in will produce a truncation that satisfies , thus we will not have stopped. This accounts for a term in , for each (even for ).

In particular this means that

The other cases are counted in (not necessarily disjoint from the previous count!)

which has measure

Strictly speaking we should count the difference

We prove the bound

Indeed, observe that

and reverse the order of summation to get

In general this means that

and in particular

Lemma 1 Fix , then

Proof: Write

where of course . Then

and then the inequality , valid for , proves the result.

Comment. To prove that for , observe that the function is concave and .

The function .

As a corollary we get the following Theorem

Theorem 2 Let be the number of bits it takes to decide to which interval the number belongs. Then we have

where is called the entropy of .

Furthermore, the in (2) is tight by our example with the uniform distribution.

Concluding remarks. I got the inspiration for this post from reading [1], chapter 5, where the optimal algorithm for producing a random variable from fair coin tosses is described. I wondered, usually when working with probabilities one uses the procedure that I explained in the post, which more or less corresponds to the so called Inversion method, so how far is it from the optimum? In this post I have proved that it is not that far from being optimal actually. In [1] it is proved that the optimal procedure satisfies the same bounds for the expected value , but it is not shown that the inequality on the RHS is tight for the optimal procedure.

References.

1. Thomas M. Cover, Joy A. Thomas, Elements of Information Theory. Wiley Series in Telecommunications and Signal Processing, Second Edition, 2006.

Grading a class

Imagine we had a class with students and each week they hand in a sheet of homework. Now, you choose a set of of them at random and correct only those . At the end, the grade assigned to a student is the average among all of his homework sheets that you corrected. How many weeks does it take for every student to have a grade?

Comment: I came up with this question because I have implemented such a system and I wanted to choose wisely as to have a grade for each student every weeks.

Coupons collector problem.

It is easy to see that this problem is related to the classical coupon collector problem. The problem reads as follows: you have coupons and each time you buy one (picked uniformly at random from the possible ones) and the question is how long it takes you on average to get the full collection. The answer here is

where is the random variable corresponding to the number of coupons it takes you to get the full collection, and .

The proof follows easily upon noticing that, once you have different coupons, you have to wait on average to get a new one.

It is also not difficult to prove that, even though what we have above is the expected value, the actual value of is usually not much bigger than (remember that we may estimate ). Indeed,

because is the probability of never getting (up to time ) a given coupon. The event is the union of the events “not getting a given coupon”, thus we have bounded the probability of the union with the sum .

Thus, if we get

Teacher’s problem. Back to our problem, if represents the number of weeks it takes us to have a grade for every single student, intuitively we should have ()

If we look at the sequence of sets of elements we get, and we write them all in a line in some order, we get a possible outcome for the coupons collector problem… but it is a bit better than in the coupons collector’s case, because we are guaranteed that the first coupons are distinct, the second group of coupons are distinct, and so on. What is better, these cases have higher probability than before, so one expects to have such an inequality (I am not claiming this constitutes a proof!). This establishes, though, the parallel between the two problems, now we expect to have nearly the same results, but with a factor of involved.

We note that the probability of never getting a given student in iterations is

Thus we also get

Considering we get

Proposition 1 We have the bound

This means that we never wait much more than weeks. However, is the expected value as in the case of the coupons collector problem? The answer is negative, but I claim that asymptotically this is not far from the truth.

Proposition 2 We have

Proof: Indeed, we note that bounding the probability of the union by the sum of the probabilities is just the first term of the inclusion-exclusion process, if we continue we get the so-called Bonferroni’s inequalities

for all . Here we note that

whenever (else it is ). So fixing any and , letting

for , which already suggests the claimed result. To actually get it, we must make a better estimate of the remainder term. Note that, in (2) we have

which equals, taking logs and using

Here we may rewrite this as

and the second term is quadratic

Hence if we get

so that

because . Thus, from (1) we get

but the two extremes converge to as , thus the result.

Applying this to my class. In my case I usually have students and I would like to be so I will want to have

in order to apply our inequality and have at most % of probability leaving out some student… thus and (which is, of course, nonsense… because then ). The problem here is that we are making a gross estimation for such a small , thus, in fact, looking more directly at

and setting , we get , i.e. . The actual minimal value of is indeed … by inspection, bad news for me (I was using ). In fact, to have probability roughly 1/2-1/2, we must pick .

This proof is essentially that of [1] for the Coupon’s Collector problem.

References

1. Erdős, Paul; Rényi, Alfréd (1961), On a classical problem of probability theory (PDF), Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6: 215–220.

Riemann-Lebesgue

The purpose of this post is to discuss the Riemann-Lebesgue Lemma, why it makes sense, and some interesting applications among which we have , the proof of which, in my opinion, explains a lot more clearly why it should equal .

Recently I have grown quite fond of the Riemann-Lebesgue Lemma, the Fourier Transform and Fourier Series, through studying Tauberian Theorems in Analytic Number Theory, and Partial Differential Equations.

The Riemann-Lebesgue lemma states that

 

for quite a general set of functions .

In the case of continuous functions the interpretation is that has periods of length proportional to , in which, being continuous, the variation in is really small, while the integral of in this periods is . Thus we will be adding roughly for each cycle, being the change in during the cycle. Adding these up leaves us with something of the order of , which can be made arbitrarily small as .

Lemma 1 Let be continuous, then we have

Proof: Observe that is uniformly continuous on the compact set . Thus, given an arbitrary there is such that whenever .

Next consider so that , we partition the integration intervals into pieces of size less than

where the are a short-hand for .

Here it is clear that the first and the last integrals tend to as because

which , and similarly for the other one. Thus, for a certain with we may assume that implies that these two integrals have absolute value less than .

As for the case of with integer, note that (it goes through a whole cycle!) implies

where the last inequality follows from the fact that the distance to the left-most point of the interval is less than and so .

Hence, collecting terms, we get

for .

Example 1. We will prove that (assuming its existence, which may be shown by the alternating series test):

 

Let us denote this integral by . Consider then

which clearly satisfy and . Setting we get

Note that almost fits into the Riemann-Lebesgue, but is not continuous on , it tends to infinity close to . To remedy this problem (somewhat surprisingly) we look first at

here we run into trouble again, but at the points and instead of .

Why insist with ? Well, in fact, it is well-known that

for a proof look at below.

To finally eliminate the discontinuities, we note that

can be extended continuously (by considering the limits at ) to .

The choice should not be surprising as

when . In fact we are eliminating the contribution from the simple poles!

We are very lucky because

while

Thus

and considering odd we have

which shows by the Riemann-Lebesgue lemma.

The Riemann-Lebesgue lemma is more general actually.

Lemma 2 Consider where is the -algebra of the Lebesgue-measurable sets and is the Lebesgue measure. Then

where is to be interpreted as , the Lebesgue integral.

Proof: The continuous functions are dense in under the Lebesgue measure .Thus it follows that, given a measurable function we have a sequence of continuous functions such that so that, decomposing as we have

from where the result follows upon making and sufficiently large in order.

Of course, the proofs read verbatim when we change for any bounded periodic-function , since the principle of the proof stays the same.

Lemma 3 Consider where is the -algebra of the Lebesgue-measurable sets and is the Lebesgue measure. Let be a bounded periodic measurable function on , with period , such that . Then

where is to be interpreted as , the Lebesgue integral.

Another possible extension is the case in which we have a continuously differentiable function , in such a case we may say much more about the rate of decay.

Lemma 4 Consider . Then

as

Proof: Applying integration by parts

and therefore

thus proving the result.

Example 2. We will prove that

 

for , and that this convergence is uniform on for any .

1. First show that .
2. Integrate it in from to to get

   

3. To make the integrand of the form with differentiable when , we must remove the pole of at . Consider

   

   then is holomorphic on because we removed the pole, in particular it is continuously differentiable on for any .

4. Thus

   

   is when .

5. Observe that, by what we know from Example 1, we have

   

   and here when . Indeed

   

   thus, integrating by parts, we get .

Proof of . Somewhat surprisingly, the computation of

boils down to a matter of evaluating a particular coefficient of a polynomial!

Let us write , so that we get

Here observe that so that

Note that we have

and therefore, by factoring from each of the factors, we get

where the notation denotes the coefficient of in .

For instance, for , we observe

as the term appears in the sum if and only if is even.

Remark. The integral may also be computed by induction and the use of trigonometric identities. However, I feel that the proof above is much more illuminating.

Exercise. Use the result from Example 2. to prove that .

Higher order Newton-Raphson

In this post we shall see one way to look at the Newton–Raphson formula, and the extensions this produces. Actually, I came up with this idea a few years back, while I was studying for a Numerical Analysis exam.

Introduction. We are given a function , and we are interested in finding a root such that . Here we shall first assume that our function if at least , that is, it has continuous second derivatives.

To generate a ‘fixed point method’, what we do is we find a convenient function such that exactly for the zeroes (or the zero) of . Then, we start at some point , and consider the sequence . If this sequence converges , then is a fixed point of and so a zero of .

The most trivial example of such a method follows from choosing a constant and considering

so that if and only if .

Let us assume that a sequence defined by converges to , then by looking at the Taylor–expansion of at , we get

To accelerate the convergence of to , we would like to cancel the linear term so that the error roughly squares in each iteration. However, this seems impossible if we do not know and .

The way to fix this is to consider not a constant, but a function too! A function such that is enough, because we note that if , then by expanding Taylor of order for and then Taylor of order one for :

Thus, the most obvious choice is , which yields

which gives the Newton–Raphson iteration.

What is the trick here?. The trick was to choose so that . We note that, since , we need not care about the derivative of at :

so that

What if we now want to cancel without affecting the first derivative? The real trick is to notice that, when you have and differentiate it less than times, you get at . Now, when you differentiate exactly times and evaluate the result at , then all the terms vanish, except for the one in which we choose to differentiate all the times. Hence

Thus, by considering

and fixing the coefficients recursively, we can cancel all of the first derivatives at .

Indeed, we have

and here the zeroes of become fixed points of order in . Of course, this procedure doesn’t ensure that no new zeroes have been introduced (it does introduce new zeroes sometimes).

Example. A method of order to get follows from computing the positive root of by considering with

This method, however, has a few fixed points other than :

of course, the latter two are purely imaginary.

Since, when is very large we have , we get that the sequence defined by iteration must be bounded, and hence it must have a subsequence that converges to one of our fixed points.

To normalize in terms of , we note that all fixed points are of the form which suggests considering

instead. Here what we want to see is that as we keep on composing .

What we first note is that, when we have that , hence it is possible to get negative starting with a positive number. Let us avoid this problem by noticing that for all where it makes sense (its real zeros are , both with multiplicity ), hence, if we let we have whenever . As a matter of fact, we have that and so when . When , we note that , and so the convexity of along with , imply

when satisfy , and is very large. Therefore for , while having implies (derivative is positive), and therefore if , we have decreasing and always . Hence .

The function is concave for , hence this will mean that more generally for , and therefore we can only have when (if it at some point exceeds one, we are done by the previous part). Indeed, and , hence by concavity

whenever satisfy , and equality occurs if and only if either or is .

In conclusion, since we can write , we have that

here

Without knowing , we may still note that and hence taking is certainly enough. Even better, when is an integer, we may write with , then picking does the trick. Indeed, because

and so , where .

Complex plot of the result of applying above exactly seven times, showing a more complicated situation. The red area corresponds to the convergence to .

Complex plot of the result of applying Newton-Raphson with exactly eleven times. In this case the only fixed points are and .

Final comments.

Although the idea is amusing, it is fair to say that in terms of complexity we do not gain that much with respect to the usual Newton-Raphson. As a matter of fact, if we are given a method of order 3, and doing two iterations of Neton-Raphson were much less costly than doing one of our method of order 3, we are being wasteful (the error is “raised” to the power of 4 every two iterations of Newton-Raphson).

The fast decay of the gamma function

The purpose of this post is to discuss the fast decay of the gamma function when along the imaginary axis. This is an interesting topic, as it is not usually discussed, we are generally more interested in the increase of the gamma function on the positive real axis, because there we have , and we thus get the asymptotic behaviour of the factorials.

As it is well-known (see [1]), we have a generalised Stirling’s formula

as over a slit-domain with for some . Here denotes the principal part of the logarithm of , while need not be the principal part of the logarithm of . It must coincide with the principal part of the logarithm, however, up to an integer multiple of , and so, in particular, we have equality for the real parts of both sides of (1).

The behaviour of the gamma function is illustrated in the following complex plot. For each point, the intensity of the light indicates the absolute value of the resulting value (thus, black means while white means ), and the colour indicates the phase angle . What is striking about the picture is that the gamma function seems to decay very fast to almost being when the imaginary part is larger that the real one.

Complex plot of on .

Next we will be interested in , and therefore we will only be interested in the real part of the RHS of (1), because for all we have . Thus, we will compute the real part of the RHS of (1).

Let us write with , since the case follows then simply from applied repeatedly. By definition we have and here, since , we have , which of course should tend to as with . We will need a little more precision here to get the asymptotic estimates for , and so we will need the following lemma.

Lemma 1 Let , we have

where denotes the sign of .

Proof: Since is an odd function, it is enough to prove the result for . Let us differentiate the LHS of (1), we get

and so the function is constant in and the value of this constant follows by taking .

The consequence of this is, since , that

and here when we may use the Taylor expansion of around to get

as with .

Now, after a little bit of algebra, we get

when . For , we observe that

and so, if , we get

And, subtracting and adding (and another term) we finally get

As a little simplification, note that and so we have

whenever with , and .

Remark 1 If we redo the algebra more carefully, we can check that

as with , here we define . Note that the threshold for fast decay is .

Remark 2 A bit more precisely, the threshold for fast decay is approximated by the equation , if we disregard the linear terms.

Indeed, on the one hand, when we get

as , which tends to still. And, on the other hand, if with , we get

which tends to , and so .

The limits of the exponential decay can be seen in terms of the darkness of the pixels.

The orange line corresponds to the solutions of the equation .

References

1. N.G. de Bruijn, Asymptotic methods in analysis. Dover Publications, United States, 3rd edition, 1981.
2. Sage was used to produce the pictures. See here and here.

The Fibonacci Word

Let us define by and , and extend it to a homomorphism of by . Let us note that

Something very interesting is going on, each seems to be a prefix of . We will see that this is indeed the case.

Let us write . It is clear that , and so and so on for . Then we have

This implies that the digits converge pointwise to those of

and we shall call the Fibonacci word.

It should be noted that the origin of the name is motivated by the fact that , which mimicks the definition of the Fibonacci numbers .

The Fibonacci word is quite special. For starters, each subword (a finite and consecutive subsequence of characters) of appears infinitely many times. A sequence satisfying this property is said to be recurrent.

It is clear that is recurrent, indeed because if is a finite subword, then is a subword of for some and then, since is a subword of for each .

The Fibonacci word is also what we call a balanced word.

Definition 1 (Balanced word) A binary word is said to be balanced if for every and for pair of subwords (a consecutive sublock of ) and of length , we have that the number of ones in and differs in at most .

If we denote by the number of ones in , then the latter part of the definition can be rewritten as .

Lemma 2 If a binary sequence is not balanced (be it finite or not), then it contains two subwords and for some .

Proof: Let and satisfy and have length as short as possible. It is clear then that and must differ in their borders (else we can eliminate the part that is equal and still get the same difference ). Clearly then and , since the cross cases , and , are not possible (because and the latter are shorter), while having , implies . Now we claim . Assume otherwise, then there is a first point where they differ, that is , where , . Note then that can’t be because otherwise we have and as subwords, and these are shorter. Hence and , . But then we have which again leads to an absurd.

We prove is balanced. Suppose otherwise, then there would be subwords and within for large enough. Since is recurrent, we may further assume that the two subwords and we will be working with are not at the beginning of . Clearly is not empty as can’t appear in by definition of . The word can only start with a and end with a , since there can’t be two consecutive s (else would not be a subword). Thus and so and are subwords of . Now is injective from to and we observe that

• A within the sequence implies that the element right to its left is a , and that we may extract the preimage of this pair to be .
• A indicates that the first must come from as otherwise it would be followed by a .

In conclusion, we know that the character to the left of is a and then contains which has as its preimage and this is a subword of . Similarly, we note that having in implies having in . So both and appear as subwords of and is not balanced too. This idea follows inductively until we get small enough for it to be obvious that is balanced and we have reached an absurd.

Remark 1 (The Fibonacci word is not eventually periodic) Observe that the number of ones in is while its length is . This follows by induction and the fact that for .

Since where is the Golden Ratio, it follows that the density of ones in tends to as . Since is not rational, this proves that is not eventually periodic (otherwise the limit would be being the period, and thus rational).

Remark 2 (The Fibonacci word is Sturmian) Since is both balanced and not–eventually periodic, it follows that it is Sturmian (see [1]). In particular, this means that the number of subwords of length in is exactly for each .

References

1. See the book Substitutions in Dynamics, Arithmetics, and Combinatorics.

Partitions and divisors

The number of partitions of a non-negative integer is, roughly speaking, the number of ways in which we can write as a sum of positive integers disregarding the order of the terms, and we denote this number by .

Formally speaking then, the fact that we do not care about the order of the terms translates into the fact that we may choose them to be ordered increasingly as follows
this is the set of partitions of , and we then define to be its cardinal (number of elements).

A few examples

And here we show the partitions of , the heights of the columns correspond to the sizes of the integers involved in the partition ( listed in decreasing order):

meaning

respectively.

The objective of this post is to have a combinatorial proof of the following identity.

Identity 1. Given we have

where is the sum of the positive divisors of .

Note. Before going into the proof, we note that it is not immediately obvious why should be related to a number-theoretic quantity such as , which corresponds to a multiplicative property (divisibility) rather than an additive one.

Proof: To prove it, we observe that the left-hand-side is the cardinal of where , and we will now find a way to count the same thing, but that produces the right-hand-side in the process.

We start the other way around, given a partition of , for which we write , we are going to exploit the fact that to index the integer in .

The idea is, if we want to index , there is exactly one such that

where the empty sum is interpreted as being .

Assume , then to fully determine , in addition to , we have to indicate a number from , so that

Now, the way in which we indicate and is as follows. Assume we had

First we record first the size of the summand, and then which one of the indexes we are referring to. To indicate , this is done by considering where is the index of within .

Thus, once we indicate , a multiple of and a number , we have actually fully determined . In how many partitions , with , can we indicate in this exact same manner? Clearly , because, once we have fixed at least terms equal to , the rest can be filled up as we please.

It follows then that

Now, this can be rewritten as

which is simply .

This idea doesn’t stop here, try the following exercise.

Exercise 1 A rooted tree is an unlabeled tree with a distinguished vertex known as `the root’. If denotes the number of rooted trees with vertices, prove that we have

where .

Remark. Finally, it is fair to remark that these identities can be proved by means of generating functions. Indeed, we have the OGF

and then rest is similar to the proof by generating functions in this post.

Binary look-and-say sequences

A few days ago, Numberphile released a video on YouTube about the famous Look-And-Say sequence, presented by John Conway himself. Just as a reminder (if you have not watched the video, which I thoroughly recommend you do), this sequence begins as follows

and is produced by `reading out loud’ each sequence. For instance, reads as `one one’, and so the result is . Then in turn is read as `two ones’, and so we get , then `one two, one one’ thus , etc. Hence the name look-and-say, or, as John Conway named it `audioactive decay’.

If you like, what we are doing is coding `runs’. That is, we look at the first character , and count how many of these appear in a block, until some different character appears, and we encode , where is the length of the run in decimal notation (with no leading s) and is our character.

If you have watched the video, you might have seen that the length of the elements of the sequence satisfies

which is the root of a polynomial of degree 71, a really remarkable property.

When I shared the video above, Matt suggested looking at the binary variant starting with . This eventually led to a nice discussion on the topic, discussing algorithms to estimate the limit for this case, and for another variant. As a result, in the end, I thought of a proof of analogous properties for the binary case, in fact, these are all significantly simpler than in the case of base .

We are going to define our sequence over the alphabet as follows, first let , and then proceed as above but use base to code the length of the runs. Thus

for instance, to code and produce we have three s followed by one , and .

For simiplicity, we will denote the length of the string resulting from applying the rule above times but with the seed at the beginning. For example , the length of , as we have started with the seed . Also, we will denote the rule above by , so that for each .

We will prove that

where satisfies the equation . As a matter of fact, the constant already appears in OEIS, but not for the reason above. Again, observe that satisfying a polynomial of degree instead of a polynomial of degree is a massive difference.

We will begin by making a few observations which are inspired by the ideas given by John Conway in the video above, in particular, we will try breaking the strings into `atoms’.

Observation 1. Suppose we had an string

where the point is meant to be concatenation, and it is there just to draw attention to that point in the string. Then, the result of applying the above rule (in binary) times to is the same as applying the rule times to each of the two parts and separately, and then concatenating the results.

In other words, we have

where .

Proof: Well, certainly and are not in the same run, so .

Afterwards, we observe that necessarily ends with a to indicate that the last character is a , while always starts with a , since the binary representation of a nonzero number (the number of s in the first run of ) will always start with a . Hence the process repeats itself.

So, using this idea, I first implemented a fast algorithm to compute the lengths for quite large (up to 900), and check that the digits indeed coincided with those in A092526.

The idea is that one can always break up the string into independent fragments of the form (plus a little detail with the last run). Then one runs these sequences independently, and memoizes, that is, remembers their results, becuase each string of the form is going to break up again into smaller such strings.

Next I asked the computer to give me the distinct `atoms’ it found, somewhat surprisingly there were quite few of them, and this lead to the following observation. Observe that here we are assuming that the strings always begin with a , as, if this where not already true for , then it is true for (all lengths in binary start with a ).

Observation 2. We need only look at strings of the form with at most five 0s and at most five s, because eventually (after is applied a number of times that is) any string decomposes into a concatentation of elements of the form

where denotes the `end-of-string’ character.

Proof: First note that the images by of the elements of the form are again concatenations of elements of the same form . Then, by Observation 1, it is enough to show the result for strings that are of either one of the following forms: , . We proceed by induction in the length of the strings. When we have length no more than , the result is trivial. Assume, now, the result to be true for all lengthes less than . And assume we are given a string of the form or that has length .

If with we have . Here the length of the binary representation of in base is , and similarly the length of is . If or , we observe that for , and that for all , and so

and the result follows by using Observation 1, combined with the inductive hypothesis. Else, if and the string satisfies already.

The previous two observations are valid regardless of the initial seed. The trick now, is to note that we may produce a system of equations in by considering the generating functions

that is, the coefficient of is the length of .

When a string decays into with each of the form in , we note that this is implies

indeed, because for .

With this tool at hand, we note that we can produce a system of equations for the elements of the form (taking into account each such element also decays into elements of the same form after applying a few times), solve it, and then get the result by looking at

The procedure explained above can be programmed easily. Now, for the case in which we start with , we will produce a somewhat smaller system by looking at the strings of .

Case starting with . Note that produces the equation

and now we need `info’ on . Again , that is

In turn , thus consider now  and . Observe while , and so

The strings and already have their own equations, and so we may just proceed with . We have , thus

But we need to go on with , and get , so

Here had already appeared, and so we continue just with . We get

and we stop here, as no new `atomic’ string has appeared.

In all we have

a system of equations over the field .

A digraph representation of the process when started at 10. An edge indicates that is one of the independent factors that make up .

Solving (using, say, Sage or Maxima) we get

and so

Here we observe that has real root in the interval , as and . The other two roots are not real (observe that for all ), and so they are conjugates , . By looking at the coefficients of , we have , that is , and so implies that we have .

Now, we prepare for its partial fraction decomposition, we have

and here

for some coefficients . Let us denote . Equation implies that

for . As we remarked above, we have , and so . As for all , this means that (else would tend to ). Moreover, as , we have that

as , and note that implies . Thus we have proved the result.

Remark. As a matter of fact, we can also check that .

Matt proposed the following: You have an infinte stream where each is a random variable taking the value with probability and with the same probability, and the are independent. Suppose that you incrementally apply the `binary run encoding’ as above, does

exist? What is its value?

Edit. According to my computations now, what we have is

I may explain this in another post, it actually follows by using ideas from Analytic Combinatorics. Also, I am pretty sure that converges to the same number, but in probability. For this we should have a look at the variance I guess.

One might be tempted to use the strong law of Large Numbers for , unfortunately there are a few technical details that need to be taken care of.

References

1. Numberphile on YouTube: Look-and-Say Numbers (feat John Conway).
2. Sequence A092526, Online Encyclopedia of Integer Sequences: A092526.
3. Look-and-say sequence, Wikipedia: here.
4. Sage, free open-source mathematics software system. See here.

Generating a random permutation

It is well-known that any permutation of can be written as a product of transpositions, that is, of permutations of the form with , where we recall that is the permutation satisfying and for . In this post however, we will do the opposite. We will start with the identity permutation and compose transpositions uniformly at random. How long do we have to go before any given permutation is roughly equally likely to appear?

Remark 1 Observe that this method is equivalent to having all of the elements from through layed out on an array, and then randomly swapping a pair of them. It is natural to think that, if we keep on going long enough, the resulting permutation is going to be a (uniformly) `random’ one.

// initialize the array, but we will work with 0...N-1 instead.
for (int i = 0; i < N; i++)
    a[i] = i;
// for a number of iterations k that should depend on N
for (int i = 0; i < k; i++)
{
    int x = random(0,N-1); // pick an element uniformly at random from {0,...,N-1}
    int y = random(0,N-1); // independently
    swap(a,x,y); // swap positions x and y in a.
}
return a;

However, this raises a few questions: Is it truly `random’? For how long do we have to keep on swapping elements?

This process can be modeled as follows

and so on, where all the pairs are independent random variables, such that

What we want to know is

• Given , does as ?
• If that were indeed the case, how fast is the convergence?

We will start with the first question. For this, we will model the problem with a markov chain. The state space will be , now observe that given , the probability of moving to for the following iteration is

• if . This follows from the fact that we have ways to generate the identity, by choosing a trasposition of the form .
• if for some trasposition . Notice that this transposition is uniquely determined by , hence giving the previous probability as corresponds to the pairs and .
• otherwise.

So, the transition probability matrix is constant, i.e. does not depend on the number of iterations we have already gone through.

Next, since we can always go from to , we observe that the markov chain is aperiodic, and, since any permutation can be written as a product of transposition, we get that the markov chain is also irreducible. It follows then (classic result in Markov Chains), that this markov chain has a unique stationary distribution, and that from any given initial distribution (starting at with probability for instance), we end up converging to the limit distribution Now, what is this probability distribution ?

To check that is indeed the uniform distribution, we check that the uniform distribution is indeed stationary. Given the distribution , the probability of being on a particular state for the next iteration is

Indeed, the first term corresponds to the transpositions , while the second sum ranges over with . If by applying we end up having , the previous permutation was necessarily .

By letting for all , it follows from that the probability of having in the next iteration is

showing that this is indeed the stationary distribution.

Great, now we know that the distribution of tends to as , but how fast does it converge? With we are far from having a uniform distribution since the resulting permutation must have at least one fixed point. Indeed there is at least one element that does not turn up in any of the transpositions we have applied so far. So for instance

whenever , where we have used cycle notation.

So, actually, what we have seen is that the diameter of the graph is at least , but that still leaves out the question of the speed of convergence.

An easier question is the following: how close are we to having

In this case it is not difficult to compute explicitly when . Observe that equals

Note that

for all , and

hence, if we denote, by symmetry, when , we get

Here, since , it follows that

Then

and by letting we get

as .

So, for instance, this tells us that, when , we get

for , meaning that is, with probability roughly , a fixed point. Of course, this is an unreasonably large number, as the probability of being a fixed point if were uniformly distributed would have to be .

Looking at these probabilities for , that is

a choice of would seem reasonable. However, looking at those for , which are given by

we see that something more interesting is going on.

If the maximum relative error is , then

and, since we know that

we get

Thus, in order to have , that is, to have the relative error bounded by a constant , it is necessary to have at least

iterations (and maybe not sufficient, this is a lower-bound), where the constant of the term actually depends on .

Some concluding remarks:

Remark 2 As we have mentioned, the method to generate permutations that we discuss above is actually a bit crude. In fact, we can do better as follows:

// initialize the array, but we will work with 0...N-1 instead.
for (int i = 0; i < N; i++)
    a[i] = i;
// for each position choose one of the not-chosen elements
for (int i = 0; i < N; i++)
{
    int pos = random(i,N-1); // pick an element uniformly at random from {i,...,N-1}
    swap(a,i,pos); // swap positions i and pos in a.
}
return a;

Remark 3 The construction above is quite general. If we consider a generator set , the subgroup can be sampled uniformly in the limit by taking

where the random variables are independent and uniformly distributed, with distribution

where is a free (fixed) parameter, which actually affects the rate of convergence.

Again, given a distribution over , the distribution for the next iteration is

It is clear again that taking , the previous equation is satisfied. As the resulting Markov chain is irreducible (when considering ) and aperiodic (as we have ), this is the limiting distribution.

Matters of convergence become even more difficult however, as we do not even know how large is going to be.

Finite fields and trinomials

In this post we shall prove that is irreducible in , thus proving there are infinitely many irreducible trinomials over . Maybe my proof is overcomplicated, so if you have a simpler one, go ahead and comment.

First remember that finite fields are of the form with for some prime and , and that is Galois, where .

Proposition 1 If is a finite field with elements, and characteristic . Then for some .

Proof: If had two prime divisors, then we have a prime divisor . Now, seen as an additive group, must have a subgroup of order by Cauchy’s Theorem, and thus we must have an element such that has order . However, too, since , and this is nonsense since and so .

Remark 1 In fact, we will actually have . This follows from the fact that if we have an extension , then is a vector space over .

Proposition 2 Let be a finite field with elements and characteristic . Then is unique up to isomorphism (thus the notation), and is Galois where .

Proof: Note that must be exactly the splitting field (splitting fields are isomorphic) of , in fact, the set of roots forms the field . Since that polynomial only has simple roots, being the splitting field of a separable polynomial over , it follows that is Galois.

For , note that when we are working over a field of characteristic . This follows from the Binomial Theorem, and the fact that is prime.

Finally, we are going to characterize the group where and .

Proposition 3 Let , where is a prime, and . Let us define by

then we have

Proof: From for all , and the fact that is clearly multiplicative, we have that is a morphism, since . By Fermat’s Little Theorem, we have that is constant over , thus .

Since is finite, it follows that is cyclic, thus it contains an element of order . Note then that for all , but . Thus we find that .

Finally, since is Galois, it follows from the Funamental Theorem that .

Remark 2 Clearly the previous proposition generalizes to the case where and is a subfield of (we must have then , since ). In which case , since is the subfield characterized by the fact that their elements correspond exactly to the roots of .

Remark 3 The map is usually called the Frobenius map.

As a reminder, we have the following useful proposition:

Proposition 4 Let be a finite Galois extension. Let , then we have

where is the set of Galois conjugates of .

Proof: Since is finite, must be algebraic over . Let be its minimal polynomial over . Since must permute roots of , it follows that contains only distinct roots of , thus it follows that must divide over . So we will be done if we can prove that .

Let , note then that but and … thus . But is injective and , thus and so

and so its coefficients must be fixed by every , being Galois, it follows then that .

Now we are almost done, we will move on to proving that is irreducible.

Proof: Note that , and so, being that has only simple roots (its formal derivative is ) for each , it follows that the roots of in a splitting field must be exactly the elements satisfying but .

Now let be an element such that but , out of the possible ones. We will be done if we can show its irreducible polynomial over has degree .

Remember now that , and so by the previous proposition we find that we will be done if we can show that are all distinct (note that , since and has order ). Since has order , this is the same as showing that the order of module must be .

To finish off the problem then, we shall prove a Lemma.

Lemma 5 Let , then we have where .

Proof: By induction, the result is obvious for by picking .

Now let and assume the result to be true for . For we have, by the inductive hypothesis

where . Thus, expanding we get

and here note that

where , thus since we get that .

Now this proves that the order of module must be exactly .

Proof: Since is coprime to , we get . Thus must divide . If , then we must have that either or .

The former option is impossible since . For the latter, we note that we have where , by the Lemma, so is impossible since .

Comment: The previous exercise appears as part of a note about Golomb’s conjecture in this book . Golomb’s conjecture states that there are infinitely many irreducible trinomials over  that are primitive (which is a lot stronger than what we proved), I haven’t looked much into it, but as of 2005 the conjecture was still open.