My database patent finally has been granted after a long and expensive ordeal. While this is better than not having it granted after a long and expensive ordeal, it still was a truly pathetic reflection on the state of the American patent system. My perception (and, from what I can gather, that of most sensible individuals) is that the American intellectual property system as a whole is broken beyond repair and is one of the primary impediments to real innovation in this country. The system only serves large corporations with deep pockets and large teams of lawyers — and they mostly use it to troll smaller companies or build defensive portfolios to deter competitor lawsuits.
But enough about the sewage dump known as the US Patent system; my thoughts on it are unambiguously expressed here. Instead, this is a happy post about happy things. And what makes people happier than a stream database?
My patent is for a type of stream database that can be used to efficiently manage and scan messages, business transactions, stock data, news, or myriad other types of events. It is the database I wish I had when I was doing high-frequency statistical arbitrage on Wall Street, and which I subsequently developed and refined.
I’ll post a more detailed discussion of it shortly, but here is the basic gist. The idea is based on a sort of indexed multiply-linked-list structure. Ok, maybe that’s too basic a gist, so I’ll elaborate a little.
To use a common example from stock trading, we may wish to query something like the last quote before a trade in a stock. As an individual query, this is easy enough to accomplish in any type of database. However, doing it efficiently and in high volume becomes more challenging. Standard relational and object databases quickly prove unsuitable. Even stream databases prove inadequate. They either require scanning lots of irrelevant events to arrive at the desired one or waste lots of space through sparse storage and/or are constrained to data at fixed intervals. But real data doesn’t work that way. Some stocks have lots of trades and few quotes, others have few quotes and lots of trades. Events happen sporadically and often in clusters.
My approach is to employ a type of multiply-linked list. Each entry has a time stamp, a set of linkages, and a payload. In the stock example, an event would link to the previous and next events overall, the previous and next events in the same stock, and the previous and next events of the same type and stock (ex. quote in IBM or trade in Microsoft). To speed the initial query, an index points to events at periodic intervals in each stock.
For example, to find the last quote before the first trade in IBM after 3:15:08 PM on a given day, we would use the index hash to locate (in logarithmic time) the latest trade prior to 3:15PM in IBM. Then we would scan trades-in-IBM forward (linkage 3) until 3:15:08 to pick the latest. Then we would scan IBM backward (linkage 2) from that latest trade until we encounter a quote.
We also could simulate a trading strategy by playing back historical data in IBM (linkage 2) or all stock data (linkage 1) over some period. This could be done across stocks, for individual stocks, or based on other specific criteria. If there are types of events (example limitbooks) which we do not need for a specific application, they cost us no time since we simply scan the types we care about instead.
This description is vastly oversimplified, and there are other components to the patent as well (such as a flow manager). But more on these another time.
If you’re curious, the patent is US 11593357 B2, titled “Databases And Methods Of Storing, Retrieving, And Processing Data” (originally submitted in 2014). Since the new US Patent Search site is completely unuseable (and they don’t provide permalinks), I’ve attached the relevant document here.
over parameters 
(with state space 
). We acquire some data 
, and wish to use it to infer 
is easy to compute or sample, and (3) the normalization 
is not expensive to compute or adequately approximate.
. However, there also is another view we may take. We need not restrict ourselves to a single Bayesian update. It is perfectly reasonable to ask whether multiple updates using the same 
. Our method is conceptually equivalent to performing successive experiments which happen to produce the same data 
is a derived normalization factor, nothing more.
, and denote the elements of 
.
-vectors to denote probability or conditional probability distributions over 
component the probability of 
), but it turns out to be simpler to use diagonal 
matrices.
with 
.
the data set 
times. I.e., the equivalent of having performed an experiment 
is an 
with 
).
via an 
, with 
. Note that 
and 
.
with 
.
is a scalar. In our notation, 
.
. What happens if we repeat this? A second iteration substitutes 
. This is homogeneous of degree 
in 
normalization factor in 
. The same reasoning extends to 
.
, and let 
. Our expression for 
after 
.
, which can be written 
. We know that 
, so as long as 
we have 
. Specifically, for 
we have 
for 
. Note that the denominator is negative since 
and the numerator is negative for small enough 
.
. If we perform the same analysis for 
, we get 
, which corresponds to 
. The denominator diverges for large enough 
.
. As 
, all but the dominant 
are exponentially suppressed. The net effect of infinite iteration is to pick out the maximum likelihood value. I.e., we select the 
for 
and 
. It is easy to see what happens in this case. 
, so 
and 
. Note that 
here, but we stated the denominator explicitly to facilitate visualization of the extension to 
degenerate maximum 
(each 
). The limit of iterated posteriors 
. This reduces to our previous result when 
.
for the maximum likelihood 
‘s from contention for the maximum likelihood.
to a countable set poses no problem. In the continuous case, we must work with intervals (or measurable sets) rather than point values. For any 
be the maximum likelihood probability. If we consider an interval 
as our maximum likelihood set, then the maximum likelihood “value” is the (measurable) set 
. For any 
for 
. However, for a fixed 
. Put another way, we cannot simply assume uniform convergence.
update. In that case, we keep the original prior and view the posterior as the aforementioned pruned version of the prior.
.
‘s. All others are irrelevant. The maximum likelihood values typically form a tiny subset of 
and the false negative rate 
.
the event of having Covid, and by 
the event of testing positive for it. 
is the prior probability of having covid. It is your pre-test estimate based on everything you know. For convenience, we’ll often use 
, where 
denotes the outcome of the test: either 
.
and 
. These numbers are properties of the test, independent of the individuals being tested. For example, the manufacturer could test 1000 swabs known to be infected with covid from a petri dish, and 
would be the number which tested negative divided by 1000. Similarly, they could test 1000 clean swabs, and 
would be the number which tested positive divided by 1000.
that you are infected given that you tested positive, and (2) the probability that you are not infected given that you tested negative 
. I.e. the probabilities that the test correctly reflects your infection status.
, a direct consequence of the fact that 
.
, which is 
. The prior of infection was 
. For 
.
).
, or about 0.7%. We will define 
.
more likely to be infected post-test than pre-test. This seems significant! Unfortunately, the actual probability is 
.
.
. For small 
.
as the prior, the probability of being uninfected post-test is 0.99757 vs 0.9932 pre-test. For all practical purposes, our knowledge has not improved.
-axis). Note that graph 1 has an abbreviated 
, it provides near certainty of infection.
and “sensitivity” refers to 
. See 
, de Rham Complex, review of some diff geom, Lie deriv and bracket, chain complexes, chain maps, homology, cochain complexes, cohomology, tie in to cat theory.
: Used for a Principal bundle. Not really used here, but mentioned in passing.
as a map from the de Rham complex to the singular cochain complex
and 
means
and 
: as 
-dimensional vector spaces over 
or as finite-basis modules over the smooth fns on M. The former is useful for abstract formulation while the latter is what we calculate with in DG. The transition between the two can be a source of confusion.
unconstrained fantasy teams, ultimately evaluating under 
million plausible teams and executing in under 
seconds on a relatively modest desktop computer. 
of players which constitute a fantasy team. A fantasy team must have precisely this number of players.
players from one position and 
each from 
players on a team, with specified positions P,P,C,1B,2B,3B,SS,OF,OF,OF. Salary cap is $50K. Constraints: (1) 
hitters (non-P players) from a given real team, and (2) players from 
different real games must be present.
players, with no position requirements. Salary cap is $50K. Constraints: (1) players from 
hitters from any one team.
hitters (non-P players) from a given real team, and (2) players from 
players, with 2 pitchers and 5 hitters. Salary cap is $50K. Constraints are: (1) 
players, with 2 pitchers and 6 hitters. $50K salary cap. Constraints are: (1) 
such teams (for some 
groups. It is easy to see that the 
hitter per team constraints fit this mold.
denotes player 
in our listing.
of games represented in the given tournament. This would be all the games played on a given day. Almost every team plays each day of the season, so this is around 15 games. We’ll ignore the 2nd game of doubleheaders for our purposes (so a given team and player plays at most once on a given day).
of teams represented in the given tournament. This would be all 30 teams.
of length 
of length 
of length 
of length 
of length 
of length 
if player 
if a pitcher, where 
, the teams from 
, and the positions from 
. We’ll assign 
to the pitcher category in the 
. The vectors 
groups (the positions), and marked as a partition.
groups (the teams), and marked as a partition.
groups (the games), and marked as a partition.
groups (the teams for hitters plus a single group of all pitchers), and marked as a partition.
(i.e. P,P,C,1B,2B,3B,SS,OF,OF,OF)
(i.e. 
)
(i.e. 
(i.e. 
(i.e. 
)
items in any one group of Feature 4. (i.e. 
. For a given group, we do this as follows. Assume that we are required to select 
and value 
then we cull item 
groups with (
,
,
,
) allowed items. We need to select 
items from amongst these. In reality, fantasy baseball tournaments with flex groups have fewer other groups — so the size isn’t quite this big. But for other Fantasy Sports it can be. 
. Suppose we can prune just 1/3 of the players (evenly, so 30 becomes 20, 60 becomes 40, and 90 becomes 60). This reduces the state space by 130x to around 
. If we can prune 1/2 the players, we reduce it by 
to around 
. And if we can prune it by 2/3 (which actually is not as uncommon as one would imagine, especially if many items have 
to a somewhat less unmanageable starting point of 
. 
operations (it doesn’t), where 
is the non-flex group size and 
which is 
operations. In reality it would be far lower. So a careful cull is well worth it!
. If it is set too high, we will cull too few items and waste time down the road. If it is too low, we may run into problems meeting the ancillary constraints. 
and cost 
in order to cull an item with value 
to reflect this. If 
is the number of selected items for group 
strictly better items. Note that 
is the total number of items in the 
group. Some of the same items may be available to multiple groups, but our collection must consist of distinct items. So there are 
bins, the number of primary feature groups. For the 
possible selections. We can precompute this easily enough.
. I.e. the product of the total combinations of this group and those that come after.
is the sum of the top 
is 
. I.e., the best total value we can get from all subsequent groups.
is the sum of the bottom 
is 
. I.e., the cheapest we can do for all subsequent groups, if value is no concern.
) or from most to fewest (high to low 
). We also are given 
, the lowest collection value we will consider. We’ll discuss how this is obtained shortly. 
sorted by value or by cost depending on our 2nd choice above. I.e., we are iterating over the possible selections of 
is the minimum cost of all remaining groups (
onward). This is the lowest cost we possibly could achieve for subsequent groups. It is the pre-computed 
is the maximum value of all remaining groups (
is the cost of our current selection for group 
is the value of our current selection for group 
then there is no way to select from the remaining groups and meet the cost cap. Worse, all remaining iterations within group 
then there is no way to select a high enough value collection from the remaining groups. However, it is possible that other iterations may do so (since we’re iterating by cost, not value). We prune just the current selection, and move on to the next combo in group 
and value 
and group 
. We need to maintain a value-sorted list of our top collections in a queue-like structure. 
, the best value realized, This also resets 
for some user-defined tolerance 
. We then must drop any already-accumulated collections which fall below the new ![{\epsilon\in [0,\infty]}](https://s0.wp.com/latex.php?latex=%7B%5Cepsilon%5Cin+%5B0%2C%5Cinfty%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
?
we report back (or do we keep them all)?
![{\delta\in [0,1]}](https://s0.wp.com/latex.php?latex=%7B%5Cdelta%5Cin+%5B0%2C1%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
?
or 
will do. As mentioned, 
. There is good reason to believe that, for any common tournament structure, the results would be consistent once established. It also is likely they will reflect these. Why? The fastest option allows the most aggressive pruning early in the process. That’s why so few collections needed to be analyzed. 
regardless of whether we switch or not. But you weren’t asked to improve on the probability, just to maximize your expected payment. Consider the following 3 arguments:
. If it is wrong to switch then the other envelope contains 
, but if it is right to switch it contains 
. There are even odds of either, so your expectation if you switch is 
. This is better than the 
. If it is wrong to switch then the envelope you chose contains 
, and if right to switch it contains 
. If you switch, you get 
. So it always is better NOT to switch! 
and 
(though you don’t know which envelope contains which). You pick one, but there is equal probability of it being either 
. If you switch, the same holds true for the other envelope. So you still have an expected reward of 
. If we switch, then 
. If we keep the initial envelope then 
. Whether we switch or not, the expected value is 
or 
. We must now draw an important distinction. It is correct that 
or 
with equal probability. We defined 
. It determines which two numbers 
we are dealing with. We do not know 
with 
. The envelopes thus contain 
for some integer 
of the values involved (taking care to use 
for some 
(defined to be the lesser of the two). We open one, and see 
. If it is the upper then the pair is 
, otherwise the pair is 
. To claim that these have equal probabilities means that 
and 
are equally probable. We made this assumption independent of the value of 
.
![{[M,N]}](https://s0.wp.com/latex.php?latex=%7B%5BM%2CN%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
, which we supposedly know or assume apriori. We certainly can impose a uniform distribution on it. Each pair 
with ![{n\in [M,N-1]}](https://s0.wp.com/latex.php?latex=%7Bn%5Cin+%5BM%2CN-1%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
. But now we’ve introduced additional information (in the form of 
). For any 
and 
. If we know ![\displaystyle \langle V_K \rangle= \sum_{n=-\infty}^\infty P(n) [P(m=n|n) 2^n + P(m=n+1|n) 2^{n+1}]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Clangle+V_K+%5Crangle%3D+%5Csum_%7Bn%3D-%5Cinfty%7D%5E%5Cinfty+P%28n%29+%5BP%28m%3Dn%7Cn%29+2%5En+%2B+P%28m%3Dn%2B1%7Cn%29+2%5E%7Bn%2B1%7D%5D&bg=fefeeb&fg=000000&s=0&c=20201002)
for either of the two envelope orders. So we have 
. We immediately see that for this to be defined the probability distribution must drop faster than ![\displaystyle \langle V_S \rangle= \sum_{n=-\infty}^\infty P(n) [P(m=n|n) 2^{n+1} + P(m=n+1|n) 2^{n}]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Clangle+V_S+%5Crangle%3D+%5Csum_%7Bn%3D-%5Cinfty%7D%5E%5Cinfty+P%28n%29+%5BP%28m%3Dn%7Cn%29+2%5E%7Bn%2B1%7D+%2B+P%28m%3Dn%2B1%7Cn%29+2%5E%7Bn%7D%5D&bg=fefeeb&fg=000000&s=0&c=20201002)
we get the same answer.
![\displaystyle \langle V_S \rangle= \sum_m P(m) [P(n=m|m) 2^{m+1} + P(n=m-1|m) 2^{m-1}]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Clangle+V_S+%5Crangle%3D+%5Csum_m+P%28m%29+%5BP%28n%3Dm%7Cm%29+2%5E%7Bm%2B1%7D+%2B+P%28n%3Dm-1%7Cm%29+2%5E%7Bm-1%7D%5D&bg=fefeeb&fg=000000&s=0&c=20201002)
and 
. We know that 
. Plugging these in, we get
![\displaystyle \langle V_S \rangle= \sum_m [0.5 P(n=m) 2^{m+1} + 0.5 P(n=m-1) 2^{m-1}]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Clangle+V_S+%5Crangle%3D+%5Csum_m+%5B0.5+P%28n%3Dm%29+2%5E%7Bm%2B1%7D+%2B+0.5+P%28n%3Dm-1%29+2%5E%7Bm-1%7D%5D&bg=fefeeb&fg=000000&s=0&c=20201002)
. We can rewrite the index on the 2nd sum to get 
, which gives us 
, the exact same expression as before!
exactly offsets the average gain from switching in all other cases. We do no better by switching than by keeping.
or 
but not both). To meaningfully analyze the problem we require a slightly stronger assumption, though: specifically that the set from which they be drawn (without repetition) possesses a strict linear ordering. However, it need not even possess any algebraic structure or a metric. Since we are not concerned with expectation values, no such additional structure is necessary.
(i.e. 
for all real 
stick with the initial choice, otherwise switch. We’ll refer to 
because the probability that 
has measure 
glance, this seems pointless. It feels like all we’ve done is introduce a lot of cruft which will have no effect. We can go stand in a corner flipping a coin, play Baccarat at the local casino, cast the bones, or anything else we want, and none of that can change the probability that we’re equally likely to pick the lower envelope as the higher one initially — and thus equally likely to lose as to gain by switching. With no new information, there can be no improvement. Well, let’s hold that thought and do the calculation anyway. Just for fun.
the values in the two envelopes in order. I.e., 
by definition. In terms of 
and 
. We’ll denote our contrived distribution 
and cdf 
.
or 
. So 
. There are no subtleties lurking here. We’ve assumed nothing about the underlying distribution over 
. Whatever 
and 
and 
. The latter forms the criterion by which we will keep 
is just notation for “the probability the sampled value is greater than 
and 
since by assumption 
is monotonically increasing (we assumed its support is all of 
there is a greater probability that 
than 
. We shouldn’t switch. A similar argument shows we should switch if 
.
, of course. We’ll return to this shortly, but first let’s revisit the assumptions which make this work. We don’t need the envelopes to contain real numbers, but we do require the following of the values in the envelopes:
is the true underlying distribution over 
since we are handed the envelopes to begin with. Perhaps the game is played many times with values drawn according to 
unless 
. We don’t employ a factor of ![\displaystyle \begin{array}{rcl} P(win)= \int_{x<y} dx dy Q(x,y)[p(z=x|(x,y))p(x<d) \\ + p(z=y|(x,y))p(d<y)] \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Brcl%7D++P%28win%29%3D+%5Cint_%7Bx%3Cy%7D+dx+dy+Q%28x%2Cy%29%5Bp%28z%3Dx%7C%28x%2Cy%29%29p%28x%3Cd%29+%5C%5C+%2B+p%28z%3Dy%7C%28x%2Cy%29%29p%28d%3Cy%29%5D+%5Cend%7Barray%7D+&bg=fefeeb&fg=000000&s=0&c=20201002)
since those are the immutable 50-50 envelope ordering probabilities. After a little rearrangement, we get:
over the joint distribution 
. However, we cannot directly use 
because we defined 
and we don’t know whether 
or 
. Let’s start by computing the probability of 
(being the observed and unobserved values).
we integrate this. 
. This is a good point to introduce two quantities which will be quite useful going forward.
![\displaystyle p(z)= \frac{1}{2}[I_1(z)+I_2(z)]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+p%28z%29%3D+%5Cfrac%7B1%7D%7B2%7D%5BI_1%28z%29%2BI_2%28z%29%5D&bg=fefeeb&fg=000000&s=0&c=20201002)
. This gives us:
. It is easy to see that:
, we can figure that out. 
and 
is the symmetrized version. ![{\int q(w,z)dw= \int dw [Q(w,z)+Q(z,w)]= (P_2(z/2)+P_2(2z))}](https://s0.wp.com/latex.php?latex=%7B%5Cint+q%28w%2Cz%29dw%3D+%5Cint+dw+%5BQ%28w%2Cz%29%2BQ%28z%2Cw%29%5D%3D+%28P_2%28z%2F2%29%2BP_2%282z%29%29%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
. So 
. This is just what we’d expect — though we’re really dealing with discrete values and are being sloppy (which ends us up with a ratio of infinities from the 
. From a purely probability standpoint, we should switch if 
. If we reimpose the algebraic structure and try to compute expectations (as in the previous problem) we would get an expected value of ![{z[P_2(z/2)/2 + 2P(2z)]}](https://s0.wp.com/latex.php?latex=%7Bz%5BP_2%28z%2F2%29%2F2+%2B+2P%282z%29%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
from switching . Whether this is less than or greater than 
.
directly. To optimize our probability of winning, we observe 
. If there is additional algebraic structure and expectations can be defined, then an analogous calculations give whatever switching criterion maximizes the relevant expectation value.
![\displaystyle \begin{array}{rcl} P'(win)= \int dz \frac{[\theta(I_1(z)-I_2(z)) I_1(z) + \theta(I_2(z)-I_1(z))I_2(z)]}{I_1(z)+I_2(z)} \\ = \int dz \frac{\max(I_1(z),I_2(z))}{(I_1(z)+I_2(z)} \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Brcl%7D++P%27%28win%29%3D+%5Cint+dz+%5Cfrac%7B%5B%5Ctheta%28I_1%28z%29-I_2%28z%29%29+I_1%28z%29+%2B+%5Ctheta%28I_2%28z%29-I_1%28z%29%29I_2%28z%29%5D%7D%7BI_1%28z%29%2BI_2%28z%29%7D+%5C%5C+%3D+%5Cint+dz+%5Cfrac%7B%5Cmax%28I_1%28z%29%2CI_2%28z%29%29%7D%7B%28I_1%28z%29%2BI_2%28z%29%7D+%5Cend%7Barray%7D+&bg=fefeeb&fg=000000&s=0&c=20201002)
and 
are monotonic (one increasing, the other decreasing), we have a cutoff value 
(defined by 
) below which we should switch and above which we should not.
into our current notation, but it’s easier to compute directly. For given 
. Based on our algorithm, we will do so with probability 
. The probability of not needing to switch is 
and we do so with probability 
. I.e., our probability of success for given 
where 
and 
. The optimal solutions lie at one end or the other. So it obviously is best to have 
when 
and 
when 
. This would be discontinuous, but we could come up with a smoothed step function (ex. a logistic function) which is differentiable but arbitrarily sharp. The gist is that we want all the probability in 
. Integrating over 
. I.e., We end up with 
as our probability of success. If we had used 
for our 
instead. Neither is optimal in general.
![{p(z)=\frac{1}{2}[I_1(z)+I_2(z)]}](https://s0.wp.com/latex.php?latex=%7Bp%28z%29%3D%5Cfrac%7B1%7D%7B2%7D%5BI_1%28z%29%2BI_2%28z%29%5D%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
. Given that 
given by 
) is
![\displaystyle H(z'>z|z)= \frac{-I_1(z)\ln I(z) - I_2(z)\ln I_2(z) + (I_1(z)+I_2(z))\ln [I_1(z)+I_2(z)]}{I_1(z)+I_2(z)}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+H%28z%27%3Ez%7Cz%29%3D+%5Cfrac%7B-I_1%28z%29%5Cln+I%28z%29+-+I_2%28z%29%5Cln+I_2%28z%29+%2B+%28I_1%28z%29%2BI_2%28z%29%29%5Cln+%5BI_1%28z%29%2BI_2%28z%29%5D%7D%7BI_1%28z%29%2BI_2%28z%29%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
. This yields a conditional entropy:
the probability based on the true distribution and keep 
and ![\displaystyle D(Q || P, z)= \frac{-I_2(z)\ln [(I_1(z)+I_2(z))(1-F(z))/I_2(z)] - I_1(z)\ln [(I_1(z)+I_2(z))F(z)/I_1(z)]}{I_1(z)+I_2(z)}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+D%28Q+%7C%7C+P%2C+z%29%3D+%5Cfrac%7B-I_2%28z%29%5Cln+%5B%28I_1%28z%29%2BI_2%28z%29%29%281-F%28z%29%29%2FI_2%28z%29%5D+-+I_1%28z%29%5Cln+%5B%28I_1%28z%29%2BI_2%28z%29%29F%28z%29%2FI_1%28z%29%5D%7D%7BI_1%28z%29%2BI_2%28z%29%7D&bg=fefeeb&fg=000000&s=0&c=20201002)
![\displaystyle \begin{array}{rcl} \langle D(Q || P) \rangle= \frac{1}{2}\int dz [-(I_1(z)+I_2(z))\ln [I_1(z)+I_2(z)] - I_2(z)\ln (1-F(z)) \\ -I_1(z)\ln F(z) + I_1(z)\ln I_1(z) + I_2(z)\ln I_2(z)] \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Brcl%7D++%5Clangle+D%28Q+%7C%7C+P%29+%5Crangle%3D+%5Cfrac%7B1%7D%7B2%7D%5Cint+dz+%5B-%28I_1%28z%29%2BI_2%28z%29%29%5Cln+%5BI_1%28z%29%2BI_2%28z%29%5D+-+I_2%28z%29%5Cln+%281-F%28z%29%29+%5C%5C+-I_1%28z%29%5Cln+F%28z%29+%2B+I_1%28z%29%5Cln+I_1%28z%29+%2B+I_2%28z%29%5Cln+I_2%28z%29%5D+%5Cend%7Barray%7D+&bg=fefeeb&fg=000000&s=0&c=20201002)
, the entropy of our actual distribution over 
, the mean Bernoulli entropy of the actual distribution. In these terms, we have:
where 
is the always-switch strategy, and 
is the probability of employing the always-keep strategy. A player would flip a biased-coin with Bernoulli probability 
and choose one of the two-strategies based on it. That has nothing to do with the measure-theory approach we’re taking here. In particular, a mixes strategy makes no use of the observed value 
.
and right cosets are written 
. Each is a set of elements in 
is not a useful inverse since 
, so neither left cosets nor right cosets multiply as desired. More generally 
does not consist of a product of an element of 
. 
to be the set of left cosets. As mentioned, it is not a group in general. There is an equivalent definition for right cosets, written 
, but it doesn’t appear often. In most cases we care about the two are the same. 
for all 
for all 
so this is the same exact condition. 
is a Normal Subgroup if it obeys the conditions which make the cosets into a group. 
(or 
). 
has (by definition) the natural structure of a group. It is called the Quotient Group. 
is an inclusion (i.e. injective), defined by 
(where the righthand 
is the quotient map (surjective), defined by 
(with the righthand viewed as a coset, i.e. an element of 
). This map is defined for any subgroup, with 
, the following hold:
is a Normal Subgroup of 
is a subgroup of 
.
is a Normal Subgroup of 
is isomorphic to the Quotient Group 
(being very loose with notation)? The answer is no, it’s more complicated.
where 
for every pair. Here are some basic properties:
means that 
is injective. 
means that 
means 
. 
. 
such that 
. Basically, we can move to 
and back from 
without losing info — which means 
such that 
. Basically, we can move to 
without losing info — which means 
, it can mean one of two things.
. I.e. it is the direct product set (but not group). 
(the integers mod 30). This has several obvious subgroups (
, 
, 
, 
, 
, 
). 
if 
for some 
and 
. Note that 
, NOT that it is the null set. I.e., 
, the trivial group.
, we define a new group 
. We’ll denote by 
the effect of the automorphism 
on 
(i.e. all pairs 
. Multiplication on 
. The inverse is 
. 
and 
. The normality of 
. The notation is deceptive because it hides our choice of 
there exists a Semidirect product 
and 
(the former being the Normal Subgroup in each case). One is a Direct Product, and the other 3 are not. 
. 
(i.e. every 
maps to the identify map on 
. 
, which is isomorphic to 
is isomorphic to 
as our function. I.e., 
. We very well could have non-isomorphic 
with Normal Subgroups 
where 
. I.e. they are the same Normal Subgroup, but with different parent groups. We then would have different 
and 
choices. Put differently, the freedom in 
. 
. 
. This is unique. 
. There may multiple of these, corresponding to different 
which are disjoint (i.e. 
requires that 
, and 
both Normal Subgroups. 
. I.e. 
, there may be no homomorphisms between them. If there are homomorphisms, there may be none which form an SES. Consider a general pair of homomorphisms 
and 
, with no assumptions. We may turn to the first isomorphism theorem for help, but that does us no good. The first isomorphism theorem says that 
and 
, and 
and 
. This places no constraints on 
, this is a group extension. Only if it right splits can we write 
, and only if it left splits can we write 
.
. But we don’t have an injective homomorphism 
, which is what would be need for it to be isomorphic to a subgroup of 
A Place of Sand 