DataScience4you2me

A couple years ago I wrote a blog post looking at how close the quaternions come to commuting. That is, the post looked at the average norm of xy – yx . A related question would be to ask how often quaternions do commute, i.e. the probability that xy – yx = 0 for randomly chosen x and y . There’s a general theorem for this [1]. For a discrete non-abelian group, the probability that two elements commute, chosen uniformly at random, is never more than 5/8 for any group. To put it another way, in a finite group either all pairs of elements commute with each other or no more than 5/8 of all pairs commute, with no possibilities in between. What if we have an infinite group like the quaternions? Before we can answer that, we’ve got to say how we’d compute probabilities. With a finite group, the natural thing to do is make every point have equal probability. For a (locally compact) infinite group the natural choice is Haar measure. Subject to some technical conditions, Haar measure...

Most people have heard of word problems, but not as many have heard of the word problem. If you’re imagining that the word problem is some superlatively awful word problem, I can assure you it’s not. It’s both simpler and weirder than that. The word problem is essentially about whether you can always apply algebraic rules in an automated way. The reason it is called the word problem is that you start by a description of your algebraic system in terms of symbols (“letters”) and concatenations of symbols (“words”) subject to certain rules, also called relations. The word problem for groups For example, you can describe a group by saying it contains a and b , and it satisfies the relations a ² = b ² and a -1 b a = b -1 . A couple things are implicit here. We’ve said this a group, and since every element in a group has an inverse, we’ve implied that a -1 and b -1 are in the group as well. Also from the definition of a group comes the assumption that multiplication is associati...

In his book The Algorithm Design Manual , Steven Skiena has several sections called “War Stories” where he talks about his experience designing algorithms for clients. Here’s an excerpt of a story about finding the best airline ticket prices. “Look,” I said at the start of the first meeting. “This can’t be so hard. Consider a graph … The path/fare can be found with Dijkstra’s shorted path algorithm. Problem solved!” I announced waving my hand with a flourish. The assembled cast of the meeting nodded thoughtfully, then burst out laughing. Skiena had greatly underestimated the complexity of the problem, but he learned, and was able to deliver a useful solution. This reminds me of a story about a calculus professor who wrote a letter to a company that sold canned food explaining how they could use less metal for the same volume by changing the dimensions of their can. Someone wrote back thanking him for his suggestion listing reasons why the optimization problem was far more compl...

Suppose a contractor is measuring the length of a wall. He starts in one corner of the room, and lets out a tape measure heading for the other end of the wall. But something is in the way, so instead of measuring straight to the corner, he measures to a point near the corner on the adjacent wall. If you looked down on the room from a bird’s eye view, the contractor wants to measure the distance from (0, 0) to ( x , 0), but instead measures from (0, 0) to ( x , y ) where y is small relative to x . How much difference does this make? The measurement error, as a function of y , is given by ( x ² + y ²) 1/2 – x . Expanding this function in a Taylor series around y = 0 shows that the error is approximately y ²/2 x . So the error is not on the order of y but of y ²/ x . The latter is much smaller if y is small relative to x . For example, suppose a room is 10 feet (120 inches) long. If someone were to measure the length of the room by running a tape measure to a point 4 inches up...

The previous post mentioned a Math Overflow question about unexpected mathematical images, and reproduced one that looks like field grass. This post reproduces another set of images from that post. Start anywhere in the complex plane with integer coordinates and walk west one unit at a time until you run into Gaussian prime [1]. Then turn left (counterclockwise) 90° and keep taking unit steps. Apparently this process will often (always?) return you to your starting point. Different starting points lead to different patterns. Here’s an example given in the post, starting at 3 + 5 i . Here’s a more complex walk starting at 27 + 30 i . I tried starting at 127 + 131 i and got a simple, uninteresting image. I tried again starting at 127 + 130 i and got something much more complicated. I didn’t time it, but it took several minutes to plot. Here’s the code that made the plots. (Note that Python uses j rather than i for imaginary unit.) from sympy import isprime import matplotl...

Math Overflow has an interesting question about unexpected mathematical images. Here’s a response from Payam Seraji that was easy to code up. Here’s the code that produced the image. from numpy import * import matplotlib.pyplot as plt t = linspace(0, 39*pi/2, 1000) x = t*cos(t)**3 y = 9*t*sqrt(abs(cos(t))) + t*sin(0.2*t)*cos(4*t) plt.plot(x, y, c="green") plt.axes().set_aspect(0.3) plt.axis('off') The post Simple equations whose plot looks like field grass first appeared on John D. Cook . from John D. Cook https://ift.tt/2G18PJ1 via IFTTT

I said something to my wife this evening to the effect that it’s best for employees to have one or at most two projects at a time. Two is good because you can switch off when you’re tired of one project or if you’re waiting on input. But with three or more projects you spend a lot of time task switching. She said “But …” and I immediately knew what she was thinking. I have a lot more than two projects going on. In fact, I would have to look at my project tracker to know exactly how many projects I have going on right now. How does this reconcile with my statement that two projects is optimal? Unless you’re doing staff augmentation contracting, consulting work is substantially different from salaried work. For one thing, projects tend to be smaller and better defined. Also consultants, at least in my experience, spend a lot of time waiting on clients (especially when clients are lawyers). So you take on more work than you could handle if everyone wanted your attention at once. At lea...

The factorial of a positive integer n is the product of the numbers from 1 up to and including n : n ! = 1 × 2 × 3 × … × n . The superfactorial of n is the product of the factorials of the numbers from 1 up to and including n : S ( n ) = 1! × 2! × 3! × … × n !. For example, S(5) = 1! 2! 3! 4! 5! = 1 × 2 × 6 × 24 × 120 = 34560. Here are three examples of where superfactorial pops up. Vandermonde determinant If V is the n by n matrix whose ij entry is i j -1 then its determinant is S ( n -1). For instance, V is an example of a Vandermonde matrix. Permutation tensor One way to define the permutation symbol uses superfactorial: Barnes G -function The Barnes G -function extends superfactorial to the complex plane analogously to how the gamma function extends factorial. For positive integers n , Here’s plot of G ( x ) produced by Plot[BarnesG[x], {x, -2, 4}] in Mathematica. More posts related to factorial Any number can start a factorial Alternating sums...

This post will look at simple numerical approaches to solving the preditor-prey (Lotka-Volterra) equations. It turns out that the simplest approach does poorly, but a slight variation does much better. Following [1] we will use the equations u ‘ =  u ( v – 2) v ‘ = v (1 – u ) Here u represents the predator population over time and v represents the prey population. When the prey v increase, the predators u increase, leading to a decrease in prey, which leads to a decrease in predators, etc. The exact solutions are periodic. Euler’s method replaces the derivatives with finite difference approximations to compute the solution in increments of time of size  h . The explicit Euler method applied to our example gives u ( t +  h ) = u ( t ) + h u ( t ) ( v ( t ) – 2) v ( t +  h ) = v ( t ) + h v ( t ) (1 – u ( t )). The implicit Euler method gives u ( t +  h ) = u ( t ) + h u ( t + h ) ( v ( t + h ) – 2) v ( t +  h ) = v ( t ) + h v ( t ...

The function σ k takes an integer n and returns the sum of the k th powers of divisors of n . For example, the divisors of 14 are 1, 2, 4, 7, and 14. If we set k = 3 we get σ 3 ( n ) = 1³ + 2³ + 4³ + 7³ + 14³ = 3096. A couple special cases may use different notation. σ 0 ( n ) is the number of divisors n and is usually denoted d ( n ), as in the previous post . σ 1 ( n ) is the sum of the divisors of n and the function is usually written σ( n ) with no subscript. In Python you can compute σ k ( n ) using divisor_sigma from SymPy. You can get a list of the divisors of n using the function divisors , so the bit of code below illustrates that divisor_sigma computes what it’s supposed to compute. n, k = 365, 4 a = divisor_sigma(n, k) b = sum(d**k for d in divisors(n)) assert(a == b) The Wikipedia article on σ k gives graphs for k = 1, 2, and 3 and these graphs imply that σ k gets smoother as k increases. Here is a similar graph to those in the article. ...

A while back I wrote about continued fractions of square roots . That post cited a theorem that if d is not a perfect square, then the continued fraction representation of d is periodic. The period consists of a palindrome followed by 2⌊√ d ⌋. See that post for details and examples. One thing the post did not address is the length of the period. The post gave the example that the continued fraction for √5 has period 1, i.e. the palindrome part is empty. There’s a theorem [1] that says this pattern happens if and only if d = n ² + 1. That is, the continued fraction for √ d is periodic with period 1 if and only if d is one more than a square. So if we wanted to find the continued fraction expression for √26, we know it would have period 1. And because each period ends in 2⌊√26⌋ = 10, we know all the coefficients after the initial 5 are equal to 10. [1] Samuel S. Wagstaff, Jr. The Joy of Factoring. Theorem 6.15. from John D. Cook https://ift.tt/3kF96ki via IFTTT

Take any positive integer  d that is not a multiple of 2 or 5. Then there is some integer k such that d × k has only 1’s in its decimal representation. For example, take d = 13. We have 13 × 8457 = 111111. Or if we take d = 27, 27 × 4115226337448559670781893 = 111111111111111111111111111. Let’s change our perspective and start with the string of 1’s. If d is not a multiple of 2 or 5, then there is some number made up of only 1’s that is divisible by d . And in fact, the number of 1’s is no more than d . This theorem generalizes to any integer base b > 1. If d is relatively prime to b , then there is a base b number with d or fewer “digits” which is divisible by d [1]. The following Python code allows us to find the number k such that d × k has only 1’s in its base b representation, provided k is relatively prime to b . It returns the number of 1’s we need to string together to find a multiple of k . If k shares a factor with b , the code returns 0 because...

I was explaining to someone this evening that I’m in the habit of saying “bang” rather than “exclamation point.” Here’s a list of similar nicknames for symbols. These nicknames could complement the NATO phonetic alphabet if you needed to read symbols out loud, say over the phone. You might, for example, pronounce “HL&P” as “Hotel Lima Pretzel Papa.” Or you might use them to have one-syllable names for every symbol. This is a different objective than maximizing phonetic distinctiveness. For example, referring to # and $ as “hash” and “cash” is succinct, but could easily be misheard. You could also optimize for being clever. Along those lines, I like the idea of pronouncing ( and ) as “wane” and “wax”, by analogy with phases of the moon, though this would be a bad choice if you want to be widely and quickly understood. Even if someone understood the allusion to lunar phases, and they knew which one looks like an opening parenthesis and which one looks like a closing parenthe...

The Lagrange inversion formula can be used to find the power series for the inverse of a function. I wrote about a different approach this problem a couple years ago , that time using Bell polynomials. This time I’ll give a formula that is more direct and easier to remember. Suppose we have a function A ( x ) and can compute its derivatives. We want to find a power series for B ( x ) where B ( A ( x )) = x . We assume A (0) = 0 and A ‘(0) ≠ 0. The k th coefficient in the power series for B( x ) is given by where [ k – 1] in front of a function means to take the ( k -1)st coefficient in its power series. Let’s apply this to get the first few terms of the series for tangent. Since inverse tangent has a simpler power series than tangent, we’ll set A ( x ) = arctan( x ) so that B ( x ) is tangent, i.e. the inverse of the inverse tangent. Of course we could just find the power series for tangent directly, and this is just a demonstration. Power series inversion is more useful when yo...

Ten years ago I wrote about how cosine makes a decent approximation to the normal (Gaussian) probability density. It turns out you get a much better approximation if you raise cosine to a power. If we normalize cos k ( t ) by dividing by its integral we get an approximation to the density function for a normal distribution with mean 0 and variance 1/ k . Here are the plots of cos k ( t ), normalized to integrate to 1, for k = 1, 2, and 3. And here’s a plot of cos 3 ( t ) compared to a normal with variance 1/3. And finally here’s a plot of L ² error, the square root of the integral of the square of the approximation error, as a function of k .   from John D. Cook https://ift.tt/2OKAVZU via IFTTT

The set of lines perpendicular to an ellipse carve out a shape called an astroid. If we replace the ellipse with an egg, we get a similar shape, but less symmetric. The equation for the egg is described here with parameters a = 3, b = 2, and k = 0.1. The ellipse above has the same a and b but k = 0. Related post: Envelopes of epicycloids from John D. Cook https://ift.tt/2NrOwEC via IFTTT

Many methods for numerically solving ordinary differential equations are either Runge-Kutta methods or linear multistep methods. These methods can either be explicit or implicit. The table below shows the four combinations of these categories and gives some examples of each. Runge-Kutta methods advance the solution of a differential equation one step at a time. That is, these methods approximate the solution at the next time step using only the solution at the current time step and the differential equation itself. Linear multistep methods approximate the solution at the next time step using the computed solutions at the latest several time steps. Explicit methods express the solution at the next time step as an explicit function of other information, not including the solution itself. The solution at the next time step appears on only one side of the equations. Implicit methods express the solution at the next time step as a function of other information including the soluti...