text:
Distribution and variance in blackjack

Introduction

Analysis of casino blackjack has been a recurring passion project of mine for nearly two decades now.  I have been back at it again for the last couple of months, this time working on computing the distribution (and thus also the variance) of the outcome of a round.  This post summarizes the initial results of that effort.  For reference up front, all updated source code is available here, with pre-compiled binaries for Windows in the usual location here.

Up to this point, the focus has been on accurate and efficient calculation of exact expected value (EV) of the outcome of a round, for arbitrary shoe compositions and playing strategies, most recently including index play using a specified card counting system.  This is sufficient for evaluating playing efficiency: that is, how close to “perfect play” (in the EV-maximizing sense) can be achieved solely by varying playing strategy?

But advantage players do not just vary playing strategy, they also– and arguably more importantly– have a betting strategy, wagering more when they perceive the shoe to be favorable, wagering less or not at all when the shoe is unfavorable.  So a natural next step is to evaluate such betting strategies… but to do so requires not just expected value, but also the variance of the outcome of each round.  This post describes the software updates for computing not just the variance, but the entire probability distribution of possible outcomes of a round of blackjack.

Rules of the game

For consistency in all discussion, examples, and figures, I will assume the following setup: 6 decks dealt to 75% penetration, dealer stands on soft 17, doubling down is allowed on any two cards including after splitting pairs, no surrender… and pairs may be split only once (i.e., to a maximum of two hands).  Note that this is almost exactly the same setup as the earlier analysis of card counting playing efficiency, with the exception of not re-splitting pairs: although we can efficiently compute exact expected values even when re-splitting pairs is allowed, computing the distribution in that case appears to be much harder.

Specifying (vs. optimizing) strategy

The distribution of outcomes of a round depends on not only the rule variations as described above, but also the playing strategy.  This is specified using the same interface as the original interface for computing expected value, which looks like this:

virtual int BJStrategy::getOption(const BJHand & hand, int upCard,
bool doubleDown, bool split, bool surrender);

The method parameters specify the “zero memory” information available to the player: the cards in the current hand, the dealer’s up card, and whether doubling down, splitting, or surrender is allowed in the current situation.  The return value indicates the action the player should take: whether to stand, hit, double down, split, or surrender.  For example, the following implementation realizes the simple– but poorly performing– “mimic the dealer” strategy:

virtual int getOption(const BJHand & hand, int upCard,
bool doubleDown, bool split, bool surrender) {
if (hand.getCount() < 17) {
return BJ_HIT;
} else {
return BJ_STAND;
}
}

When computing EV, instead of returning an explicit action, we can also return the code BJ_MAX_VALUE, meaning, “Take whatever action maximizes EV in this situation.”  For example, the default base class implementation of BJStrategy::getOption() always returns BJ_MAX_VALUE, meaning, “Compute optimal composition-dependent zero memory (CDZ-) strategy, maximizing overall EV for the current shoe.”

However, handling this special return value requires evaluating all possible subsequent hands that may result (i.e., from hitting, doubling down, splitting, etc.).  When only computing EV, we can do this efficiently, but for computing the distribution, an explicit specification of playing strategy is required.

The figure below shows a comparison of the resulting distribution of outcomes for these two example strategies.

Probability distribution of player outcomes of a unit wager on a single round from a full shoe, using “mimic the dealer” strategy (red) vs. optimal strategy (blue).

It is perhaps not obvious from this figure just how much worse “mimic the dealer” performs, yielding a house edge of 5.68% of initial wager; compare this with the house edge of just 0.457% for optimal CDZ- strategy.

Algorithm details

Blackjack is hard (i.e., interesting) because of splitting pairs.  It is manageably hard in the case of expected value, because expected value is linear: that is, if $X_1$ and $X_2$ are random variables indicating the outcome of the two “halves” of a split pair, then the expected value of the overall outcome, $E[X_1+X_2]$, is simply the sum of the individual expected values, $E[X_1]+E[X_2]$.  Better yet, when both halves of the split are resolved using the same playing strategy, those individual expected values are equal, so that we need only compute $2E[X_1]$.  (When pairs may be split and re-split, things get slightly more complicated, but the idea still applies.)

Variance, on the other hand, is not linear– at least when the summands are correlated, which they certainly are in the case of blackjack split hands.  So my first thought was to simply try brute force, recursively visiting all possible resolutions of a round.  Weighting each resulting outcome by its probability of occurrence, we can compute not just the variance, but the entire distribution of the outcome of the round.

This was unacceptably slow, taking about 5 minutes on my laptop to compute the distribution for CDZ- strategy from a full 6-deck shoe.  (Compare this with less than a tenth of a second to compute the CDZ- strategy itself and the corresponding overall EV.)  It was also not terribly accurate: the “direct” computation of overall EV provides a handy source of ground truth against which we can compare the “derived” overall EV using the distribution.  Because computing that distribution involved adding up over half a billion individual possible outcomes of a round, numerical error resulted in loss of nearly half of the digits of double precision.  A simple implementation of Kahan’s summation algorithm cleaned things up.

Two modifications to this initial approach resulted in a roughly 200-fold speedup, so that the current implementation now takes about 2.5 seconds to compute the distribution for the same full 6-deck optimal strategy.  First, the Steiner tree problem of efficiently calculating the probabilities of outcomes of the dealer’s hand can be split up into 10 individual trees, one for each possible up card.  This was an interesting trade-off: when you know you need all possible up cards for all possible player hands– as in the case of computing overall EV– there are savings to be gained by doing the computation for all 10 up cards at once.  But when computing the distribution, some player hands are only ever reached with some dealer up cards, so there is benefit in only doing the computation for those that you need… even if doing them separately actually makes some of that computation redundant.

Second, and most importantly, we don’t have to recursively evaluate every possible resolution of pair split hands.  The key observation is that (1) both halves of the split have the same set of possible hands– viewed as unordered subsets of cards– that may result; and (2) each possible selection of pairs of such resolved split hands may occur many times, but each with the same probability.  So we need only recursively traverse one half of any particular split hand, recording the number of times we visit each resolved hand subset.  Then we traverse the outer product of pairs of such hands, computing the overall outcome and “individual” probability of occurrence, multiplied by the number of orderings of cards that yield that pair of hands.

3:2 Blackjack isn’t always optimal

Finally, I found an interesting, uh, “feature,” in my original implementation of CDZ- strategy calculation.  In early testing of the distribution calculation, I noticed that the original direct computation of overall EV didn’t always agree with the EV derived from the computed distribution.  The problem turned out to be the “special” nature of a player blackjack, that is, drawing an initial hand of ten-ace, which pays 3:2 (when the dealer does not also have blackjack).

There are extreme cases where “standing” on blackjack is not actually optimal: for example, consider a depleted shoe with just a single ace and a bunch of tens.  If you are dealt blackjack, then you can do better than an EV of 1.5 from the blackjack payoff, by instead doubling down, guaranteeing a payoff of 2.0.  Although interesting, so far no big deal; the previous and current implementations both handle this situation correctly.

But now suppose that you are initially dealt a pair of tens, and optimal strategy is to split the pair, and you subsequently draw an ace to one of those split hands.  This hand does not pay 3:2 like a “normal” blackjack… but deciding what “zero memory” action to take may depend on when we correct the expected value of standing on ten-ace to its pre-split 3:2 payoff: in the previous implementation, this was done after the post-split EVs were computed, meaning that the effective strategy might be to double down on ten-ace after a split, but stand with the special 3:2 payoff on an “actual” blackjack.

Since this violates the zero memory constraint of CDZ-, the current updated implementation performs this correction before post-split EVs are computed, so that the ten-ace playing decision will be the same in both cases.  (Note that the strategy calculator also supports the more complex CDP1 and CDP strategies as well, the distinctions of which are for another discussion.)

What I found interesting was just how common this seemingly pathological situation is.  In a simulation of 100,000 shoes played to 75% penetration, roughly 14.5% of them involved depleted shoe compositions where optimal strategy after splitting tens and drawing an ace was to double down instead of stand.  As expected, these situations invariably occurred very close to the cut card, with depleted shoes still overly rich in tens.  (For one specific example, consider the shoe represented by the tuple (6, 6, 1, 5, 8, 2, 5, 9, 2, 34), indicating 6 aces, 6 twos, 34 tens, etc.)

Wrapping up, this post really just captures my notes on the assumptions and implementation details of the computation of the probability distribution of outcomes of a round of blackjack.  The next step is to look at some actual data, where one issue I want to focus on is a comparison of analysis approaches– combinatorial analysis (CA) and Monte Carlo simulation– their relative merits, and in particular, the benefits of combining the two approaches where appropriate.

Serializing MATLAB data

Consider the following problem: given a value in the MATLAB programming language, can we serialize it into a sequence of bytes– suitable for, say, storage on disk– in a form that allows easy recovery of the exact original value?

Although I will eventually try to provide an actual solution, the primary motivation for this post is simply to point out some quirks and warts of the MATLAB language that make this problem surprisingly difficult to solve.

“Binary” serialization

Our problem requires a bit of clarification, since there are at least a couple of different reasonable use cases.  First, if we can work with a stream of arbitrary opaque bytes– for example, if we want to send and receive MATLAB data on a TCP socket connection– then there is actually a very simple and robust built-in solution… as long as we’re comfortable with undocumented functionality.  The function b=getByteStreamFromArray(v) converts a value to a uint8 array of bytes, and v=getArrayFromByteStream(b) converts back.  This works on pretty much all types of data I can think of to test, even Java- and user-defined class instances.

Text serialization

But what if we would like something human-readable (and thus potentially human-editable)?  That is, we would like a function similar to Python’s repr, that converts a value to a char string representation, so that eval(repr(v)) “equals” v.  (I say “‘equals'” because even testing such a function is hard to do in MATLAB.  I suppose the built-in function isequaln is the closest approximation to what we’re looking for, but it ignores type information, so that isequaln(int8(5), single(5)), for example.)

Without further ado, following is my attempt at such an implementation, to use as you wish:

function s = repr(v)
%REPR Return string representation of value such that eval(repr(v)) == v.
%
%   Class instances, NaN payloads, and function handle closures are not
%   supported.

if isstruct(v)
s = sprintf('cell2struct(%s, %s)', ...
repr(struct2cell(v)), repr(fieldnames(v)));
elseif isempty(v)
sz = size(v);
if isequal(sz, [0, 0])
if isa(v, 'double')
s = '[]';
elseif ischar(v)
s = '''''';
elseif iscell(v)
s = '{}';
else
s = sprintf('%s([])', class(v));
end
elseif isa(v, 'double')
s = sprintf('zeros(%s)', mat2str(sz, 17));
elseif iscell(v)
s = sprintf('cell(%s)', mat2str(sz, 17));
else
s = sprintf('%s(zeros(%s))', class(v), mat2str(sz, 17));
end
elseif ~ismatrix(v)
nd = ndims(v);
s = sprintf('cat(%d, %s)', nd, strjoin(cellfun(@repr, ...
squeeze(num2cell(v, 1:(nd - 1))).', ...
'UniformOutput', false), ', '));
elseif isnumeric(v)
if ~isreal(v)
s = sprintf('complex(%s, %s)', repr(real(v)), repr(imag(v)));
elseif isa(v, 'double')
s = strrep(repr_matrix(@arrayfun, ...
@(x) regexprep(char(java.lang.Double.toString(x)), ...
'\.0$', ''), v, '[%s]', '%s'), 'inity', ''); elseif isfloat(v) s = strrep(repr_matrix(@arrayfun, ... @(x) regexprep(char(java.lang.Float.toString(x)), ... '\.0$', ''), v, '[%s]', 'single(%s)'), 'inity', '');
elseif isa(v, 'uint64') || isa(v, 'int64')
t = class(v);
s = repr_matrix(@arrayfun, ...
@(x) sprintf('%s(%s)', t, int2str(x)), v, '[%s]', '%s');
else
s = mat2str(v, 'class');
end
elseif islogical(v) || ischar(v)
s = mat2str(v);
elseif iscell(v)
s = repr_matrix(@cellfun, @repr, v, '%s', '{%s}');
elseif isa(v, 'function_handle')
s = sprintf('str2func(''%s'')', func2str(v));
else
error('Unsupported type.');
end
end

function s = repr_matrix(map, repr_scalar, v, format_matrix, format_class)
s = strjoin(cellfun(@(row) strjoin(row, ', '), ...
num2cell(map(repr_scalar, v, 'UniformOutput', false), 2).', ...
'UniformOutput', false), '; ');
if ~isscalar(v)
s = sprintf(format_matrix, s);
end
s = sprintf(format_class, s);
end

That felt like a lot of work… and that’s only supporting the “plain old data” types: struct and cell arrays, function handles, logical and character arrays, and the various floating-point and integer numeric types.  As the help indicates, Java and classdef instances are not supported.  A couple of other cases are only imperfectly handled as well, as we’ll see shortly.

Struct arrays

The code starts with struct arrays.  The tricky issue here is that struct arrays can not only be “empty” in the usual sense of having zero elements, but also– independently of whether they are empty– they can have no fields.  It turns out that the struct constructor, which would work fine for “normal” structures with one or more fields, has limited expressive power when it comes to field-less struct arrays: unless the size is 1×1 or 0x0, some additional concatenation or reshaping is required.  Fortunately, cell2struct handles all of these cases directly.

Multi-dimensional arrays

Next, after handling the tedious cases of empty arrays of various types, the ~ismatrix(v) test handles multi-dimensional arrays– that is, arrays with more than 2 dimensions.  I could have handled this with reshape instead, but I think this recursive concatenation approach does a better job of preserving the “visual shape” of the data.

In the process of testing this, I learned something interesting about multi-dimensional arrays: they can’t have trailing singleton dimensions!  That is, there are 1×1 arrays, and 2×1 arrays, even 1x2x3 and 2x1x3 arrays… but no matter how hard I try, I cannot construct an mxnx1 array, or an mxnxkx1 array, etc.  MATLAB seems to always “squeeze” trailing singleton dimensions automagically.

Numbers

The isnumeric(v) section is what makes this problem almost comically complicated.  There are 10 different numeric types in MATLAB: double and single precision floating point, and signed and unsigned 8-, 16-, 32-, and 64-bit integers.  Serializing arrays of these types should be the job of the built-in function mat2str, which we do lean on here, but only for the shorter integer types, since it fails in several ways for the other numeric types.

First, the nit-picky stuff: I should emphasize that my goal is “round-trip” reproducibility; that is, after converting to string and back, we want the underlying bytes representing the numeric values to be unchanged.  Precision is one issue: for some reason, MATLAB’s default seems to be 15 decimal digits, which isn’t enough– by two— to accurately reproduce all double precision values.  Granted, this is an optional argument to mat2str, which effectively uses sprintf('%.17g',x) under its hood, but Java’s algorithm does a better job of limiting the number of digits that are actually needed for any given value.

Other reasons to bypass mat2str are that (1) for some reason it explicitly “erases” negative zero, and (2) it still doesn’t quite accurately handle complex numbers involving NaN, although it has improved in recent releases.  Witness eval(mat2str(complex(0, nan))), for example.  (My implementation isn’t perfect here, either, though; there are multiple representations of NaN, but this function strips any payload.)

But MATLAB’s behavior with 64-bit integer types is the most interesting of all, I think.  Imagine things from the parser’s perspective: any numeric literal defaults to double precision, which, without a decimal point or fractional part, we can think of as “almost” an int54.  There is no separate syntax for integer literals; construction of “literal” values of the shorter (8-, 16-, and 32-bit) integer types effectively casts from that double-precision literal to the corresponding integer type.

But for uint64 and int64, this doesn’t work… and for a while (until around R2010a), it really didn’t work– there was no way to directly construct a 64-bit integer larger than 2^53, if it wasn’t a power of two!

This behavior has been improved somewhat since then, but at the expense of added complexity in the parser: the expression [u]int64(expr) is now a special case, as long as expr is an integer literal, with no arithmetic, imaginary part, etc.  Even so much as a unary plus will cause a fall back to the usual cast-from-double.  (It appears that Octave, at least as of version 4.0.3, has not yet worked this out.)

The effect on this serialization function is that we have to wrap that explicit uint64 or int64 construction around each individual integer scalar, instead of a single cast of the entire array expression as we can do with all of the other numeric types.

Function handles

Finally, function handles are also special.  First, they must be scalar (i.e., 1×1), most likely due to the language syntax ambiguity between array indexing and function application.  But function handles also can have workspace variables associated with them– usually when created anonymously– and although an existing function handle and its associated workspace can be inspected, there does not appear to be a way to create one from scratch in a single evaluatable expression.

Posted in Uncategorized | 6 Comments

IBM Research Ponder This: August 2016 Puzzle

This month’s IBM Research puzzle is pretty interesting: it sets the stage by describing a seemingly much simpler problem, then asking for a solution to a more complicated variant.  But even that simpler problem is worth a closer look.

I won’t spoil the “real” problem here– actually, I won’t approach that problem at all.  Instead, let’s start at the very beginning:

Problem 1: You have 10 bags, each with 1000 gold coins.  Each coin should weigh exactly 10 grams, but one of the bags contains all counterfeit coins, weighing only 9 grams each.  You have a scale on which you can accurately measure the weight of any number of coins.  With just one weighing, how can you determine which bag contains the counterfeit coins?

This is a standard, job-interview-ish, “warm-up” version of the problem, with the following solution: arbitrarily number the bags 1 through 10, and take $k$ coins from bag $k$, for a total of 55 coins.  If all of the coins were genuine, the total weight would be 550 grams; the measured deficit from this weight indicates the number of the counterfeit bag.

So far, so good.  The IBM Research version of the problem extends this in two ways (and eventually a third): first, what happens if more than one bag– or possibly none of the bags– might be counterfeit?  And second, what if there is a limited number $n$ of coins available in each bag (where, for example, $n=1000$ above)?  From the IBM Research page:

If $n \geq 1024$ then one can identify the [subset of] counterfeit bags using a single measurement with an accurate weighing scale.  (How?)

That is, instead of knowing that exactly one bag is counterfeit, any of the $2^{10}=1024$ possible subsets of bags may be counterfeit, and our objective is to determine which subset, with just a single weighing of coins carefully chosen from each bag.

The motivation for this post is that, although the statement above seems to telegraph the intended elegant solution to this “warm-up” version of the problem, (a) that intended solution can actually be implemented by requiring only $n=512$ coins in each bag, not 1024; and (b) even this stronger bound is not tight– that is, even before approaching the “real” problem asked in this month’s IBM Research puzzle, the following simpler variant is equally interesting:

Problem 2: What is the minimum value of $n$ (i.e., the minimum number of coins in each bag), for which a single weighing is sufficient to determine the subset of bags containing counterfeit coins?

Hint: I ended up tackling this by writing code to solve smaller versions of the problem, then leaning on the OEIS to gain insight into the general solution.

[Edit: The puzzle statement on the IBM Research page has since been updated to reflect that the “nice”– but still not tight– bound is 512, not 1024.]

Posted in Uncategorized | 4 Comments

Twisty lattice paths, all alike

I haven’t posted a puzzle in quite a while, so…

Every morning, I drive from my home at 1st and A to my work at 9th and J (8 blocks east and 9 blocks north), always heading either east or north so as not to backtrack… but I choose a random route each time, with all routes being equally likely.  How many turns should I expect to make?

And a follow-up: on busy city streets, left turns are typically much more time-consuming than right turns.  On average, how many left turns should I expect to make?

The first problem is presented in Zucker’s paper referenced below, and solved using induction on a couple of recurrence relations.  But it seems to me there is a much simpler solution, that more directly addresses the follow-up as well.

Reference:

• Zucker, M., Lattice Paths and Harmonic Means, The College Mathematics Journal, 47(2) March 2016, p. 121-124 [JSTOR]

Posted in Uncategorized | 2 Comments

Rainbows

Recently my wife and I saw a double rainbow, shown below.  I’m a lousy photographer, but it’s there if you look closely, along the top of the picture:

There are plenty of existing sources that describe the mathematics of rainbows: briefly, rays of sunlight (entering the figure below from the right) strike airborne droplets of water, bending due to refraction, reflecting off the inside of the droplet, and finally exiting “back” toward an observer.

The motivation for this post is to describe the calculations involved in predicting where rainbows can be seen, but focusing on generalization: with just one equation, so to speak, we can let the sunlight bounce around a while inside the water droplet, and predict all of the different “higher-order” rainbows (double, tertiary, etc.) at once.  I think this is a nice “real” problem for students of differential calculus; its solution involves little more than the chain rule and some trigonometry.

The figure above shows the basic setup, where angle $\alpha \in (0, \pi/2)$ parameterizes the location where a ray of sunlight, entering horizontally from the right, strikes the surface of the spherical droplet.  The angle $\beta$ is the corresponding normal angle of refraction, related by Snell’s law:

$n = \frac{n_{water}}{n_{air}} = \frac{\sin \alpha}{\sin \beta}$

where $n_{air}=1.00029$ and $n_{water}=1.333$ are the indices of refraction for air and water, respectively.  (Let’s defer for the moment the problem that these indices actually vary slightly with wavelength.)

As a function of $\alpha$, at what angle does the light ray exit the picture?  Starting with the angle $\alpha$ shown in the center of the droplet, and “reflecting around” the center counterclockwise– and including the final additional refraction upon exiting the droplet– the desired angle $\theta$ is

$\theta(\alpha) = \alpha + (k+1)(\pi - 2\beta) + \alpha$

where– and this is the generalization– the integer $k$ indicates how many times we want the ray to reflect inside the droplet ($k=1$ in the figure above).  The figure below shows how this exit angle $\theta$ varies with $\alpha$, for various numbers of internal reflections.

The key observation is that for $k>0$, there is a critical minimum exit angle, in the neighborhood of which there is a concentration of light rays.  We can find this critical angle by minimizing $\theta$ as a function of $\alpha$.  (Note that there is no critical angle when $k=0$, and so a rainbow requires at least one reflection inside the droplets.)

At this point, we have a fairly straightforward, if somewhat tedious, calculus problem: find $\theta$ where $\theta'(\alpha)=0$.  It’s an exercise for the reader to show that this occurs at:

$\alpha = \cos^{-1}\sqrt{\frac{n^2-1}{k(k+2)}}$

$\theta = 2\alpha + (k+1)(\pi - 2\beta)$

Evaluating at $k=1$ yields an angle $\theta$ of about 318 degrees.  This requires some interpretation: imagine a line between you and the Sun.  Then standing with the Sun behind you, a primary rainbow is visible along a cone making an angle of about 360-318=42 degrees with this line.

(Coming back now to the dependence of index of refraction on wavelength: although the variation is negligible for air, the index of refraction for water varies from about 1.33 for red light to about 1.34 for violet light, so that the rainbow is not just a band of brighter light, but a spread of colors from about 41.1 to 42.5 degrees… with the red light on the outside of the band.)

For $k=2$, the critical $\theta$ is about 411 degrees, corresponding to a viewing angle of about 51 degrees… with two differences: first, the additional internal reflection means that the light strikes the bottom half of each droplet, making a complete “loop” around the inside of the droplet before exiting toward the observer.  Second, this opposite direction of reflection means that the bands of colors are reversed, with red on the inside of the band.

Finally, the angle for $k=3$ is about 498 degrees: such a tertiary rainbow may be seen facing the Sun (good luck with that), in a sort of “corona” around it at an angle of about 42 degrees.

Category theory without categories

(Following is an attempt to capture some of my thoughts following an interesting student discussion.  I think I mostly failed during that discussion, but it was fun.)

How do we know when two sets $X$ and $Y$ have the same “size”?  The layman answer is, “When they both have the same number of elements,” or even better, “When we can ‘pair up’ elements from $X$ and $Y$, with each element a part of exactly one pair.”

The mathematician formalizes this idea as a bijection, that is, a function $f:X \rightarrow Y$ that is both:

• Injective, or “one-to-one”: if $f(x_1)=f(x_2)$, then $x_1 = x_2$.  Intuitively, distinct elements of $X$ map to distinct elements of $Y$.
• Surjective, or “onto”: for every element $y \in Y$, there exists some $x \in X$ such that $f(x)=y$.  Intuitively, we “cover” all of $Y$.

Bijections are handy tools in combinatorics, since they provide a way to count elements in $Y$, which might be difficult to do directly, by instead counting elements in $X$, which might be easier.

So far, so good.  Now suppose that a student asks why injectivity and surjectivity are the critical properties of functions that “pair up” elements of two sets?

This question struck a chord with me, because I remember struggling with it myself while learning introductory algebra.  The ideas behind these two properties seemed vaguely “dual” to me, but the structure of the actual definitions looked very different.  (I remember thinking that, if anything, the properties that most closely “paired” with one another were injective and well-defined (i.e., if $x_1 = x_2$, then $f(x_1)=f(x_2)$; compare this with the above definition of an injection).  Granted, well-definedness might seem obvious most of the time, but sometimes an object can have many names.)

One way to answer such a question is to provide alternative definitions for these properties, that are equivalent to the originals, but where that elegance of duality is more explicit:

• A function $f:X \rightarrow Y$ is injective if and only if, for all functions $g,h:W \rightarrow X$, $f \circ g = f \circ h$ implies $g=h$.
• A function $f:X \rightarrow Y$ is surjective if and only if, for all functions $g,h:Y \rightarrow Z$, $g \circ f = h \circ f$ implies $g=h$.

It’s a great exercise to show that these new definitions are indeed equivalent to the earlier ones.  But if that’s the case, and if these are more pleasing to look at, then why don’t we always use/teach them instead?

I think there are at least two practical explanations for this.  First, these definitions are inconvenient.  That is, to use them to show that $f:X \rightarrow Y$ is a bijection, we end up having to drag a third (and fourth) arbitrary hypothetical set $W$ (and $Z$) into the mix, with corresponding arbitrary hypothetical functions to compose with $f$.  With the usual definitions, we can focus all of our attention solely on the two sets under consideration.

Second, these new definitions can be dangerous.  Often the function $f$ we are trying to show is a bijection preserves some useful structural relationship between the sets $X$ and $Y$ (e.g., $f$ may be a homomorphism)… but to use the new definitions, we must consider all possible additional functions $g,h$, not just that restricted class of functions that behaves similarly to $f$.  We have strayed into category theory, where monomorphisms and epimorphisms generalize the notions of injections and surjections, respectively.  I say “generalize,” because although for sets, these definitions are equivalent, in other categories (rings, for example), things get more complicated, where a monomorphism may not be injective, or (more frequently) an epimorphism may not be surjective.

Posted in Uncategorized | 2 Comments

Sump pump monitoring with a Raspberry Pi

I am not much of a mathematician, and even less of a programmer.  But I am at my most dangerous when wielding a screwdriver, attempting to be “handy.”  So this project was a lot of fun.

My house is situated on a hill, and the sump pump in my basement acts up seasonally, rain or shine, making me suspect a possible underground spring or stream.  To test this theory, my goal was to monitor the behavior of the sump pump, measure the rate at which water is ejected from the pit, and as a safety feature, to automatically send myself text messages in the event of any of several possible failure conditions (e.g., pump or float switch failure, excessive depth of water in the pit, etc.).

The setup is shown in the diagram below.  I was able to use mostly existing equipment from past educational projects, with the exception of some wiring, a length of PVC pipe, and an eTape liquid level sensor that I wanted to try out.  The sensor is a length of tape submerged in the sump pit (inside a PVC pipe to keep it vertical); it acts as a variable resistor, with the resistance decreasing linearly as the water rises in the pit.  Using a voltage divider circuit, the resistance is (indirectly) measured as a voltage drop across the tape, using a DI-145 analog-to-digital converter.  The A/D has a simple USB-serial output interface with a Raspberry Pi, where a few Python scripts handle the data recording, filtering, and messaging.

Raspberry Pi 3 monitoring DI-145 A/D converted voltage across eTape liquid level sensor.

The figure below shows a sample of one hour’s worth of recorded data.  The y-axis is the voltage drop across the tape, where lower voltage indicates higher water depth.  Note that the resistance is linear in the water depth, but the voltage is not.

One hour of recorded voltage: raw 120 Hz input (green), filtered (red), with detected pump cycles (blue).

The green curve is the raw voltage; I’m not sure whether the noisy behavior is due to the tape sensor or the A/D.  Fortunately the DI-145 samples at 120 Hz (despite all documentation suggesting 240 Hz), so that a simple low-gain filter, shown in red, cleans things up enough to allow equally simple edge detections of the pump turning on, shown in blue.  (And this is after nearly two weeks of no rain.)  Based on those edge detections, the program sends me text messages with periodic updates, or alerts if the water depth gets too high, or the pump starts cycling too frequently, or abruptly stops cycling.

All of the Python code is available at the usual location here.


text:
Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks

Abstract : Given a digraph G, a lot of attention has been deserven on the maximum number φ(G) of fixed points in a Boolean network f : {0, 1} n → {0, 1} n with G as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the feedback bound φ(G) ≤ 2 τ , where τ is the minimum size of a feedback vertex set of G. In this paper, we study the maximum number φ m (G) of fixed points in a monotone Boolean network with interaction graph G. We establish new upper and lower bounds on φ m (G) that depends on the cycle structure of G. In addition to τ , the involved parameters are the maximum number ν of vertex-disjoint cycles, and the maximum number ν * of vertex-disjoint cycles verifying some additional technical conditions. We improve the feedback bound 2 τ by proving that φ m (G) is at most the largest sub-lattice of {0, 1} τ without chain of size ν + 2, and without another forbidden pattern described by two disjoint antichains of size ν * + 1. Then, we prove two optimal lower bounds: φ m (G) ≥ ν + 1 and φ m (G) ≥ 2 ν *. As a consequence, we get the following characterization: φ m (G) = 2 τ if and only if ν * = τ. As another consequence, we get that if c is the maximum length of a chordless cycle of G then 2 ν/3 c ≤ φ m (G) ≤ 2 cν. Finally, with the techniques introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (3), pp.1702 - 1725. 〈10.1137/16M1060868〉
Domaine :

Littérature citée [31 références]

https://hal.archives-ouvertes.fr/hal-01630477
Soumis le : mardi 7 novembre 2017 - 16:23:13
Dernière modification le : mercredi 31 janvier 2018 - 10:24:05
Document(s) archivé(s) le : jeudi 8 février 2018 - 13:52:36

Fichier

2017_04_12_maxFP_Monotonous_R1...
Fichiers produits par l'(les) auteur(s)

Citation

Julio Aracena, Adrien Richard, Lilian Salinas. Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (3), pp.1702 - 1725. 〈10.1137/16M1060868〉. 〈hal-01630477〉

Métriques

Consultations de la notice

34

Téléchargements de fichiers

format: plain


text:
# Diagonals of a Parallelogram are Equal & Intersect at Right Angles

Here we will prove that if in a parallelogram the diagonals are equal in length and intersect at right angles, the parallelogram will be a square.

Given: PQRS is a parallelogram in which PQ ∥ SR, PS ∥ QR and diagonal PR ⊥diagonal QS.

To prove: PQRS is a square, i.e., PQ = QR = RS = SP and an angle, say ∠SPQ = 90°.

Proof:

In ∆PQR and ∆RSP,

∠QPR = ∠PRS (Since, PQ ∥ SR and QR is a transversal)

∠QRP = ∠SPR (Since, QR ∥ PS and PR is a transversal)

PR = PR (Common Side).

Therefore, ∆PQR ≅ ∆RSP (By AAS criterion of congruency).

Therefore, PQ = SR (CPCTC).

Similarly, ∆PQS ≅ ∆RSQ (By AAS criterion of congruency).

Therefore, PS = QR (CPCTC).

∆OPQ ≅ ∆ORS (By AAS criterion of congruency).

Therefore, OP = OR (CPCTC).

Similarly, ∆POQ ≅ ∆ROQ (By SAS criterion of congruency).

Therefore, PQ = QR (CPCTC).

Therefore, PQ = QR = RS = SP. (Proved)

∆SPQ ≅ ∆RQP (By SSS criterion of congruency).

Therefore, ∠SPQ = ∠RQP (CPCTC).

But ∠SPQ + ∠RQP = 180° (Since, PS ∥ QR).

Therefore, ∠SPQ = ∠RQP = $$\frac{180°}{2}$$ = 90°. (Proved).

From Diagonals of a Parallelogram are Equal & Intersect at Right Angles to HOME PAGE


text:
Given hourly NOX and NO2 from a roadside site and hourly NOX, NO2 and O3 from a background site the function will estimate the emissions ratio of NO2/NOX --- the level of primary NO2

calcFno2(input, tau = 60, user.fno2, main = "", xlab = "year", ...)

## Arguments

input A data frame with the following fields. nox andno2 (roadside NOX and NO2 concentrations), back_nox, back_no2 and back_o3 (hourly background concentrations of each pollutant). In addition temp (temperature in degrees Celsius) and cl (cloud cover in Oktas). Note that if temp and cl are not available, typical means values of 11 deg. C and cloud = 3.5 will be used. Mixing time scale. It is unlikely the user will need to adjust this. See details below. User-supplied f-NO2 fraction e.g. 0.1 is a NO2/NOX ratio of 10 series and is useful for testing "what if" questions. Title of plot if required. x-axis label. Other graphical parameters send to scatterPlot.

## Value

As well as generating the plot itself, calcFno2 also returns an object of class openair''. The object includes three main components: call, the command used to generate the plot; data, the data frame of summarised information used to make the plot; and plot, the plot itself. If retained, e.g. using output <- calcFno2(...), this output can be used to recover the data, reproduce or rework the original plot or undertake further analysis.

An openair output can be manipulated using a number of generic operations, including print, plot and summary.

## Details

The principal purpose of this function is to estimate the level of primary (or direct) NO2 from road vehicles. When hourly data of NOX, NO2 and O3 are available, the total oxidant method of Clapp and Jenkin (2001) can be used. If roadside O3 measurements are available see linearRelation for details of how to estimate the primary NO2 fraction.

In the absence of roadside O3 measurements, it is rather more problematic to calculate the fraction of primary NO2. Carslaw and Beevers (2005c) developed an approach based on linearRelation the analysis of roadside and background measurements. The increment in roadside NO2 concentrations is primarily determined by direct emissions of NO2 and the availability of One to react with NO to form NO2. The method aims to quantify the amount of NO2 formed through these two processes by seeking the optimum level of primary NO2 that gives the least error.

Test data is provided at http://www.openair-project.org.

## References

Clapp, L.J., Jenkin, M.E., 2001. Analysis of the relationship between ambient levels of O3, NO2 and NO as a function of NOX in the UK. Atmospheric Environment 35 (36), 6391-6405.

Carslaw, D.C. and N Carslaw (2007). Detecting and characterising small changes in urban nitrogen dioxide concentrations. Atmospheric Environment. Vol. 41, 4723-4733.

Carslaw, D.C., Beevers, S.D. and M.C. Bell (2007). Risks of exceeding the hourly EU limit value for nitrogen dioxide resulting from increased road transport emissions of primary nitrogen dioxide. Atmospheric Environment 41 2073-2082.

Carslaw, D.C. (2005a). Evidence of an increasing NO2/NOX emissions ratio from road traffic emissions. Atmospheric Environment, 39(26) 4793-4802.

Carslaw, D.C. and Beevers, S.D. (2005b). Development of an urban inventory for road transport emissions of NO2 and comparison with estimates derived from ambient measurements. Atmospheric Environment, (39): 2049-2059.

Carslaw, D.C. and Beevers, S.D. (2005c). Estimations of road vehicle primary NO2 exhaust emission fractions using monitoring data in London. Atmospheric Environment, 39(1): 167-177.

Carslaw, D. C. and S. D. Beevers (2004). Investigating the Potential Importance of Primary NO2 Emissions in a Street Canyon. Atmospheric Environment 38(22): 3585-3594.

Carslaw, D. C. and S. D. Beevers (2004). New Directions: Should road vehicle emissions legislation consider primary NO2? Atmospheric Environment 38(8): 1233-1234.

linearRelation if you have roadside ozone measurements.


text:
Languages and Scripting
Showing results for
Do you mean

SOLVED

# can not parser ~\$user

user=`whoami`
in my script, I have the following lines

for i in `ls ~\$user/.*table`
do
echo "Modifying \$i now....."
echo
done

when I run it, it always put the ' ' around \$user and gave the following errors

++ ls '~anderson/.*table'
ls: ~anderson/.*table: No such file or directory

If I do ls ~anderson/.*table, it gave desired output.

how do I get around the problem :-(

thak you

but, if I run manually like "ls ~yanga
>
1 ACCEPTED SOLUTIONS
Highlighted
Honored Contributor

# Re: can not parser ~\$user

Since the only workaround to your problem seems to be injecting the "eval" command in the for loop line, it looks like the shell isn't doing variable expansion before running the command. You can force it do so using eval...

for i in `eval ls ~\$user/.*table`
do
echo "Modifying \$i now....."
echo
done

hope it helps!
7 REPLIES
Honored Contributor

# Re: can not parser ~\$user

First problem is that you are apparently using the Korn shell. This doesn't happen in the POSIX shell, /usr/bin/sh, which is the standard HP-UX shell. :)
--
Jeff Traigle
Honored Contributor

# Re: can not parser ~\$user

Jeff is right. It works in the POSIX shell but not the Korn shell. The man pages for both shells seem to have the same description for tilde substitution, so my guess is that you've found a bug in HP-UX's version of the Korn shell.

JP
Acclaimed Contributor

# Re: can not parser ~\$user

PHCO_33169 corrects some tidle related bugs in ksh for 11.11; since you didn't bother to identify your OS version, this may or may not be applicable. In any event, the use of ksh on HP-UX is somewhat discouraged as sh (the POSIX shell) is the default and I suspect gets much more rigorous testing than does ksh.
If it ain't broke, I can fix that.
Highlighted
Honored Contributor

# Re: can not parser ~\$user

Since the only workaround to your problem seems to be injecting the "eval" command in the for loop line, it looks like the shell isn't doing variable expansion before running the command. You can force it do so using eval...

for i in `eval ls ~\$user/.*table`
do
echo "Modifying \$i now....."
echo
done

hope it helps!

# Re: can not parser ~\$user

yes, "eval" did the trick!

thank you
Honored Contributor

# Re: can not parser ~\$user

Minor correction to my last post, the shell is doing variable expansion but not doing the filename metacharacter expansion. Since ~\$user is the home directory of user "anderson" on your system, hence the shell needs to be forced to re-evaluate the command line before executing it. Otherwise the command tries to list all files named ".*table" under the sub-directory "~anderson".

hope it helps!


text:
Box-Cox transformation coefficient (lambda) in SPSS or R
1
0
Entering edit mode
5.6 years ago

Hello all, I want to transform one variable, which is skewed, to a normal distribution. An appropriate transformation method should be decided based on Box-Cox transformation coefficient (lambda) value. However, I couldn't calculate in SPSS or R.

Anyone who have experience?

Box-Cox Lambda SPSS R • 9.4k views
0
Entering edit mode

Can you add more detail on your specific problem? - there's a box-cox method in the MASS package, and there's even an R-Bloggers tutorial

0
Entering edit mode

First of all, thank you very much. I have seen both links you mentioned.

I have non-normally distributed continuous outcome variable. Therefore, I need to transform to a normal distribution using an appropriate method that is selected based on Box-Cox transformation coefficient (λ) value. The decision should be made as follows: λ = 1.00: no transformation needed; produces results identical to original data λ = 0.50: square root transformation λ = 0.33: cube root transformation λ = 0.25: fourth root transformation λ = 0.00: natural log transformation λ = -0.50: reciprocal square root transformation λ = -1.00: reciprocal (inverse) transformation and so forth.

Now, I have got difficulty to calculate λ using SPSS or R.

1
Entering edit mode
5.5 years ago

One of my friends advised me to use forecast package in R.

install.packages("forecast")

library(forecast)

lambda2<- BoxCox.lambda(dataname\$variablename, method = "loglik", lower = -20, upper = 20)

Then, if lambda (λ);

λ = 1.00: no transformation needed; produces results identical to original data
λ = 0.50: square root transformation
λ = 0.33: cube root transformation
λ = 0.25: fourth root transformation
λ = 0.00: natural log transformation
λ = -0.50: reciprocal square root transformation
λ = -1.00: reciprocal (inverse) transformation and so forth.

If the lambda (λ) estimate is none of the above value, use another transformation method. At least in my experience, I can recommend the two-step transformation method in SPSS.

Reference:

1. Osborne JW. Improving your data transformations: Applying the Box-Cox transformation. Practical Assessment, Research & Evaluation. 2010 Oct;15(12):1-9.

2. Templeton GF. A two-step approach for transforming continuous variables to normal: implications and recommendations for IS research. Communications of the Association for Information Systems. 2011 Jan 1;28(4):41-58.

Box-Cox transformation coefficient (lambda) in SPSS or R - ResearchGate. Available from: https://www.researchgate.net/post/Box-Cox_transformation_coefficient_lambda_in_SPSS_or_R [accessed Mar 27, 2017].


text:
ghc-8.2.1: The GHC API

This checks whether a pass correctly looks through debug annotations (SourceNote). This works a bit different from other consistency checks: We check this by running the given task twice, noting all differences between the results.


text:
• 碳排放 •

### 中国渔业生产系统隐含碳排放结构特征及驱动因素分解

1. 1.中国海洋大学经济学院,青岛 266100
2.中国海洋大学海洋发展研究院,青岛 266100
3.青岛理工大学商学院,青岛266520
• 收稿日期:2020-09-07 修回日期:2020-11-13 出版日期:2021-06-25 发布日期:2021-08-25
• 通讯作者: 孔海峥,女,山东青岛人,博士,讲师,主要研究方向为海洋碳汇、海洋经济布局。E-mail: konghaizheng@hotmail.com
• 作者简介:李晨,女,山东青岛人,博士,教授,硕士生导师,主要研究方向为海洋资源、渔业经济与水产品贸易流通。E-mail： phdlichen@126.com
• 基金资助:
国家社会科学规划基金项目(11BJY064);山东省自然科学基金项目(ZR2016GQ05)

### Structural characteristics and driving factors of embodied carbon emissions from fishery production system in China

LI Chen1,2(), LI Haoyu1, KONG Haizheng3(), FENG Wei1

1. 1. School of Economics, Ocean University of China, Qingdao 266100, China
2. Marine Development Studies Institute, Ocean University of China, Qingdao 266100, China
3. Business School, Qingdao University of Technology, Qingdao 266520, China
• Received:2020-09-07 Revised:2020-11-13 Online:2021-06-25 Published:2021-08-25

Abstract:

In the face of the new development situation, the traditional mode of fishery production no longer can meet the requirements of the current social transformation. The low-carbon development of the fishery industry is an inevitable choice for its sustainable development in China, a practical need to ensure the national food security and promote the income increase of farmers (fishermen) and economic and social development, and is of great significance for fundamentally promoting the supply side structural reform of China’s marine fisheries. Based on the input-output model and the extended Kaya identity, this study examined the changing trend and structural characteristics of embodied carbon emissions in China’s fishery production system, and decomposed the driving factors of the embodied carbon emissions. The results show that: (1) Embodied carbon emission of fishery production system in China as a whole showed a trend of rising, slightly decreasing, rising again, and falling, the primary fishery sector always had the highest embodied carbon emissions, but the embodied carbon emissions of the secondary and tertiary fishery sectors increased gradually. (2) Fishery capture and aquaculture, processing, and circulation are the main sectors of the embodied carbon emissions in the fishery industry. The embodied carbon emission level per unit output value of the three fishery sectors and the 12 sub-sectors all showed a downward trend, among which the embodied carbon emission level per unit output value of fishery drug, aquatic transportation, and fishery construction sub-sectors was the highest, which had a great impact on the embodied carbon emissions of the fishery industry. (3) The fishery economic growth and general fishery technological progress have positive impact on the embodied carbon emissions of the industry, and fishery economic growth is the main factor that drives the growth of the embodied carbon emissions. Fishery population, fishery economic structure, and low-carbon fishery technology have a certain degree of restraining effect to the embodied carbon emissions. Low-carbon fishery technologies are the biggest factor to restrain the embodied carbon emissions of fisheries in China. Therefore, adjusting the structure of the fishery industry, changing the mode of fishery growth, and improving the application level of low-carbon fishery technologies are the key to effectively restraining the embodied carbon emissions and realize the low-carbon development of the fishery industry in China.


text:
# Show Reference: "Modulation of Neuronal Interactions Through Neuronal Synchronization"

Modulation of Neuronal Interactions Through Neuronal Synchronization Science (New York, N.Y.), Vol. 316, No. 5831. (15 June 2007), pp. 1609-1612, doi:10.1126/science.1139597 by Thilo Womelsdorf, Jan-Mathijs M. Schoffelen, Robert Oostenveld, et al.
@article{womelsdorf-et-al-2007,
abstract = {Brain processing depends on the interactions between neuronal groups. Those interactions are governed by the pattern of anatomical connections and by yet unknown mechanisms that modulate the effective strength of a given connection. We found that the mutual influence among neuronal groups depends on the phase relation between rhythmic activities within the groups. Phase relations supporting interactions between the groups preceded those interactions by a few milliseconds, consistent with a mechanistic role. These effects were specific in time, frequency, and space, and we therefore propose that the pattern of synchronization flexibly determines the pattern of neuronal interactions.},
author = {Womelsdorf, Thilo and Schoffelen, Jan-Mathijs M. and Oostenveld, Robert and Singer, Wolf and Desimone, Robert and Engel, Andreas K. and Fries, Pascal},
citeulike-article-id = {1391619},
day = {15},
doi = {10.1126/science.1139597},
issn = {1095-9203},
journal = {Science (New York, N.Y.)},
keywords = {synchrony},
month = jun,
number = {5831},
pages = {1609--1612},
pmid = {17569862},
posted-at = {2014-06-01 17:41:53},
priority = {2},
publisher = {American Association for the Advancement of Science},
title = {Modulation of Neuronal Interactions Through Neuronal Synchronization},
url = {http://dx.doi.org/10.1126/science.1139597},
volume = {316},
year = {2007}
}


text:
# What is the Implicit Function Theorem good for?

What are some applications of the Implicit Function Theorem in calculus? The only applications I can think of are:

1) the result that the solution space of a non-degenerate system of equations naturally has the structure of a smooth manifold;

2) the Inverse Function Theorem.

I am looking for applications that would be interesting to an advanced US math undergraduate or 1-st year graduate student who is seeing the Implicit Function Theorem for the first or second time. The context is I will be explaining this result as part of a review of manifold theory.

-
Coupled with Sard's theorem, you know "most" level-sets of smooth functions are smooth submanifolds. Lagrange multipliers are a big application, of course. –  Ryan Budney Sep 7 '10 at 0:04
Actually, as to 2), I personally find it more natural to see the Implicit FT as an application of the Inverse FT, rather than the opposite. –  Pietro Majer Sep 7 '10 at 7:16
I usually state the implicit function theorem and inverse function theorem as one theorem about the situation when $Df_x$ is an onto linear map. An interesting side-question, what do people call the corresponding theorem when $Df_x$ is a one-to-one linear map? I've been calling it the mono-split lemma or local embedding lemma or variants on that theme. –  Ryan Budney Sep 7 '10 at 8:00
One nice application (of the inverse fuction theorem I guess) is that the exponential map is a local diffeomorphism. This is useful for a bunch of stuff. An easy fact which follows is that the only connected abelian Lie groups are products of tori and copies of R^n. –  Callan McGill Feb 16 '12 at 5:02

The infinite-dimensional implicit function theorem is used, among other things, to demonstrate the existence of solutions of nonlinear partial differential equations and parameterize the space of solutions. For equations of standard type (elliptic, parabolic, hyperbolic), the standard version on Banach spaces usually suffices, but you have to be clever about which Banach space to use. There is a generalization of the implicit function theorem, due to Nash who used it to demonstrate the existence of isometric embeddings of Riemannian manifolds in Euclidean space, that works for even more general types of PDE's. Moser stated and proved a simpler version of the theorem. There is a beautiful survey article by Richard Hamilton (who originally used the Nash-Moser implicit function theorem to prove the local-in-time existence of solutions to the Ricci flow) on the Nash-Moser implicit function theorem.

-
In fact, if you set up everything the right way as Nijenhuis does in Strong Derivatives and Inverse Mappings Albert Nijenhuis The American Mathematical Monthly Vol. 81, No. 9 (Nov., 1974), pp. 969-980 the inverse function theorem is equivalent to the standard Picard's existence theorem in ODE's (with Lipschiz condition). –  alvarezpaiva Mar 17 '12 at 9:25
Just as a curiosity, here's an IFT argument about harmonic maps of the standard n-sphere near the identity that Peng Lu and I wrote up for a section in RF Part IV: math.ucsd.edu/~benchow/IFT-HarmonicMapsNearIdentitySn.pdf I assume it is a folklore result and I would like to know if any one has a reference for this. –  Bennett Chow Oct 15 '13 at 5:20

One of the major applications of Implicit Function Theorem is the lesson it teaches:

                      Locally, Manifold Theory = Linear Algebra.

That is, locally, we can perform our calculus as if it is linear algebra. Solving simultaneous equations, discussing about linear independence of coordinates, basis set and mapping from one manifold to another can be viewed as linear transformations. Discuss the invertability of functions as if they are linear transformations. Infact by Darboux theorem, in Symplectic manifold theory the linear algebra aspects is more prominent.

-
Exactly, thank you. Learning that lesson, and learning to treat submanifolds as subspaces in local coordinates, makes a lot of calculus much easier to grasp. –  Elizabeth S. Q. Goodman Feb 16 '12 at 3:26
Agreed 100%! I like to say that via the implicit function theorem, local differential geometry is just "nonlinear linear algebra". –  Deane Yang Feb 16 '12 at 13:55

I think of the implicit function theorem as a basic result that underlies many results in transversality and Morse theory. These two ideas are the major tools in the study of manifolds. You cannot understand manifolds without them.

So if we look at the inverse image of a non-degenerate critical value in a manifold it will have finitely many singular points. Outside a neighborhood of these, the pre-image appears as a submanifold. Local coordinates are obtained via the implicit function theorem. Look at any book on manifold theory and you will see it used.

-
I am confused. Isn't the statement "Outside a neighborhood of these [the critical points], the pre-image appears as a submanifold" an example of result "the solution space of a non-degenerate system of equations naturally has the structure of a smooth manifold." In your example, you are looking at the solutions to $f(x)=q_0$, for $q_0$ a regular value. Admittedly, my original statement was (intentionally) ambiguous. –  jlk Sep 7 '10 at 14:33
I meant outside a neighborhood of the singularity, but within the same level. –  Scott Carter Sep 7 '10 at 21:06
Thanks for the clarification! –  jlk Sep 27 '10 at 6:27

The Implicit Function Theorem appears in a typical undergraduate course on mathematical economics, and I find that application gives me more inspiration than applications in mathematics. Here is a simple example. Suppose a company's profit $\Pi$ is a function of the number $x$ of widgets they produce (which they can choose) and a vector of other variables $\vec{y}$ over which they have no control (the price at which they can sell the widgets, cost of raw materials, etc.). Then by Calc 1, the profit-optimizing quantity $x^\ast$ will satisfy the equation $\frac{\partial}{\partial x} \Pi \vert_{x = x^\ast} = 0$.

The Implicit Function Theorem says that ${x^\ast}$ is a function of $\vec{y}$. This is just the unsurprising statement that the profit-maximizing production quantity is a function of the cost of raw materials, etc. But the IFT does better, in that in principle you can evaluate the derivatives $\partial x^* / \partial y_i$. If the company acts to maximize its profit, then these derivatives predict how the company will change its production in response to changes in external factors such as the cost of raw materials.

(You might be worried about the hypothesis in the IFT that $\frac{\partial^2}{\partial x^2} \Pi$ is nonzero. But in this example it is trivially satisfied because economists usually assume that marginal cost is increasing and that marginal revenue is decreasing, or anyway increasing more slowly than marginal cost.)

-

If you go a little bit further than the inverse and implicit function theorems, you can get a fairly practical theorem. Kantorovich's theorem gives you fairly strong sufficient conditions for a system of smooth equations to have a solution. Moreover it tells you how quickly Newton's method converges in that situation. For example, this theorem is used by Harriet Moser to prove that SnapPea does give approximations to actual solutions to the hyperbolic gluing equations. The applications of course are pretty broad, this is one on the fairly pure end of the spectrum. Kantorovich was an economist although I do not understand the economics problems he was interested in.

If you're interested, this perspective on the inverse and implicit function theorems is in "full glory" in Hubbard's multi-variable calculus text.

2nd answer: The proof of Sard's theorem is a delicate dance with the Implicit Function Theorem, Taylor's Theorem and some basic argument with Lebesgue measure zero.

-

One elementary application to ODEs: a differential equation $$u'(t)=f(t, u(t ))$$ with a continuous RHS of the form

$$f(t,x):=-\frac{\partial_t g(t,x)}{\partial_x g(t,x)},$$ for some $C^1$ function $g$ with non-vanishing $\partial_x g,$ has a one-parameter family of solutions whose graphs are the level sets of $g$. This is a largely used solution method, but it's the IFT that ensures that these solutions are indeed well-defined functions, implicitly defined by $g(t,u(t))=c.$ Incidentally, note that this is a case where there holds uniqueness for the Cauchy problem, even if the Lipschitz assumptions may fail to hold.

-
IFT is very crucial in Cauchy-Kowalevski theorem which is fundamental to question of solvability of linear partial differential equations in the analytic framework. This is just a PDE version of the answer given above. –  Uday Apr 1 '12 at 17:15

In studying how the fixed points of a one parameter family of real functions $f_\mu(x)=f(x,\mu)$ as the parameter $\mu$ changes, one is lead to study the solutions of the equation $$f(x,\mu)=x.$$ The implicit function theorem is the right tool for this task, and in general, for the study of bifurcation in dynamical systems, both continuous and discrete.

-

See the article: Nord, Gail; David Jabon, and John Nord; The Global Positioning System and the Implicit Function Theorem, SIAM Review, vol. 40:3 (1998), 692--696; for a nice application of the IFT to estimating the errors involved in GPS measurements.

-
Thanks! The article looks interesting! –  jlk Sep 8 '10 at 4:04

The implicit function theorem is critical in the theory of manifolds (especially that of Riemann surfaces) in showing that a subvariety of affine or projective space is actually a submanifold. I found this out bluntly after trying to read a textbook on Riemann surfaces and realizing that I didn't entirely understand it for this reason. Furthermore, the conditions of the implicit function theorem motivate the definition of a non-singular point of a variety, and in more advanced algebraic geometry, the notion of an etale map. Another important notion in algebraic geometry motivated by the implicit function theorem is that of a local complete intersection. To read an elementary account of this latter notion, see I.3 of Algebraic Curves and Riemann Surfaces by Miranda.

A good book to see how multivariable calculus and commutative algebra interact is Smooth Manifolds and Observables by Nestruev.

-
@Davidac897, Thanks! One typo: a non-singular subvariety of an affine space is a submanifold, not an arbitrary subvariety. –  jlk Sep 7 '10 at 6:48
Right - what I meant is that if you have a subvariety and if it is a submanifold and you want to show that it is one, then you (often) use the implicit function theorem to do so. I wasn't implying that it's always a submanifold. –  David Corwin Sep 7 '10 at 7:09

One thing I've learned recently (moving into symplectic geometry from topology) is that people often underestimate the value of regarding manifolds locally as graphs of functions, or submanifolds of Euclidean space. The IFT helps with this, and provides actual applications, but here's possible motivation.

--My recent favorite example for intuition: How does a surface of negative curvature behave? Like the graph of a harmonic function on $\mathbb R^2$ (where the Hessian is not 0). That is to say, if you have trouble imagining a surface in $\mathbb R^3$ which has no hills and valleys but only saddles, try graphing a function like $xy$ or $e^x\cos y$.

--Related to this: use IFT to study the curvature of a surface in $\mathbb R^3$ (or $n$-manifold in $\mathbb R^{n+1}$) nearby a strict maximum in any one coordinate. I'm not sure what the nicest precise statement should be here to cover all non-generic cases, but it's fun route to differential geometry if someone hasn't had it.

--Less directly related to the IFT: What does a Morse critical point "look like''? We like to say that the Morse function can be given in some local coordinates by $x_1^2+\ldots +x_k^2-x_{k+1}^2-\ldots x_n^2$, but when we visualize this, we usually see the manifold (OK, surface) itself as the graph of that function over a piece of $\mathbb R^n$. Thus making the Morse function "height" as usual.

-

I like to begin an introduction to manifolds by proving that the following conditions on a subset of $\mathbb R^n$ are equivalent:

1. Locally it can be mapped to an open subset of $\mathbb R^p\times 0$ by a diffeomorphism between open subsets of $\mathbb R^n$.

2. Locally it appears as the graph of a smooth function expressing $n-p$ of the coordinates as functions of the other $p$.

3. Locally it is $f^{-1}(0)$ for a smooth map to $\mathbb R^{n-p}$ whose derivative has maximal rank (i.e. rank $n-p$).

4. Locally it is the image of a smooth map from $\mathbb R^p$ of maximal rank (i.e. rank $p$).

2 implies 1 easily. 1 implies 3 and 4 easily. 4 implies 2 by the inverse function theorem in dimension $p$. 3 implies 2 (this implication might be called the implicit function theorem) by the inverse function theorem in dimension $n$.

I like to think that any one of these four would serve as a good definition of "smooth $p$-dimensional manifold in $\mathbb R^n$" for those who have not studied abstract manifolds, but that you haven't really begun to get into the subject until you see that they are the same.

-

A fundamental application is

Theorem Let $t\mapsto A(t)$ a $C^1$-family of $n\times n$ matrices. If at $t=0$, $A(0)$ has a simple eigenvalue $\lambda_0$, then for $t$ small enough, $A(t)$ admits a simple eigenvalue $\lambda(t)$ that is a $C^1$-function of $t$ and is such that $\lambda(0)=\lambda_0$. In addition, its derivative at $t=0$ is given by $\dot\lambda(0)=x^*\dot A(0)x$ where $x$ is the normalized ($\|x\|=1$) eigenvector associated with $\lambda_0$.

Of course, there are infinite-dimensional versions of this statement. Both finite and infinite-dimensinal versions are used daily by hundreds of mathematicians.

-

By changing coordinates you can make a simple function appear compluicated. Have you ever asked yourself if the opposite is true: givern a "complicated" function, can I make it look simpler in a neighborhood of a point by changing thecoordinates near that point?

The implicit function theorem states that if that point is not a critical point, then you can find coodinates near that point such that, in these coordinates the function is a linear function.

-
Very useful observation for reductions of pseudodifferential operators. –  Uday Apr 11 '12 at 1:55
For polynomials over the $p$-adic numbers there is a version of the implicit function theorem which makes the domain of the implicit function precise. I'll state the two-variable version here, along with an application to counting congruences modulo powers of $p$. Both generalise easily to any number of variables.
Let $f(X,Y) \in \mathbf{Z}_p[X,Y]$. Suppose that $a, b \in \mathbf{Z}_p$ are such that $f(a,b) = 0$ and $\frac{\partial f}{\partial X}(a,b) \not\equiv 0$ mod $p$. Then there exists a continuous function $g : b + p\mathbf{Z}_p \rightarrow a + p\mathbf{Z}_p$ such that if $y \in b + p\mathbf{Z}_p$ then $f(x,y) = 0$ if and only if $x = g(y)$.
I learned of an application of this result from Benjamin Klopsch. Suppose that $f(X,Y) \in \mathbf{Z}[X,Y]$ is non-singular and let $N_k(f)$ be the number of residue classes $(x,y) \in (\mathbf{Z} / p^k \mathbf{Z})^2$ such that $f(x,y) \equiv 0$ mod $p^k$. Applying the result above to each solution of $f(a,b) \equiv 0$ mod $p$ gives $N_k(f) = N_1(f)p^{k-1}$ for all $k \ge 1$.


text:
# cross product example

Already registered? - Definition & Examples, Identifying the Constant of Proportionality, Inverse Operations in Math: Definition & Examples, Centroid & Center of Mass of a Semicircle, Ratios and Proportions: Definition and Examples, What Are Coplanar Points? Find the length and direction? © copyright 2003-2020 Study.com. Dot product is also known as scalar product and cross product also known as vector product. Since you can only compare two fractions at a time with this method, you'll need to repeat it if you are comparing more than two fractions. a x b = i (a2 b3 – a3 b2) + j (a3 b1 – a1 b3) + k (a1 b2 – a2 b1) a x b = i {2 * 7 – (-5) * (-3)} + j { (-5) * 2 – 4 * 7} + k {4 * (-3) – 2 * 2} a x b = -i + ( – 38 j) + ( – 16 k) Therefore, the vector cross product of the two vectors (4, 2, -5) and (2, -3, 7) is (-1, -38, -16). study a) Compute \langle 3, 1, 0 \rangle \times \langle -1, 1, 2 \rangle. The Cross Product Method. If the denominators are the same, the fraction with the largest numerator is larger. To unlock this lesson you must be a Study.com Member. We can only compare two fractions at a time with this method, so if you're trying to compare more than two fractions, you'll need to repeat these steps using two fractions at a time. courses that prepare you to earn Anyone can earn In this lesson, you'll learn how to perform the cross product method accurately and understand the results in order to identify which fraction is bigger or smaller or if the fractions are equivalent. Not sure what college you want to attend yet? - Definition & Examples, Quiz & Worksheet - Cross Product Rule & Properties, Over 83,000 lessons in all major subjects, {{courseNav.course.mDynamicIntFields.lessonCount}}, How to Perform Addition: Steps & Examples, How to Perform Subtraction: Steps & Examples, How to Perform Multiplication: Steps & Examples, How to Multiply Large Numbers: Steps and Examples, How to Perform Division: Steps & Examples, Performing Long Division with Large Numbers: Steps and Examples, The Commutative Property: Definition and Examples, The Associative Property: Definition and Examples, The Multiplication Property of Zero: Definition & Examples, Arithmetic Calculations with Signed Numbers, Commutative Property: Definition & Examples, Cross Multiplication: Definition & Examples, High School Algebra II: Tutoring Solution, Biological and Biomedical Be sure to write your products down in such a way that you can identify which fraction they each represent. - Definition & Examples, Solving Equations with Infinite Solutions or No Solutions, What Is Scientific Notation? and career path that can help you find the school that's right for you. {{courseNav.course.topics.length}} chapters | Also find the volume of the parallelepiped with PQ, PR, and PQ, 1.a)Find a non-zero vector orthogonal to the plane through the points P\left ( 1,0,0 \right ),Q\left ( 4,-2,3 \right ),R\left ( -1,2,1 \right ) b)Find the volume of a parallelpiped through the positio. {{courseNav.course.mDynamicIntFields.lessonCount}} lessons Visit the High School Algebra II: Tutoring Solution page to learn more. Let a, b, c be vectors such that a \times b = c, b \times c = a and c \times a = b. A vector has magnitude (how long it is) and direction:. Calculate the cross product between $\vc{a} = (3, -3, 1)$ and $\vc{b} = (4,9,2)$. If the products are identical, the fractions are equivalent. Earn Transferable Credit & Get your Degree, What is a Proportion in Math? - Definition, Formula & Examples, What is a Line Segment in Geometry? In this case if the line of action of the force is extended and a perpendicular is dropped on it from the point of calculation of torque then this perpendicular is called as moment arm. a) Find the curl of the vector field. Try refreshing the page, or contact customer support. Be sure to leave a space in between them, like this: Draw an 'X' diagonally between the two fractions. Services. It's critical that you multiply upward diagonally to get accurate products for the corresponding fractions. Being a vector operation, the cross product is extremely important in all sorts of sciences (particularly physics), engineering, and mathematics. As a member, you'll also get unlimited access to over 83,000 Enrolling in a course lets you earn progress by passing quizzes and exams. Direction of torque can be calculated by the rules of cross product. succeed. The magnitude (length) of the cross product equals the area of a parallelogram with vectors a and b for sides: Dot Product – Let we have given two vector A = a1 * i + a2 * j + a3 * k and B = b1 * i + b2 * j + b3 * k. Where i, j and k are the unit vector along the x, y and z directions. (when defined) of u  v. u = 4i + 9j v = i - j. It involves multiplying the numerator of one fraction by the denominator of … Two vectors can be multiplied using the "Cross Product" (also see Dot Product). 's' : ''}}. By multiplying fractions a certain way, you can quickly see which fraction is smaller, which fraction is larger, or if they're equivalent. The cross product method is used to compare two fractions. Example #2. Biology Lesson Plans: Physiology, Mitosis, Metric System Video Lessons, Lesson Plan Design Courses and Classes Overview, Online Typing Class, Lesson and Course Overviews, Diary of an OCW Music Student, Week 4: Circular Pitch Systems and the Triad, Personality Disorder Crime Force: Study.com Academy Sneak Peek.

Sea Anemone Symmetry, Janome Hd3000 Second Hand, Sonic Character Colors, Kurayami Meaning In Japanese, Good And Gather Garlic Hummus, Epsom Salt For Succulents, Social Constructionism Religion, How To Choose Balsamic Vinegar,


text:
How To Scale A Pssm For Ncbi Blast
2
5
Entering edit mode
11.3 years ago

Hi again,

I'm trying to do a local NCBI BLAST search using the PSSM of a conserved CDD domain (.smp file in the database, cave LARGE file).

My database is containing nucleotide sequences and the PSSM is for proteins, so I would like to use tblastn for this search. The tblastn executable accepts PSSMs, so no problem there.

But: the matrix in the .smp file is scaled by a factor of 100; according to the specs, the BLAST program should be able to downscale the matrices back to a factor of 1 automatically.

If I'm running tblastn however, I get the following error:

BLAST engine error: PSSM has a scaling factor of 100. PSI-BLAST does not accept scaled PSSMs

Now, is there either a way to run tblastn with scaled matrices or a tool to scale them? And if not, do I just scale the matrix values by 1/100 or the lambda, kappa and h factors (whatever these are) as well?

blast pssm • 4.9k views
2
Entering edit mode
11.3 years ago

I am not aware of any tool that can do what you want to do. This is what I would do to eliminate the scaling:

• Change the scaling factor from 100 to 1
• Divide all weights in the PSSM by 100
• Possibly multiply lambda by 100
• Keep kappa and h unchanged

The part about the scaling factor and the weights should be self-explanatory (and you indeed suggested to do the same yourself).

The reason for possibly having to scale lambda is that it is used in the Karlin-Altschul formula: E = kappa*N*exp(-lambda*S). The big question is if BLAST corrects S for the scaling factor before plugging it into this formula. If it does, you should not change lambda. If it does not, you need to multiply lambda by 100 when dividing all the weights in the PSSM by 100. I sadly do not know the finer details of BLAST well enough to know which is the case.

The way kappa is used in the formula means that it should not be affected by the scaling factor. The parameter H is the entropy, which is used for calculating the effective length of query sequences and sequences in the database. The formula used is effective_length = max(length-lambda*S/H, 1). Consequently, H should also not be effected by the scaling (since lambda*S should be unchanged).

0
Entering edit mode

Thanks for the answer! I have some things to add I found out myself meanwhile: lambda, kappa, and h values are stored as triplets of numbers in the NCBI smp files, eg. lambda { 267, 10, -3 }. I think that means a value of 267 * 10^-3 = 0.267, being saved in this fashion because the format only supports integers as values. Thus dividing the weights by 100 will result in a loss of accurary, which in my case will not matter much because I use this search only as a pre-filtering step.

0
Entering edit mode

Yes, no surprise that dividing the weights by 100 will result in a loss of accuracy. As far as I understand, the whole purpose of initially scaling them up by a factor of 100 was to increase accuracy. Great that you figured out what the triplets mean - it was not clear to me at all :-)

0
Entering edit mode
11.3 years ago

Here is a little Python script for scaling a matrix with factor 100 down to 1. It does, however, only perform string operations and thus not round values. Lambda is also kept as is.

The Results are reasonable so far, the effect of the rounding error seems to be a minor one (with Lambda*100 results are weird, so I guess this is the right approach).

Usage: script infile outfile

#!/usr/bin/env python

import sys, re
f = open(sys.argv[1], 'r')
f.close()

start = content.find("scores {")
end = content.find("}", start)
scores = re.sub("([0-9]{2})(?=[\r\n\,])", "", content[start:end])
scores = re.sub("\ (\-)?,", " 0,", scores)

f = open(sys.argv[2], 'w')
f.write(content[0:start] + scores +
content[end:].replace("scalingFactor 100", "scalingFactor 1"))
f.close()


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 16 Jul 2018, 07:47

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# If n is an integer, which of the following CANNOT be

Author Message
TAGS:

### Hide Tags

Intern
Joined: 16 Jun 2010
Posts: 18
If n is an integer, which of the following CANNOT be [#permalink]

### Show Tags

Updated on: 03 Jul 2013, 00:54
6
00:00

Difficulty:

35% (medium)

Question Stats:

71% (00:53) correct 29% (01:03) wrong based on 230 sessions

### HideShow timer Statistics

If n is an integer, which of the following CANNOT be a factor of 3n+4?

A. 4
B. 5
C. 6
D. 7
E. 8

Originally posted by chintzzz on 19 Jun 2010, 02:31.
Last edited by Bunuel on 03 Jul 2013, 00:54, edited 1 time in total.
Renamed the topic and edited the question.
Math Expert
Joined: 02 Sep 2009
Posts: 47016

### Show Tags

19 Jun 2010, 02:43
chintzzz wrote:
If n is an integer, which of the following CANNOT be a factor of 3n+4?

A.4
B.5
C.6
D.7
E.8

$$3n+4=3(n+1)+1$$ cannot be a multiple of 3, it's 1 more than multiple of 3: ... 4, 7, 10, 13, 16, ... Hence it cannot be a multiple of 2*3=6 as well.

_________________
CEO
Joined: 12 Sep 2015
Posts: 2630
Re: If n is an integer, which of the following CANNOT be [#permalink]

### Show Tags

21 Nov 2017, 10:04
Top Contributor
chintzzz wrote:
If n is an integer, which of the following CANNOT be a factor of 3n+4?

A. 4
B. 5
C. 6
D. 7
E. 8

KEY CONCEPTS
If a number is divisible by 6 it MUST also be divisible by 3
Conversely, if a number is NOT divisible by 3, then that number is NOT divisible by 6

3n + 4 = 3n + 3 + 1
= 3(n + 1) + 1
We can see that 3n+4 is 1 greater than some multiple of 3
This tells us that 3n+4 is NOT divisible by 3
This means (from the rules above) that 3n+4 is NOT divisible by 6

Cheers,
Brent
_________________

Brent Hanneson – Founder of gmatprepnow.com

CEO
Joined: 12 Sep 2015
Posts: 2630
Re: If n is an integer, which of the following CANNOT be [#permalink]

### Show Tags

21 Nov 2017, 10:09
1
Top Contributor
chintzzz wrote:
If n is an integer, which of the following CANNOT be a factor of 3n+4?

A. 4
B. 5
C. 6
D. 7
E. 8

Another approach is to plug in integer values for n and start ELIMINATING answer choices..

Try n = 0
So, 3n + 4 = 3(0) + 4 = 4
4 IS a factor of 4
ELIMINATE A

Try n = 1
So, 3n + 4 = 3(1) + 4 = 7
7 IS a factor of 7
ELIMINATE D

Try n = 2
So, 3n + 4 = 3(2) + 4 = 10
5 IS a factor of 10
ELIMINATE B

Try n = 3
So, 3n + 4 = 3(3) + 4 = 13
Doesn't help...

Try n = 4
So, 3n + 4 = 3(4) + 4 = 16
8 IS a factor of 16
ELIMINATE E

By the process of elimination, the correct answer is C

Cheers,
Brent
_________________

Brent Hanneson – Founder of gmatprepnow.com

Re: If n is an integer, which of the following CANNOT be   [#permalink] 21 Nov 2017, 10:09
Display posts from previous: Sort by

# Events & Promotions

 Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.