In a monotonically increasing sequence, each element is bigger than the last. For example, the sequence of primes, $2, 3, 5, 7, 11, 13, ...$, is monotonically increasing. In its doppelganger, a monotonically decreasing sequence, every element is less than the one before. Examples include $1/2, 1/3, 1/5, 1/7, 1/11, 1/13, ...$ $-2, -3, -5, -7, -11, -13, ...$, and lots more that you could make up yourself.
This function asks whether a list is monotonically increasing:
def is_mono_inc(seq):
return all([seq[i] > seq[i-1] for i in range(1, len(seq))])
seq = [1 , 1, 2, 3, 5, 8, 13, 21]
print(f"{is_mono_inc(seq)=}")
Define your own list below and then use mono_inc() to ask whether it's monotonically increasing.
Now, define the function mono_dec() to test whether a sequence is monotonically decreasing, and try it out.
If a sequence is either monotonically increasing or decreasing, we just say it's monotonic.
Define the function mono() to see whether a list is monotonic.
"monotonic" is math-speak for "sorted".
When two or more numbers in the sequence are equal, you've run into an edge-case. Such a list could be sorted, but not monotonic. Consder the list l = [0,1,1,1,1,1,50]. This is sorted but neither monotonically increasing nor decreasing.
There are at least two easy ways to weasel out of this: one is to call such a list "monotonically non-decreasing." A second, often more useful, is to stick to sequences where that will never happen. For example, if you confine yourself to sequences of random reals, the probability of duplicates in that sequence is zero.
(The mathematician would say, "The set of real sequences that are monotonically non-decreasing, yet not monotonically increasing, is of Lebesgue measure zero," largely to show off his ability to pronounce "Lebesgue.")
While we can't generate reals in Python, floats suffice: the odds of duplicates in even very long list of random floats isn't zero, but it's so small that you can test for them and throw exceptions when they occur.
Neither can we actually generate random floats, but pseudo-random-number generators are good enough in practice. Honest.
N.B., From here on out, when we say "sequence," we'll mean a sequence of reals, and our Python programs will manipulate lists of (pseudo-)random floats.
We'll also use "sorted" instead of "monotonic" so our family can know what we're talking about.
We'll leave edge cases and technical jargon to the mathematicians.
Sorted sequences are interesting, but rare. In a sequence of length N, only 1 of the N! permutations will be sorted in increasing order, and a second in decreasing. math.factorial(N) caculates $N!$. If you generate one random real every morning, at the end of the week, the probability that your sequence will be sorted is
import math
1/math.factorial(7)
What if you do it every day for a year?
1/math.factorial(365)
The number is too small to track -- lost in the noise.
Sorted sequences are rare. Let's lower our expectations.
To do that, begin with this different, yet equivalent, definition of sorted:
Put your finger between two, successive terms of your sequence. Suppose you discover every number to the left of your finger is less than every number to its right. If that's true no matter where you put your finger, the sequence is monotonically increasing -- it's sorted.
In code
def is_mono_inc2(seq):
n = len(seq)
for i in range(1, n):
if max(seq[:i]) > max(seq[i:]):
return False
return True
print(f"{is_mono_inc2(seq)=}")
Try this function on the sequences you defined earlier to verify you get the same answer.
Suppose that you buy a stock whose value changes every day. If its value increased monotonically over the year, you'd be delighted.
If, however, its value dipped slightly on the next-to-last day, but then went back up on New-Year's Eve, you'd still be happy.
Even more general: suppose that the stock price bounces up and down, but when you write them all down, you discover that the sequence of daily prices is interesting: wherever you put your finger, the average of all the stock prices to its left is less than the average of all those to its right. The price isn't rising uniformly, but it's rising on average. Each day, at close-of-market, the days ahead are going to be better, on average, than the days gone by.
On average, things are always looking up.
We'll call this kind of sequence a trend.
from statistics import mean
def is_trend(s):
n = len(s)
for i in range(1,n):
if mean(s[:i]) > mean(s[i:]):
return False
return True
seq = [1, 2, 4, 8]
print(f"{seq=} -> {is_trend(seq)=}")
seq = [1, 2, 8, 4]
print(f"{seq=} -> {is_trend(seq)=}")
seq = [1, 8, 2, 4]
print(f"{seq=} -> {is_trend(seq)=}")
Make some sequences, then use is_trend() to test whether they're trends.
By the way, there are both rising and falling trends. It's easier just to talk about one or the other. We'll arbitrarily pick rising trends. When we say trend, it'll usually mean rising trend."
A mathematician might throw in, "Without loss of generality ..."
This choice is analogous to the one we're used to for sorting. sort() and sorted(), make monotonically increasing sequences, unless you give them the reverse=True flag.
We can go back and make statements and functions for falling trends that are mirror-images of the ones we make for rising trends. Keep this in your back pocket to pull out whenever you need it. When we do, we'll say so.
You have already noticed that you can trivially turn any random sequence into a monotonic sequence, like this:
week = 7 # days to generate random numbers
from random import random
rand_week = [random() for _ in range(week)] # a sequence of 10, random reals in [0,1)
print(f"{rand_week=}")
sort_week = sorted(rand_week) # the same numbers, sorted
print(f"{sort_week=}")
(If you beat the 2-in-ten-thousand odds against randomly generating a sorted sequence, please just go back and generate another sequence.)
Can you turn the same sequence into a trend? Sure. A monotonically increasing sequence is also a trend. Just call sorted().
That doesn't get you anything new, though, so let's explore ... just play around a little.
Even if rand_week isn't sorted, does it have a trend in it?
Is there, for example, a trend that starts at the left end -- a prefix-trend -- even if it doesn't continue to the end?
We'll start, naively, at the left end and move to the right for as long as the elements are still in a trend.
def naive_pfx_trend(s):
for i in range(1, len(s)):
if not is_trend(s[:i]):
return s[:i-1]
print(f"{rand_week=}")
print(f"{naive_pfx_trend(rand_week)=}")
Make up some other sequences and try naive_pfx_trend() on them.
This seems too cautious. We're shooting too low.
Here's why: What about a sequence that dips enough to end an early trend, but then picks back up again? What about, say, [1, 4, 2, 8, 16], which isn't sorted, but is a trend taken as a whole?
seq = [1, 4, 2, 8, 16]
print(f"{naive_pfx_trend(seq)=}")
print(f"{is_trend(seq)=}")
Seems like our function should just return the whole trend.
More to the point, it should pick this, longer prefix trend out of, say,
[1, 4, 2, 8, 16, 1, 4, 2, 8, 1, 2].
Can we pick out the longest prefix that forms a trend?
Easy. Just start from the other end. Begin with the whole sequence and back up from the right until you find the first, long trend.
def pfx_trend(s):
t = s.copy()
while t:
if is_trend(t):
return t
t.pop()
We're being careful not to modify the original sequence with pop().
We might want to go back and look at it again.
pfx_trend() returns a copy of the original prefix.
s = [1, 4, 2, 8, 16, 1, 4, 2, 8, 1, 2]
print(f"{pfx_trend(s)=}")
print(f"{s=}")
Now we're getting somewhere! Having done that, carve the biggest trend out of what remains.
print(f"{s=}")
pfx_len = len(pfx_trend(s)) # length of that prefix
suffix = s[pfx_len:] # the rest of the sequence
print(f"{suffix=}")
next_trend = pfx_trend(suffix) # the *next* long trend
print(f"{next_trend=}")
You can keep this up until you've decomposed the whole sequence into the biggest trends you can find.
We've played a little fast-and-loose for a minute, using sequences of integers instead of reals, because they take up less space. If it makes you feel better, put a .0 after each int.
It's a tutorial. Go with it.
def trendlist(s):
'''Decompose s into a list of maximal trends.'''
trendlist = [] # all trends in the decomposition
while s:
p = pfx_trend(s) # get the longest prefix
trendlist.append(p) # append it to the list of trends
p_len = len(p) # how long was that prefix?
s = s[p_len:] # get ready to start again with the rest of the sequence
return trendlist
We'll show it off with a long, random sequence.
trends = trendlist([random() for _ in range(100)]) # decompose a long, random sequence
trend_lengths = [len(trend) for trend in trends] # get their lengths
print(f"{trend_lengths=}") # what were they?
print(f"{sum(trend_lengths)=}")
Run this a few times, to see that the decompositions differ every time. (After all, they're random sequences.) Still, this always decomposes the sequence completely: the sums of the trend lengths are always that of the whole sequence.
Try decomposing a sequence or two of your own.
This decomposition is easy, easy-to-understand, and unique.
Now you can ask questions like, "What's the average number of trends in a random sequence?" and "How long are they?"
## Trend Means in a Trendlist Drop From Right to Left
If you think about it, you can see that each trend's mean will always lie between the means of the trends on either side -- less than the one on its left, greater than the one on its right. The trend means are sorted in decreasing order.
trends = trendlist([random() for _ in range(100)])
for trend in trends:
print(f"{mean(trend)=}")
Why? Whenever a trend's mean is less than that of the trend on its right, the two merge into a single, longer trend.
a = trends[2]
b = trends[3]
print(f"{is_trend(a)=}, {is_trend(b)=}, {is_trend(a+b)=}, {is_trend(b+a)=}")
This isn't hard to prove for yourself, if you want to, but proofs are a little out of scope for a tutorial.
Instead, just experiment a little to see for yourself.
Out of the $N!$ arrangements of $N$ random reals, only one is sorted.
How many are trends? At least one, because the sorted sequence is a trend. There are trends that aren't sorted, so more than that. But not all sequences are trends.
Can we say how many are? Yup.
Again, we'll start by decomposing a big, random sequence into trends.
trends = trendlist([random() for _ in range(100)])
for trend in trends:
print(f"{mean(trend)=}")
But now, let's circularly permute those trends.
If you prefer, you can pretty-print your trendlists. Here's an example, using the Python package blessed, which you can get from PyPI with pip install blessed.
(Make sure your pip is pip3, with pip --version.)
import blessed
def print_trends(seq):
trends = trendlist(seq)
term = blessed.Terminal()
for i, trend in enumerate(trends):
trend_l = [f"{elem:0.2f}" for elem in trend]
trend_s = ",".join(trend_l)
trend_p = "[" + trend_s + "]"
print(term.color(i)(trend_p), end="")
print()
Try this with rand_week
trends = trendlist(rand_week)
term = blessed.Terminal()
for i, trend in enumerate(trends):
print(term.color(i)(str(trend)), end="")
Well, that's certainly not impressive!
Why didn't that work? Because jupyter notebook doesn't do color.
This is when we encourage you to bite the bullet and try this in a terminal window of your own.
Here are the steps.
$ pip install trendlist
$ ipython
> from trendlist.simple import print_trendlist, trend_list
> from random import random
> rand_week = [random() for _ in range(7)]
> trends = trend_list(rand_week)
> print_trends(trends)
Try it with some random sequences of your own, too.
If you stick two trends together
[Left] + [Right]
with mean([Left]) < mean([Right])
they just merge into a single trend.
You can even prove it, with a little work.
Put your finger between two numbers in [Left], to split it in two, into [l] and [L],
So [Left] = [l] + [L].
You know that mean(l) < mean(L) because Left is a trend.
But you also know mean(l) < mean(Left) < mean(L) because that's how means work: the mean of two things lies between them.
Next, think about [L] + [Right]. mean(Left) < mean([L] + [Right]) < mean(Right) because, again, that's how means work.
Putting these together, mean(l) < mean([L] + [Right]
In other words, the average of the numbers to the left of your finger is less than the average of the number to its right in the whole sequence, [Left]+[Right]
You can reason the same way to show the same thing for wherever you stick your finger in [Right].
Finally, if you just stick your finger between [Left] and [Right], the mean to its left is less than the mean to its right, because that's how we started. In other words, the two trends, stuck together, make up one big trend.
So, if you have a list of adjacent trends, whenever you see a trend with a smaller mean than its neighbor on the right, you can just merge them into one.
And if you have two trends next to one another but
mean([Left]) > mean([Right])?
Then they can't merge into a single trend. If you stick your finger into the boundary between them, you've found a place where the average of the things to the left isn't less than the average of the things to the right.
A circular permutation of the sequence, S, just peels off the left end of the sequence and sticks it on the right.
def rotate(s, i):
return s[i:] + s[:i]
seq = list(range(10))
rotate(seq, 5)
Suppose you start with a trend, T, and circularly permute it. Is it still a trend?
No way. Before you rotate, mean(s[:i]) < mean(s[i:]), because it's a trend.
After you rotate, the mean of the piece now at the beginning has a bigger mean than the part on the end.
Not a trend!
Before: s = [Left]+[Right] and $\mu(Left) < \mu(Right)$
After: rotate(s, i) = [Right]+[Left] and $\mu(Right) > \mu(Left)$
Ergo, if there's a trend, no other circular permutation can be, too.
But is there one?
Okay, you've arrived.
Take a random sequence, $S = [s_0, s_1, ... s_n]$ .
Decompose it into a list of trends
$T_0 = [A + B + ... K] = [[a_0, a_1, ...] + [b_0, b_1, ... ] + ... [k_0, k_1 ...] ]$
The mean of these trends decreases, monotonically: mean(A) > mean(B) > ... > mean(K)
$T_1 = [K + A + B + ... ] = [[k_0, k_1, ...] + [a_0, a_1, ...] + [b_0, b_1, ... ] + ...]$
mean(K) < mean(A). K and A will merge to make a single trend!Okay, mean(A) > mean(B), so they stayed separate in the original decomposition,
but yes, it's possible that mean(K + A) < mean(B), so they might now merge, too, into K + A + B and so on.
You don't care.
What you do care about is that rotating the sequence this way decreases the number of trends at every step.
Eventually, you'll end up with a single trend.
(1) Every random sequence has a circular permutation that is a single trend. (2) That sequence never has more than one circular permutation that's a single trend.
Here's a function that finds that rotation.
def single_trend(s):
ts = trendlist(s)
if len(ts) == 1:
return s
mean_s = statistics.mean(s)
for t in ts:
mean_t = statistics.mean(t)
if mean_t < mean_s:
return s[rotate:] + s[:rotate]
rotate += len(t)
(This optimizes a little by noticing that every trend on the right end that has a mean less than the overall mean will end up merging into the left on rotation.)
Watch it work on rand_10
print_trendlist(rand_10)
print_trendlist(single_trend(rand_10))
Then try it on a random sequence of your own. Use is_trend() to verify your result.
So:
(1) Any set of $N$ random reals has $N!$ permutations. (1) One of them is monotonically increasing (1) $N!/N = (N-1)!$ are increasing trends. (1) Every real sequence has exactly one circular permutation that's a trend.
If you generate a random number daily, when you wake up in the morning, at the end of the week your chance of having generated a trend is $1/7$. At the end of a year? $1/365$. A 70-year lifespan?
The odds of a 70-year-lifetime's worth of daily, random floats being monotonic? Bupkis. Of being a trend? About 1/25,000.
Maybe you didn't expect that.
In your city (or the nearest city to you), if everyone generated a random real, every morning, about how many would generate a single trend over a lifetime? If you don't know the approximate population size, you can google it, ask Alexa, or go to your bookshelf and look it up in your gazetteer.