When my 8 year old twin nieces asked me what I do at my new job, I told them a story: “Imagine you meet a person who is traveling through the whole world. If he told you he started traveling an hour ago, you’d guess he started in the same city you are in. If, however, he started a day ago, he might have already traveled between cities, but you could still guess that he started from the country you are in. In a week he might have traveled through several countries, but maybe did not cross continents. If the person told you that he has traveled for a year, you would have a really hard time guessing where his travels started. My job is to find out how much time it takes for you to have no idea as to where he started his travels.” I was happy that I was able to simplify the concept of ‘mixing time’ for 8 year olds, but I’m guessing that you, the reader, might be just a bit older than my two young nieces.This simplification applies to both the mathematical probability theory term of mixing time (which we will not discuss here) and to mixing time in the context of the Tangle network.The need for such a term in our context comes from real-world performance limitations. The default tip selection algorithm uses a random walk that starts at a given transaction called a starting point. As new transactions join the Tangle, the distance of a starting point to the tips constantly grows. The greater that distance is, the more computational resources required.As time goes by, a node would therefore want to replace an old starting point with a new one, without degrading the quality of its tip selection process. If a node picks a bad starting point, it is likely to attach transactions that wouldn’t be quickly selected by other nodes. Picking a new starting point that would select the same tips as the old one is desired. Luckily, it turns out that the older two candidate starting points are, the more likely they are to select the same tips. So there we have it: The mixing time of a Tangle is how far you have to go back before any two candidate starting points behave in the same way.We now have a rough definition of mixing time.There are, of course, more formal definitions behind words like “candidate”, “behave”, and “the same”, but in order to spare readers from unnecessary details, we will skip those and move on to the more interesting parts.When the tip selection process of a node becomes too resource intensive, the node can replace the old starting point with any candidate starting point that is at least as old as the mixing time! Now we only need to figure out what the mixing time is for any specific Tangle. It turns out that producing an analytical model for mixing time is infeasible due to the complexity of the problem. Furthermore, while calculating mixing time for a Tangle is possible, it is too cumbersome to be performed constantly by nodes. We can, however, run numerical experiments on simulated nodes, and analyze the results in order to try to understand and predict the behavior of the mixing time.We have built a numerical simulator to create Tangles with transaction arrival rates of λ per unit of time and with tip selection that follows the random walk algorithm with parameter α, and calculated their mixing times.For one such Tangle, with λ of 512, α of 0.00069, and about 100,000 transactions, we have plotted each of its transaction on a two-dimensional plot, where the x-axis shows the age of the transaction, and the y-axis shows how close to the old starting points it behaves. (where 1 indicates the same behavior, and 0 indicates a totally different one).Similarity vs age for λ=512, α=0.00069We can see that in this Tangle, all transactions older than 69 are very similar to the old starting point, therefore, selecting any of these transactions as the new starting point will not result in a noticeable change in future tip selection!However, not all Tangles are as nice. For instance, here is a Tangle with λ of 32, and α of 0.0441:Similarity vs age for λ=32, α=0.0441Here not all transactions reach the top of the plot. We can see at the bottom the transactions that are ‘left behind’, and therefore become very bad as starting points, (as there is nowhere to walk forward in a random walk that starts there). Luckily, we can identify these transactions easily and exclude them as candidate starting points. Once excluded, mixing time remains valid — every remaining candidate starting point older than mixing time will preserve the behavior of our tip selection.The ratio of the transactions that remain valid candidates has already been discussed here in the ‘Confirmation rates in the Tangle’ blog post. The confirmation rate of the Tangle in the first plot is 1 (no transactions left behind), and 0.95 for the second plot. (5% transactions left behind).Evaluating both mixing time and confirmation rate for more than 200 Tangles with different λ and α values yields this table:Mixing time and confirmation confidence for different TanglesIn this table, each row represents a certain α value, and each column represents a certain λ value. Each Tangle is represented by two numbers — confirmation rate on the left and the mixing time on the right. By coloring these values we can notice the trends and make observations about the relations between α, λ, mixing time, and the confirmation rate:Tangles built with lower α values are ‘healthier’ in term of confirmation rate — there are fewer transactions that are left behind to be never confirmed. This means that we’ll be happy if everyone would use low α values, but there are other considerations here at play (which are subject to further research and a completely new blog post).Mixing time grows with the incoming transaction rate λ, but at a much slower pace. Multiplying λ by 100 raises mixing time by about 2, at least for lower α values. Future work will include simulations with larger λ values, to see how this trend continues.The highest mixing times are of Tangles with high λ values and moderate α values. What is special about that range of α values? How would that behavior look for even higher λ values?We have progressed far and beyond the story about the world traveler, produced interesting data and challenging questions. Further analysis and answers are due in order to define a method of starting point replacement, as well as to improve our understanding of the intricate behavior of The Tangle.As always, your comments and questions are very welcome, either here or through Twitter — @DanyShaanan.Mixing Time in The Tangle was originally published in IOTA on Medium, where people are continuing the conversation by highlighting and responding to this story.