Today was the last day of my independent study at BGSU.

To start off, I talked with Dr. Zirbel about finding a good problem to work on once this intensive period worked on. In addition to the one I described in the last post, I found a more well known problem having to do with the Kolakoski sequence, which is a sequence of 1s and 2s that encodes its own run length. Each 1 in the sequence corresponds to a single number later on, and each 2 corresponds to a pair of the same number later on.

In addition to this problem, there is a problem that he got from a professor who retired which essentially involves determining the number of points of an n-dimensional cube that an n-dimensional sphere with radius r < sqrt(n) can contain. We figured out the lower dimensionality cases, but the higher dimensions are more difficult once sqrt(n) > 2, because then the sphere can contain more lower-dimension edges before it reaches the upper bound of the radius. I plan to work on this first by determining a general algorithm for finding which points must be evaluated for finding this number of vertices. Once I have a computer program that can plot it, then I’ll be able to analyze that data and try to create an analytic solution.

In addition to this, I also attended the probability class and the pedagogy class. In probability, we finished the proof of the martingale convergence theorem, which was really interesting, because it made me realize that we often alter the way we look at specific cases in proofs without actually altering the statements. In pedagogy, we talked about academic honesty. It was good to see that academic honesty is taken very seriously and that the system is designed to prevent people from being dishonest.

Today we had the data science exploration class, during which we talked about different ways of approaching a data science problem when the data is unbalanced (one class, typically the class of interested, is greatly underrepresented). When this occurs, the model typically learns very well on the majority class, but it doesn’t focus on the minority class, which is assigned the greatest importance by the user. This kind of problem includes the paper we discussed previously dealing with insurance fraud, but it can encompass anything where the minority class is the focus: for example, what are the predictors for a high-magnitude earthquake?

We also heard from a couple of professors in the operations research department, which was great because we saw how machine learning and data science can be applied to a business setting.

I also went to a meeting for the RNA group, which was great because I got my C code running on the server, which feels great because I actually have my code helping out with the RNA site! I also talked to Dr. Zirbel about finding a good open problem to work on, and I did some research online to find something that was challenging but not impossible, and I landed on an interesting number theory problem that I want to explore. Basically, starting with the 1st sequence 1, 2, …, create the (i + 1)-th sequence from the elements in the (i)-th sequence by writing i + k, i – k, i + k, … for k = 1, 2, …, i. Then, copy the sequence from the (2i + 2)th point onward. The main sequence is formed by the diagonal of this array. See the picture:

The main sequence goes 1, 3, 5, 4, 10, 7, …

The conjecture is that every single positive integer is contained within that sequence. I hope to make some progress!

Today was mainly a class day, so I’ll talk about that first.

To begin with, I had the probability class, and we were mainly focused on proving the Martingale Convergence Theorem. This theorem essentially states that almost any submartingale (a sequence of random variables where the expected value of each variable is greater than or equal to the previous) will converge as the number of random variables known increases to infinity. Essentially it boils down to ruling out any divergent possibilities: positive infinity, negative infinity, and oscillation. The infinities are relatively easy to rule out due to the properties of martingales and Jensen’s inequality, but the oscillation possibility is more difficult. We didn’t finish this part yet (we will on Wednesday), but it essentially boils down to proving that it is impossible to choose any a and any b (b > a) such that the process will cross from a to b infinitely many times.

We also had the pedagogy class, which was interesting because we talked about exams for the first time. It’s interesting to note the perspective of giving exams, especially for material that becomes increasingly complex for anybody, even a professor, because time becomes a much greater consideration even if you know the material.

As far as the research on path orderings I was doing, I began thinking using Christofide’s algorithm for approximating the TSP in O(n^3) time, but gutting the parts that generate the minimum spanning tree and perfect matching. Essentially, this algorithm guarantees that it can find a TSP path that is no greater than 150% of the optimal path in O(n^3) time. The interesting part here is that the MST and perfect matching are the parts that bring the time up to O(n^3). If I can find some sort of suitable approximation for both of these, then I could probably design a heuristic that runs much faster using the framework of Christofide’s algorithm. I hope that I can also establish an upper bound on the path length relative to the optimal solution. I’m beginning to think it might be too impractical to run it in O(nlog(n)) time, because it’s impossible to check all of the distances in the matrix that amount of time. However, O(n^2) gives you enough time to check each distance in the matrix, so maybe there’s something there. Yes, greedy insertion is also O(n^2), but there isn’t an upper bound I know of.

Today there was not much time for working on my projects, so I’m going to talk about the activities I did.

To begin with, Dr. Zirbel was a guest speaker for a undergraduate data science class. He was discussing the problem of optimal ordering and clustering, which we have already discussed in detail, but it was interesting to see it again. As I’m trying to create some sort of heuristic that will approximate an optimal ordering quickly, I’m thinking about just using a linkage matrix generated by scipy to reduce the number of edges that need to be considered. I then think I should be able to use the generated linkage as a minimum spanning tree with some slight modification that connects edges to vertices instead of to other edges. I’m hoping there is also a easier way to approximate a perfect matching from the linkage matrix. I suppose one could take every cluster containing two vertices as a matching, then somehow compute for the rest.

Later in the day, I went to Dr. Zirbel’s probability and pedagogy classes. In the probability class, we continued to talk about martingales but we introduced Jensen’s inequality, which was a little unintuitive but was also very interesting. For a convex function, the value of the function for the expected value of a random variable x is less than or equal to the expected value of the function of x. In pedagogy, we discussed different ways to teach students who were far behind the rest of their class by graphing some equations in different ways and identifying the strengths and weaknesses of each, such as listing out values, applying a series of transformations, solving for certain values, etc. We also formulated a definition for confidence intervals, which we did because it is difficult to convey the idea in words especially because the terminology becomes confusing when you introduce the probability that some measured value falls within a certain range. Finally, we did an activity where we tried to make a uniform distribution, which is normally difficult for people because they tend to pick 3 and 7 most often. Then, when you repeat it, they avoid those numbers and pick the unfrequented numbers most often, making a non-uniform distribution once again. This was helpful to convey the idea of what it truly means for something to have a uniform random distribution.

To start off today, I worked on making my simulation workable by scanning with respect to the bridge angle, not theta, and looking for the steady states, in which the net torque is zero. After tweaking the program and fixing some bugs, you can see the output of the algorithm below: theta is the x axis and the net torque is the y axis.

To begin with, this presents a numerical solution for my problem– for a given state of the guitar (knowing all constants and the amount that each string has been tightened) we can find the angle of the bridge and therefore the length and tension of each string and their frequencies consequently. From there, we can figure out the proper steps to tune each string such that they are brought in tune by the other strings being tightened: we know the final state and we also know that the amount each string has been wound does not change either– all we need to do is figure out the frequencies at each step.

However, I’d like to find an analytical solution to this problem, not just a numerical solution. That is, I would like to have a specific formula that shows me the zeros of the function above. I’m not quite sure how to get there because the equation for the graph above is very complicated, but I’m going to see if I can make some progress.

Today I also went to a lunch that Dr. Zirbel set up for math majors, which was really nice because I got to talk with other students who were close to my age. This intensive is making me very excited to go to college.

I also went to a meeting with Dr. Zirbel with the officer of sustainability, which was interesting because I like seeing people getting involved with sustainability and the environment. It’s reassuring to know that people are doing what they can to work against climate change and its effects.

As the end of the intensive period approaches, I’m still trying to achieve something with the problems I’ve identified: approximate path ordering and guitar tuning optimization.

On the front of the path ordering, I’m trying to approach the problem from the angle of establishing a theoretical lower bound on length of a heuristic. Even though this sounds simple, this is somewhat difficult to quantify– selecting a random path has the minimum length of the optimal path, so we need a more complex metric to measure this. Perhaps it is possible to measure the minimum path length with respect to a random input. I’m hoping that there is some way to relate algorithms that are deterministic (they don’t get their solutions from random variables) and randomized algorithms. For example, one of the best known TSP approximation algorithms is Christofides’s algorithm, which is entirely deterministic: it uses the minimum spanning tree and the minimum length perfect matching too construct a path. Is there a way to relate the information needed by that algorithm to another that depends on random input, like greedy insertion? As far as actually writing an algorithm, I’m beginning to think that it would be most productive to take Christofides’s algorithm and exchange the exact solutions for the MST and matching for approximations.

For the other problem, the guitar tuning problem, things have been going much more slowly. I’ve moved some equations around, but it seems much too complicated to find a bridge angle theta for which the torque on the bridge is zero after the strings have been wound a distance w0, w1, …

With such a difficulty, I’ve decided to shift my approach to a more numerical method– simulation. I briefly implemented a simulation based on physical properties like angular acceleration, etc, but I think I’m just going to sample the space of various bridge angles and string winding distances. You can see the results of my time-domain simulation below. It didn’t seem to give any comprehensible result, which I believe is due to the tendency of the system to oscillate. I need to add some kind of dampening for the angle to converge as it does in reality.

Today I resumed my progress working on the ordering algorithm. I’ve decided that I’m going to try to create some sort of derivative version of the merge sort, an algorithm that orders lists in n log n time by merging and sorting lists until every element has been merged into the final sorted array. The heuristic I worked on today merges two arrays by interleaving them and iterates over groups of three and adjusts the order to minimize the path length within each chunk. This heuristic is able to slightly improve upon the score of a random path because it optimizes adjacent points, but it does nothing as far as larger scale order. A distribution of the ratio of the new path length vs the associated random path is shown below.

• 

As you can see, the mean indicates a ~7% reduction in path length, which is barely anything, but it indicates that it is doing something! However, the fact that there are paths that cross above 1.0 (they are longer than the original) is somewhat troubling. I suspect this just has to do with the random recombination of the paths. Perhaps it would be better to compare the reordered path against the interleaved path instead of the original random path…

Today also involved the exploring machine learning class. Again, we talked about the insurance fraud detection paper, which made for a very interesting discussion, as the paper produced great results while barely explaining their methods. It was really interesting to discuss not only the fact that the author made a few mathematical errors, but the writing process that might have guided them there– it’s common to edit your paper to remove something that didn’t work and replace it with something that did, but you often forget to correct the wording. I’m excited to discuss a method for oversampling data next week because then we can actually get into methods for data science.

Today, I started off the ordering algorithm by looking into the merge sort, which is a normal sorting algorithm that works by slowly building up the list into a sorted version. I hope to implement something similar for multidimensional data, but there are a lot of difficulties. One of these is the fact that comparisons have to be made between sets of three points, not two like in the sort. Essentially, I think each merge will boil down to some sort of insertion that doesn’t compare all against all like greedy insertion does.

I also began looking into a new problem: the optimal method for tuning a guitar with a floating bridge. In guitars with floating bridges, the bridge (where the strings are attached) has springs attached to the interior of the body and pivots up and down. The issue with this is that restringing/retuning the guitar is very difficult because changing the tuning of one string adjusts the angle of the bridge and disturbs the tuning of each other string. There must be a method of “overtuning” each string such that each one is brought into tune as the other strings move the bridge.

I’m not quite sure how to solve this yet, but I’ve formulated equations for the length and the tension of the strings. I believe there will probably be some differential equations involved as it is necessary to study the change of the bridge angle with respect to the stretching applied to a string as it gets tuned. I hope that I can solve this problem and hopefully make things a little easier for some people! This weekend I plan on collecting some actual data needed for the calculations, such as the linear density and spring constant for each string.

Today started off with a continuation to the meeting last week with one of Dr. Zirbel’s graduate students. We continued talking about the SSS problem, and looked at some graphs that made some really interesting patterns. It was fascinating that there were peaks along the x-axis that you could connect with a straight line. The function seems to have some really interesting complexity, almost fractal in a way. I’m hoping that I can experiment with it on my own if I have time.

Today, I also worked on the path length optimization. Before I actually start developing my algorithm, I’m trying to get an idea of how the RNA distances work. I know they don’t obey the triangle inequality, but I’m hoping that the distance from A to B and B to C tells you at least something about the distance from A to C. Here’s a graph I plotted that examines the relationship above from a medium sized set of RNAs.

Each point represents a single combination of all of the possible combinations of three different RNAs. The y axis is the sum of the two side lengths, and the x axis is the single side length. If the triangle inequality held, every single point would be above the blue line. However, some points obviously cross it. What’s interesting, though, is that the cluster in the bottom left seems to be nicely fit around the line. The cluster on the right, while not showing as neat of a conformation, does have a diagonal edge at the bottom. What this tells me is that there has to be some information here that the heuristic can infer about a distance from two related distances.

I’m hoping tomorrow to start developing the heuristic. Basically, I need to figure out the best way for it to traverse the information in the graph above efficiently and without falling into problems.

I started today off by going to the math undergraduate committee meeting. Dr. Zirbel is the new chair for that committee, so it was cool to see how the math department is trying to improve everything possible for the undergraduates. I also attended the probability class for the second session– I’m beginning to get used to the formality involved in the definitions and proofs of the math. Finally, I also went to a Putnam competition meeting at the end of the day, which was cool to be at because there were undergraduates there.

I also worked on my problem today. I first decided to make some graphs to figure out what I was working with. I sampled about a hundred thousand random paths through 100 points and plotted their length, and it looks like a pretty standard bell curve. I think repeated that for the greedy insertion algorithm, which also produced a bell curve, but shifted greatly to the left. Ideally, I will develop something that produces results somewhere in between these but at a faster rate than either. So far, what I’m trying to figure out is what information, if any, I can gather from the distance from a point A to B and point B to C that gives any insight into the distance A to C. Because these distances are between RNA 3D structures, they do not obey the triangle inequality: for three points related in the aforementioned manner, two sides must be greater than or equal to one side.

I’m trying to gather this information by plotting it and just calculating how many triangles do obey the inequality, or if you can construct a modified triangle inequality, but my guess is that a lot more investigation is needed. However, I think this is definitely a meaningful route to pursue because the triangle equality gives an upper bound on a third distance when you only know two– very useful when you need to generate a short path in a small amount of time.

The setup I have my graphs in is not ideal, but when I get a chance, I’ll upload some pictures to this page.

Edit: below are my graphs. The first represents the distribution of path lengths when randomly sampling paths between 100 points, and the second represents the distribution when running the greedy insertion heuristic. As you can see, both are nice bell curves, but greedy insertion is shifted much further towards the origin and it is narrower, indicating that it performs fairly well and consistently.