text:
# In which article/book chapter did Cantor, Hibert, and Poincare formally defined or directly discussed the term “potential infinity”?

Some media sources say that "Cantor claimed that there would only be potential infinity, not actual infinity"

In addition, the following link claims that Hilbert, Poincare, and Cantor were fully aware of the distinction between "potential infinity" and the actual one.

Is there a formal distinction between potential and actual infinities?

Of course all those mathematicians talked a lot about infinity in their publications; however I am having trouble to find exact quote on "potential infinity" from them. In which chapters did they mention the exact term "potential infinity"?

I did notice that Fraenkel mentioned "potential infinity" a lot, but not for Hilbert or Poincare.

• Welcome to HSM. The article you have linked in your first sentence appears to be full of inaccuracies and falsehoods. For example, it states "For instance, Cantor proved that the set of all functions from $(0,1)$ →$\mathbb N$ is countable. Thus he defined a one-to-one and onto function from the interval $(0,1)$ to natural numbers." This is plainly false, and not entirely coherent. Also, the statement you attribute to Cantor in the first sentence of your post is, according to the article, the view of Aristotle rather than Cantor. – Nick Jun 26 at 21:38
• @Nick I agree, that part is definitely incorrect. – High GPA Jun 26 at 22:40

You have misinterpreted the article you refer to; nowhere does it say that "Cantor claimed that there would only be potential infinity, not actual infinity". In fact, it says the opposite:

Furthermore, Cantor claimed that we could add and multiply infinity sets. Until that time, humans had followed Aristotle’s ideas about infinity. According to Aristotle, if we multiply the number 3 by infinity, it would be infinite again. Infinity would swallow everything. Based on this, he claimed that there would only be potential infinity, not actual infinity.

It's Aristotle claiming that there is only potential infinity, and we have since learned that in many ways, Aristotle was just a big windbag.

A potential infinity is the kind we work with all the time in calculus: the limit of something as something else controlling it it is allowed to grow with out bound. There is no "largest" natural number, you can always add one and get a bigger one. In a set-theoretical framework with basic axioms, any proper class is a potential infinity.

An absolute infinity is a "completed" one. As Cantor later showed, you need a whole new axiom to make it work formally. The usual way to do this is to assert the existence of a complete set of natural numbers ($$\omega$$) as an object you can manipulate. It's this Axiom of Infinity that formally defines an absolute infinity.

A number of years ago I was led to the infinite real whole numbers [die unendlichen realen ganzen Zahlen] without having realized that they were concrete numbers of real significance.$$^1$$

Cantor would never have claimed there was only potential infinity. His transfinite numbers are all completed ones.

Joseph Warren Dauben's biography of Cantor discusses this concept in Chapter 5, which is all about Cantor's 1883 Grundlagen einer allgemeinen Mannigfaltigskeitlehre.This title may cause you to do a double-take, as it transtates as "Foundations of a Theory of Manifolds". Here is the quote you're looking for:

As far as the mathematical infinite is concerned: to the extent that it has found justifiable use in science and made a useful contribution, the mathematical infinite has principally occurred in the meaning of a variable magnitude, either growing beyond all limits or diminishing to an arbitrary smallness, always, however remaining finite. I call this infinite the non-genuine-infinite [das Uneigentlich-unendliches].$$^2$$

There was great opposition to Cantor's ideas by people who couldn't wrap their heads around them. There's a remarkable quote later on in the book, criticizing "proofs" that completed infinities couldn't exist, because they assumed there were only potential infinities to begin with:

All so-called proofs against the possibility of actually infinite numbers are faulty, as can be demonstrated in every particular case, and as can be concluded on General grounds as well. It is their πρώτον ψεύδος [first lie] that from the outset they expect or even impose all the properties of finite numbers upon the numbers in question, while on the other hand the infinite numbers, if they're to be considered in any form at all, must (in their contrast of the finite numbers) constitute an entirely new kind of number, whose nature is entirely dependent upon the nature of things and is an object of research but not of our arbitrariness or prejudices.

-Cantor to Eneström$$^3$$

$$^1$$:Georg Cantor: His Mathematics and Philosophy of the Infinite, by Joseph Warren Dauben, Princeton University Press, 1990, quotation, p. 57

$$^2$$Cantor, G. Grundlagen einer allgemeinen Mannigfaltigskeitlehre. Ein mathematisch-philosophischer Versuch in der Lehre des Unendlichen. Leipzig, B.G. Teubner, 1883. Later in Mathematische Annalen. Translated by Uwe Parpart, first appearing in The Campaigner, January-February 1976, Vol 9 Nos. 1-2, P. 70.

$$^3$$ Dauben, quotation, p. 125


text:
## Research

### (Pre)publications

• "Fundamental groups of real arrangements and torsion in the lower central series quotients." (with E. Artal & B. Guerville-Ballé)
Experimental Mathematics (2018), journal , arXiv:1704.04152 12 pags.
Abstract↴

We prove that the fundamental group of the complement of a real complexified line arrangement is not determined by its intersection lattice, providing a counter-example for a problem of Falk and Randell. We also deduce that the torsion of the lower central series quotients is not combinatorially determined, which gives a negative answer to a question of Suciu.

• "Configurations of points and topology of real line arrangements." (with B. Guerville-Ballé)
(Submitted), arXiv:1702.00922 52 pags, including two appendix with detailled pictures of Zariski pairs.
Abstract↴

A central question in the study of line arrangements in the complex projective plane $\mathbb{CP}^2$ is: when does the combinatorial data of the arrangement determine its topological properties? In the present work, we introduce a topological invariant of complexified real line arrangements, the chamber weight. This invariant is based on the weight counting over the points of the arrangement dual configuration, located in particular chambers of the real projective plane $\mathbb{RP}^2$, dealing only with geometrical properties.

Using this dual point of view, we construct several examples of complexified real line arrangements with the same combinatorial data and different embeddings in $\mathbb{CP}^2$ (i.e. Zariski pairs), which are distinguished by this invariant. In particular, we obtain new Zariski pairs of 13, 15 and 17 lines defined over $\mathbb{Q}$ and containing only double and triple points. For each one of them, we can derive degenerations, containing points of multiplicity 2, 3 and 5, which are also Zariski pairs.

We explicitly compute the moduli space of the combinatorics of one of these examples, and prove that it has exactly two connected components. We also obtain three geometric characterizations of these components: the existence of two smooth conics, one tangent to six lines and the other containing six triple points, as well as the collinearity of three specific triple points.

• "A semi-canonical reduction for periods of Kontsevich-Zagier."
(Submitted), arXiv:1509.01097 26 pags.
Abstract↴

The ${\overline{\mathbb Q}}$-algebra of periods was introduced by Kontsevich and Zagier as complex numbers whose real and imaginary parts are values of absolutely convergent integrals of ${\mathbb Q}$-rational functions over ${\mathbb Q}$-semi-algebraic domains in ${\mathbb R}^d$. The Kontsevich-Zagier period conjecture affirms that any two different integral expressions of a given period are related by a finite sequence of transformations only using three rules respecting the rationality of the functions and domains: additions of integrals by integrands or domains, change of variables and Stoke's formula.

In this paper, we prove that every non-zero real period can be represented as the volume of a compact ${\overline{\mathbb Q}}\cap{\mathbb R}$-semi-algebraic set, obtained from any integral representation by an effective algorithm satisfying the rules allowed by the Kontsevich-Zagier period conjecture.

• "Combinatorics of line arrangements and dynamics of polynomial vector fields." (with B. Guerville-Ballé)
(Submitted), arXiv:1412.0137 14 pags.
Abstract↴

Let $\mathcal{A}$ be a real line arrangement and $\mathcal{D}(\mathcal{A})$ the module of $\mathcal{A}$–derivations. First, we give a dynamical interpretation of $\mathcal{D}(\mathcal{A})$ as the set of polynomial vector fields which posses $\mathcal{A}$ as invariant set. We characterize polynomial vector fields having an infinite number of invariant lines. Then we prove that the minimal degree of polynomial vector fields fixing only a finite set of lines in $\mathcal{D}(\mathcal{A})$ is not determined by the combinatorics of $\mathcal{A}$.

• "On the minimal degree of logarithmic vector fields of line arrangements." (with B. Guerville-Ballé)
Proc. XIII Intern. Conf. on Maths. and its Appl., (40), 61-66 (2016), journal .

### In preparation

• "On the equality of periods of Kontsevich-Zagier", with J. Cresson .
• "Constructing Zariski pairs of line arrangements with a given sub-combinatorics.", with B. Guerville-Ballé.
• "Decibability and 0-recognition problem for periods of Kontsevich-Zagier.", with M. Yoshinaga.

format: plain


text:
# Fitting polynomials by generating linear constraints

(There were some slight edits since the original publication. The only major change is that the time to solve each linear program probably grows cubically, not linearly, with the number of points.)

This should be the first part in a series of post exploring the generation of efficient and precise polynomial approximations. Yes, there is Lisp code hidden in the math (: See rational-simplex and vanilla-fit.

Here’s the context: we want to approximate some non-trivial function, like $$\log$$, $$\exp$$ or $$\sin$$ on a computer, in floating point arithmetic. The textbook way to do this is to use a truncated Taylor series: evaluating polynomials is pretty quick on computers. Sam Hocevar’s post on the topic does a very good job of illustrating how wrong-headed the approach is in most cases. We should instead try to find an approximation that minimises the maximal error over a range (e.g. $$[-\pi,\pi]$$ for $$\sin$$). He even has LolRemez to automatically compute such approximations for given functions. (While we’re kind of on the topic, the very neat Chebfun applies closely-related ideas to try and be to continuous functions what floating point numbers are to reals.)

The LolRemez docs point out two clever tricks to get more efficient approximations: forcing odd or even polynomials, and fixing parameters to simple values. Could we automate this process?

The goal of this series is to show that we can, by applying Operations Research (“The Science of Better”) to this micro-optimisation challenge. OR is what I do during the day, as a PhD student, and I believe that there’s a lot of missed opportunities in nifty program optimisation or analysis. (I also think that language design has a lot to offer to OR people who cope with modeling languages that have only changed incrementally since the seventies. :)

## Problem statement

For now, let’s try and solve the original problem: find, in a family of functions $$F$$ (e.g. polynomials of degree 4), an approximation $$\tilde{f}$$ of a function $$f$$ over some bounded range $$B\subset R$$ such that $$\tilde{f}$$ minimises the maximal error over that range:

$$\tilde{f} = \mathop{\arg\min}_{g \in F}\max_{x\in B} |g(x)-f(x)|.$$

$$B$$ is a dense set, with infinitely, if not uncountably, many elements, so it’s far from obvious that we can solve this, even up to negligible errors.

## The Remez algorithm

The Remez exchange algorithm shows one way to solve the minimax approximation problem, from the realm of mathematical analysis.

Let’s pretend we do not know $$\tilde{f}$$, but do know the points where its error from $$f$$ is maximised. In fact, if we are looking for polynomials of degree $$n$$, we only need $$n+2$$ such points. Let’s further impose that the errors alternate in sign: i.e., if the points are ordered ($$x_0 < \ldots < x_i < \ldots < x_{n+1}$$), then $$\tilde{f}(x_0) < f(x_0)$$, $$\tilde{f}(x_1) > f(x_1)$$, etc., or vice versa. Nifty analysis results tell us that these points exist, and that they exhibit the same absolute error $$|\epsilon|$$. We can now find the coefficients $$a_0,a_1,\ldots,a_n$$ of $$\tilde{f}$$ by solving a small linear system:

$$\sum_{j=0}^n a_j x_0^j = f(x_0) + \epsilon$$ $$\sum_{j=0}^n a_j x_1^j = f(x_1) - \epsilon$$

etc. for each $$x_i$$.

There are $$n+2$$ variables (the $$n+1$$ coefficients $$a_j$$ and $$\epsilon$$), and $$n+2$$ constraints (one for each extremum), so it’s a straight linear solve.

Of course, we don’t actually know these extremal error points $$x_i$$. The Remez algorithm works because we can initialise them with an educated guess, find the corresponding coefficients, construct a new approximation from these coefficients, and update (some) of the extremal points from the new approximation. In theory this process converges (infinitely) toward the optimal coefficients. In practice, numerical issues abound: solving a linear system is usually reasonably stable, but finding exact function extrema is quite another issue. The upside is that smart people like Sam and the boost::math team have already done the hard work for us.

## A linear minimax formulation

The minimax objective can be reformulated as an optimisation problem over reals (or rationals, really) with linear constraints and objective, a linear program:

$$\min_{e\in\mathbb{R}, a\in\mathbb{R}^{n+1}} e$$ subject to $$\sum_{i=0}^n a_ix^i \leq f(x) + e\qquad\forall x\in B$$ $$\sum_{i=0}^n a_ix^i \geq f(x) - e\qquad\forall x\in B$$

In words, we’re trying to find an error value $$e$$ and $$n+1$$ coefficients, such that the error $$|\tilde{f}(x)-f(x)|\quad\forall x\in B$$ is at most $$e$$: $$-e \leq \tilde{f}(x)-f(x)\leq e$$. The goal is to minimise that error value $$e$$.

We’re still left with the issue that $$B$$ is very large: infinite, or even uncountable. It doesn’t make sense to have two constraints for each $$x\in B$$! Our goal is to find approximations in floating point arithmetic, which helps a bit: there’s actually a finite number of floating point (single, double or otherwise) values in any range. That number, albeit finite, still tends to be impractically large. We’ll have to be clever and find a good-enough subset of constraints. Note that, unlike the Remez algorithm, we can have as many constraints as we want; we never have to remove constraints, so the quality of the approximation can only improve.

This method is an interesting alternative to the Remez algorithm because it always converges, finitely, even with (or rather, due to) floating-point arithmetic. It will also makes our future work on a branch-and-cut method marginally easier.

## Rational simplex for exact solutions to linear programs

We’ve reformulated our problem as a finite linear program, assuming that we know for which point $$x\in B$$ we should generate constraints. How can we find solutions?

LPs are usually solved with variants of the simplex algorithm, a combinatorial algorithm. This is the key part: while most of the algorithm is concerned with numerical computations (solving linear systems, etc.), these are fed to predicates that compare values, and the results of the comparisons drive each iteration of the algorithm. The key insight in the simplex algorithm is that there exists at least one optimal solution in which all but a small set of variables (the basis) are set to zero, and the value of the basic variables can then be deduced from the constraints. Better: every suboptimal (but feasible) basis can be improved by only substituting one variable in the basis. Thus, each iteration of the algorithm moves from one basis to a similar, but better, one, and numerical operations only determine whether a basis is feasible and is an improvement. Very little information has to persist across iterations: only the set of basic variables. This means that there is no inherent accumulation of round-off errors, and that we can borrow tricks from the computational geometry crowd.

Daniel Espinoza implemented that, and much more, for his PhD thesis on exact linear and integer program solvers. QSopt-Exact is a GPL fork of a fairly sophisticated simplex and branch and cut program. It exploits the fact that the simplex algorithm is combinatorial to switch precision on the fly, using hardware floats (single, double and long), software quad floats, multiprecision floats, and rational arithmetic. Unfortunately, the full solver segfaults when reporting solution values on my linux/x86-64 machine. Still, the individual simplex solvers (with double floats, quad floats, multiprecision floats and rationals) work fine. What I decided to do was to sidestep the issue and call the solvers in increasing order of precision, while saving the basis between calls. The double float implementation is executed first, and when it has converged (within epsilon), a more precise solver is called, starting from the basis on which the previous solver converged, etc. The final rational solver is exact, but very slow. Hopefully, previous solvers, while inexact, will have converged to very nearly-optimal bases, leaving only a couple iterations for the exact solver.

Rational-simplex is a one-file CL system that wraps QSopt-Exact and offers a trivial modeling language. We’ll use it a lot in the sequel.

## Solving the minimax LP with rational-simplex

linf-fit.lisp implements a minimax linear fit in 60 LOC (plus a couple kLOC in QSopt :).

Each point is defined by loc, the original value for x, a sequence of parameters (in this case, powers of x as we’re building polynomials), and the value to approximate, $$f(x)$$.

solve-fit takes a sequence of such points, and solves the corresponding LP with QSopt-Exact:

(defun solve-fit (points)
(lp:with-model (:name "linf fit" :sense :minimize)
(let ((diff  (lp:var :name "diff" :obj 1))
(coefs (loop for i below *dimension* collect
(lp:var :name (format nil "coef ~A" i)
:lower nil))))
(map nil (lambda (point)
(let ((lhs (linexpr-dot coefs
(point-parameters point)))
(rhs (point-value point)))
(lp:post<= lhs (lp:+ rhs diff))
(lp:post>= lhs (lp:- rhs diff))))
points)
(multiple-value-bind (status obj values)
(lp:solve)
(assert (eql status :optimal))
(values obj (map 'simple-vector
(lambda (var)
(gethash var values 0))
coefs))))))

With a fresh model in scope in which the goal is to minimise the objective function, a variable, diff, is created to represent the error term $$e$$, and one variable for each coefficient in the polynomial (coefs) list; each coefficient is unbounded both from below and above.

Then, for each point, the two corresponding constraints are added to the current model.

Finally, the model is solved, and a vector of optimal coefficients is extracted from the values hash table.

We can easily use solve-fit to exactly solve minimax instances with a couple thousands of points in seconds:

CL-USER> (let ((*dimension* 5) ; degree = 4
(*loc-value* (lambda (x)
(rational (exp (float x 1d0))))))
;; function to fit: EXP. Converting the argument to
;; a double-float avoid the implicit conversion to
;; single, and we translate the result into a rational
;; to avoid round-off
(solve-fit (loop for x from -1 upto 1 by 1/2048
;; create a point for x in
;; -1 ... -1/2048,0,1/2048, ... 1
collect (make-point x))))
dbl_solver: 0.510 sec 0.0 (optimal)      ; solve with doubles
ldbl_solver: 0.260 sec 0.0 (optimal)     ;   with long doubles
float128_solver: 0.160 sec 0.0 (optimal) ;   with 128 bit quads
mpf_solver: 1.110 sec 0.0 (optimal)      ;   with multi-precision floats
mpq_solver: 0.570 sec 0.0 (optimal)      ;   with rationals
3192106304786396545997180544707814405/5839213465929014357942937289929760178176
#(151103246476511404268507157826110201499879/151089648430913246511773502376932544610304
28253082057367857587607065964265169406677/28329309080796233720957531695674852114432
13800443618507633486386515045130833755/27665340899215071993122589546557472768
9582651302802548702442907342912775/54033868943779437486567557708120064
2329973989305264632365349185439/52767450140409606920476130574336)

Or, as more readable float values:

CL-USER> (values (float * 1d0) (map 'simple-vector (lambda (x)
(float x 1d0))
(second /)))
5.466671707434376d-4 ; (estimated) error bound
#(1.0000899998493569d0 0.997309252293765d0 0.49883511895923116d0
0.177345274179293d0 0.04415551600665573d0) ; coefficients

So, we have an approximation that’s very close to what LolRemez finds for $$\exp$$ and degree 4. However, we’re reporting a maximal error of 5.466672e-4, while LolRemez finds 5.466676e-4. Who’s wrong?

## Tightening the model

As is usually the case, we’re (slightly) wrong! The complete LP formulation has constraints for each possible argument $$x\in B$$. We only considered 4k equidistant such values in the example above. The model we solved is missing constraints: it is a relaxation. We’re solving that relaxation exactly, so the objective value it reports is a lower bound on the real error, and on the real optimal error. At least, we don’t have any design constraint, and the coefficients are usable directly.

We shall not settle for an approximate solution. We must simply add constraints to the model to make it closer to the real problem.

Obviously, adding constraints that are already satisfied by the optimal solution to the current relaxation won’t change anything. Adding constraints can only remove feasible solutions, and the current optimal solution remains feasible; since it was optimal before removing some candidates, it still is after.

So, we’re looking for constraints that are violated to add them to our current model. In the optimisation lingo, we’re doing constraint (or row, or cut) generation. In our problem, this means that we’re looking for points such that the error from the current approximation is greater than the estimate reported as our solution value. We’ll take a cue from the Remez algorithm and look for extremal violation points.

Extrema of differentiable functions are found where the first derivative is zero. Our approximation function is a polynomial and is trivially differentiated. We’ll assume that the user provides the derivative of the function to approximate. The (signed) error term is a difference of differentiable functions $$\tilde{f}-f$$, and its first derivative is simply the difference of the derivatives.

Assuming that the derivative is continuous, we can use the intermediate value theorem to find its roots: for each root, there is a (non-empty, open) neighbourhood such that the derivative is negative to the left of the root and positive to the right, or inversely.

This is what find-extrema.lisp implements. In optimisation-speak, that’s our separation algorithm: we use it to find (maximally-) violated constraints that we ought to add to our relaxation.

find-root takes a function, a lower bound, and an upper bound on the root, and first performs a bisection search until the range is down to 256 distinct double values. Then, the 256 values in the range are scanned linearly to find the minimal absolute value. I first tried to use Newton’s method, but it doesn’t play very well with rationals: although convergence is quick, denominators grow even more quickly. There are also potential issues with even slightly inexact derivatives. This is why the final step is a linear search. The method will work as long as we have correctly identified a tiny interval around the extremum; the interval can be explored exhaustively without involving the derivative.

%approximation-error-extrema finds candidate ranges. The sign of the derivative at each pair of consecutive points currently considered in the model is examined; when they differ, the range is passed to find-root. If we find a new extremum, it is pushed on a list. Once all the pairs have been examined, the maximal error is returned, along with the list of new extrema, and the maximal distance between new extrema and the corresponding bounds. As the method converges, extrema should be enclosed more and more tightly by points already considered in our constraints.

There are frequent calls to round-to-double: this function is used to take an arbitrary real, convert it to the closest double value, and convert that value back in a rational. The reason we do that is that we don’t want to generate constraints that correspond to values that cannot be represented as double floats: not only are they superfluous, but they also tend to have large denominators, and those really slow down the exact solver.

Finally, the two pieces are put together in driver.lisp. The constraints are initialised from 4096 equidistant points in the range over which we optimise. Then, for each iteration, the relaxation is solved, new extrema are found and added to the relaxation, until convergence. Convergence is easy to determine: when the error reported by the LP (the relaxation) over the constraint subset is the same as the actual error, we are done.

CL-USER> (time
;; muffle the simplex solver log
(find-approximation 4 -1 1
(lambda (x)
(rational (exp (float x 1d0))))
(lambda (x)
(rational (exp (float x 1d0)))))))
;  predicted error  actual       difference           log distance of new points
Iteration    1: 5.4666716e-4 5.466678e-4 [6.5808034e-10] (4 new extrema, delta 40.42 bit)
Iteration    2: 5.4666746e-4 5.4666775e-4 [3.25096e-10] (4 new extrema, delta 41.15 bit)
Iteration    3: 5.466676e-4 5.466677e-4 [9.041601e-11] (4 new extrema, delta 40.89 bit)
Iteration    4: 5.4666764e-4 5.4666764e-4 [2.4131829e-11] (4 new extrema, delta 38.30 bit)
Iteration    5: 5.4666764e-4 5.4666764e-4 [5.3669834e-12] (4 new extrema, delta 39.04 bit)
Iteration    6: 5.4666764e-4 5.4666764e-4 [2.1303722e-12] (4 new extrema, delta 36.46 bit)
Iteration    7: 5.4666764e-4 5.4666764e-4 [8.5113746e-13] (4 new extrema, delta 37.19 bit)
Iteration    8: 5.4666764e-4 5.4666764e-4 [5.92861e-14] (4 new extrema, delta 36.93 bit)
Iteration    9: 5.4666764e-4 5.4666764e-4 [8.7291163e-14] (4 new extrema, delta 34.34 bit)
Iteration   10: 5.4666764e-4 5.4666764e-4 [2.7814624e-14] (4 new extrema, delta 35.08 bit)
Iteration   11: 5.4666764e-4 5.4666764e-4 [1.22935355e-14] (4 new extrema, delta 33.82 bit)
Iteration   12: 5.4666764e-4 5.4666764e-4 [6.363092e-15] (4 new extrema, delta 34.56 bit)
Iteration   13: 5.4666764e-4 5.4666764e-4 [2.6976767e-15] (4 new extrema, delta 31.97 bit)
Iteration   14: 5.4666764e-4 5.4666764e-4 [6.2273127e-16] (4 new extrema, delta 31.71 bit)
Iteration   15: 5.4666764e-4 5.4666764e-4 [3.1716093e-16] (4 new extrema, delta 32.44 bit)
Iteration   16: 5.4666764e-4 5.4666764e-4 [8.9307225e-17] (4 new extrema, delta 29.86 bit)
Iteration   17: 5.4666764e-4 5.4666764e-4 [2.986885e-17] (4 new extrema, delta 29.60 bit)
Iteration   18: 5.4666764e-4 5.4666764e-4 [8.047477e-17] (4 new extrema, delta 30.33 bit)
Iteration   19: 5.4666764e-4 5.4666764e-4 [0.0e+0] (4 new extrema, delta 27.75 bit)
Evaluation took:
153.919 seconds of real time    ; includes time spent in the LP solvers
43.669636 seconds of total run time (39.078488 user, 4.591148 system)
[ Run times consist of 2.248 seconds GC time, and 41.422 seconds non-GC time. ]
28.37% CPU
245,610,372,128 processor cycles
4,561,238,704 bytes consed

4046879766238553594956027226378928284211150354828640757733860080712233114910799/7402816194767429570294393430906636383377554724586974324818463099198772886301048832
#(925435306122623901577988826638313570454904960173764226165130358296546098660735739/925352024345928696286799178863329547922194340573371790602307887399846610787631104
6557329860867414742326673804552068829044003331586895788335382835917/6575021589199030076761681434499916661609079970484769650357093605918
1639925832159462899796569909691517124754835951733786891469617405863/3287510794599515038380840717249958330804539985242384825178546802959
583024503858777554811473359621837746265838166280012537010086877260/3287510794599515038380840717249958330804539985242384825178546802959
145161740826348143502214435074903924097159484388538508594721873208/3287510794599515038380840717249958330804539985242384825178546802959)

Note that we found new extrema in the last iteration. However, the error for those extrema wasn’t actually larger than for the points we were already considering, so the solution was still feasible and optimal.

The fractions will be more readable in floats:

CL-USER> (values (float * 1d0) (map 'simple-vector
(lambda (x) (float x 1d0))
(second /)))
5.466676005138464d-4
#(1.0000900001021278d0 0.9973092516744465d0 0.4988351170902357d0
0.177345274368841d0 0.044155517622880315d0)

Now, we have nearly exactly (up to a couple bits) the same values as LolRemez’s example. Each iteration takes less than 10 seconds to execute; we could easily initialise the relaxation with even more than 4096 points. We should expect the impact on the solution time to be cubic: most of the simplex iterations take place in the floating point solvers, and the number of iterations is usually linear in the number of variables and constraints, but the constraint matrix is dense so the complexity of each iteration should grow almost quadratically. What really slows down the rational solver isn’t the number of variables or constraints, but the size of the fractions. On the other hand, we see that some of the points considered by our constraints differ by $$\approx 30$$ bit in their double representation: we would need a very fine grid (and very many points) to hit that.

In addition to being more easily generalised than the Remez algorithm, the LP minimax has no convergence issue: we will always observe monotone progress in the quality of the approximation and, except for potential issues with the separation algorithm, we could use the approach on any function. There is however (in theory, at least) a gaping hole in the program: however improbable, all the extrema could be sandwiched between two points for which the derivative has the same sign. In that case, the program will finish (there are no constraint to adjoin), but report the issue. A finer initial grid would be one workaround. A better solution would be to use a more robust root-finding algorithm.

## What’s next?

The minimax polynomial fitting code is on github, as a demo for the rational-simplex system. The code can easily be adapted to any other basis (e.g. the Fourier basis), as long as the coefficients are used linearly.

In the next instalment, I plan to use the cut (constraint) generation algorithm we developed here in a branch-and-cut algorithm. The new algorithm will let us handle side-constraints on the coefficients: e.g., fix as many as possible to zero, 1, -1 or other easy multipliers.

If you found the diversion in Linear programming and cut generation interesting, that makes be very happy! One of my great hopes is to see programmers, particularly compiler writers, better exploit the work we do in mathematical optimisation. Sure, “good enough” is nice, but wouldn’t it be better to have solutions that are provably optimal or within a few percent of optimal?

If you want more of that stuff, I find that Chvatal’s book Linear Programming is a very nice presentation of linear programming from both the usage and implementation points of view; in particular, it avoids the trap of simplex tableaux, and directly exposes the meaning of the operations (its presentation also happens to be closer to the way real solvers work). Works like Wolsey’s Integer Programming build on the foundation of straight linear programs to tackle more complex problems, and introduce techniques we will use (or have used) here, like branch-and-bound or cut generation. The classic undergraduate-level text on operations research seems to be Hillier and Lieberman’s Introduction to operations research (I used it, and so did my father nearly 40 years ago)… I’m not sure that I’m a fan though.

May 24th, 2012
In categories: Approximation


text:
Hi all,

I am setting up a test with several MC questions and a few numeric questions
I am trying to use AMCnumericChoices but I don't want to print the numeric tests
on the answer sheet of the MC questions. Is this possible? At the moment the box for the numeric
choice appear inside the columns of the separate answer sheet and I can't use it.

Raffaele

### Replies (9)

#### RE: AMCnuericChoices and answer sheets - Added by Alexis Bienvenüeover 8 years ago

If I understand well, you need to print (on the separate answer sheet) together the answers for numeric choices in one column, and the others in two columns?
This is not yet possible, but it is in my TODO list... Added #272

#### RE: AMCnuericChoices and answer sheets - Added by Raffaele Borrelliover 8 years ago

No, not really. What I meant is that sometimes one need to use a separate answer sheet for a set of questions (mainly for MC questions),
but in the same test it would be better to have numeric questions written normally and not with a separate answer sheet.
Something like using the option for a separate answer sheet only for the MCQ section of the test.
Is this possible?

#### RE: AMCnuericChoices and answer sheets - Added by Alexis Bienvenüeover 8 years ago

You can add question in your test that are not taken into account for the MCQ part: just don't use the question environment, but instead print the questions you want with \par, \bf and so on…

#### RE: AMCnuericChoices and answer sheets - Added by Raffaele Borrelliover 8 years ago

I am trying to do that, but if I write a question inside one copy using, for example

\FPeval\VQa{trunc(random*15/10,2)}  \FPeval\VQs{(VQa/10)}  Calculate $\VQa/10$  \AMCnumericChoices{\VQs}{digits=3,decimals=2,borderwidth=2pt,backgroundcol=lightgray,approx=5}AMCnumericChoices{\VQs}{digits=3,decimals=2,borderwidth=2pt,backgroundcol=lightgray,approx=5}

I don't get any numeric box.

#### RE: AMCnuericChoices and answer sheets - Added by Alexis Bienvenüeover 8 years ago

\AMCnumericChoices can only be used inside a question-like environment. I'm afraid I don't understand what you need exactly: can you provide an example?

#### RE: AMCnuericChoices and answer sheets - Added by Raffaele Borrelliover 8 years ago

I am attaching two files (the tex source and the final pdf). As you can see the numeric boxes are not displayed.
I'd like to have numeric boxes just below the last question.

#### RE: AMCnuericChoices and answer sheets - Added by Raffaele Borrelliover 8 years ago

Hi, is the problem clearer? I just need to append some numeric questions after the answer sheet.
Is there any possibility to do that?

#### RE: AMCnuericChoices and answer sheets - Added by Alexis Bienvenüeover 8 years ago

Perhaps with some kind of hack...
I am not sure if the following works: please test it extensively before using it.

\makeatletter
\def\AMCcloseForm{\AMC@zoneformulairefalse\AMC@ensemblefalse}
\makeatother

Then enclose your Part II block along with this new command:
{\AMCcloseForm

\begin{center}
{\bf Parte II} \\
{\bf Domande a risposta libera}
\end{center}
\vspace{3em}

\begin{questionmultx}{prova}
\FPeval\VQa{trunc(random*15/10,2)}
\FPeval\VQs{(VQa/10)}
Calcolare $\VQa/10$.
\AMCnumericChoices{\VQs}{digits=3,decimals=2,borderwidth=2pt,backgroundcol=lightgray,approx=5}
\end{questionmultx}
}

#### RE: AMCnuericChoices and answer sheets - Added by Raffaele Borrelliover 8 years ago

Hi,
thank you very much for your help. AMC recognise the sheet with numeric answers
as part of the answer sheet, so its is printed in the answer sheet file.
I have tried to produce a pdf files and then annotate them and
the system seems to work fine. The correction is good. Only the annotation does not
seem to work. It produces the annotated file but this latter does not contain the
annotation on original paper but only the file with the correct answers.
In a couple of weeks I'll have it testes on a few hundred students...let's cross fingers.

(1-9/9)


text:
# Micromass' big statistics challenge

• Challenge
Staff Emeritus
Homework Helper
If we're having a thread about probability theory, then we must have one on statistics too! The following questions are all very open-ended and thus multiple answers may seem possible. Your goal is to find a strategy to find the answer to the questions. Furthermore, you must provide some kind of reasoning as to why your strategy is a decent one.

• For an answer to count, not only the answer must be given but also a detailed strategy. An explanation of why the strategy is plausible must be given. Don't forget the detail the model you're working with and why this model is plausible.
• Any use of outside sources is allowed, but do not look up the question directly. For example, it is ok to go check probability books, but it is not allowed to google the exact question.
• If you previously encountered this statement and remember the solution, then you cannot participate in this particular statement.
• All mathematical methods are allowed.
• Please reference every source you use.
• What I feel are the best answers will be awarded on this original post. If you think you came up with a better answer, you must prove your answer is better.
Here you go:

1. SOLVED BY mfbEvery day there is one train between Mordor and Rohan. These are the number of people who want to take the train on one day:

Day 1: 233
Day 2: 231
Day 3: 254
Day 4: 212
Day 5: 202

Find the optimal number of seats in the train.

2. Take the following two sequences of coin tosses:

Code:
THHHHTTTTHHHHTHHHHHHHHTTTHHTTHHHHHTTTTTTHHTHHTHHHTTTHTTHHHHTHTTHTTTHHTTTTHHHHHHTTTHHTTHHHTHHHHHTTTTTHTTTHHTTHTTHHTTTHHTTTHHTHHTHHTTTTTHHTHHHHHHTHTHTTHTHTTHHHTTHHTHTHHHHHHHHTTHTTHHHTHHTTHTTTTTTHHHTHHH

Code:
THTHTTTHTTTTHTHTTTHTTHHHTHHTHTHTHTTTTHHTTHHTTHHHTHHHTTHHHTTTHHHTHHHHTTTHTHTHHHHTHTTTHHHTHHTHTTTHTHHHTHHHHTTHTHHTHHHTTTHTHHHTHHTTTHHHTTTTHHHTHTHHHHTHTTHHTTTTHTHTHTTHTHHTTHTTTHTTTTHHHHTHTHHHTTHHHHHTHHH

One of these sequences is from an actual coin toss experiment. The other is invented by a human. Find out which of these is which.

3. SOLVED BY Math_QED I want to estimate the number of fish in a lake. I catch 400 fish and given them all a red dot. I throw them back in the lake. Then I catch 400 fish again. I note that 100 of them have a red dot. How many fish are there in the lake?

4. SOLVED BY Ygggdrasil, mfb Unstable particles are emitted from a source and decay at a distance ##x##, a real number that has an exponential distribution with characteristic length ##\lambda##. Decay events can be observed only if they occur in a window extending from ##x=1## to ##x=20##. We observe ##6## decays at locations ##\{2,5,12,13,13,16\}##. What is ##\lambda##?

5. SOLVED BY mrspeedybob, PeroK I have a big box filled with balls. All balls have a number. I draw ##5## balls at random and record their number. They are: ##10##, ##50##, ##104##, ##130##, ##213##. How many balls do you expect to be in the box?

6. I claim I can tell the difference between coca cola and pepsi cola better than just guessing. Somebody pours 5 cups of pepsi and 5 cups of coca cola and hands them to me. I tell them which cup is which. It turns out I judged correctly 8 of the 10 cups. Do you believe my original claim?

7. SOLVED BY MarneMath A professor got a ticket twelve times for illegal overnight parking. All twelve tickets were given either Tuesdays or Thursdays. Is it justified for him to rent a garage on these days?

8. SOLVED BY QuantumQuest In a certain family, four girls take turns at washing dishes. There were four breakages. Three of them were caused by the youngest girl. Is it justified to call her clumsy?

9. SOLVED BY fresh_42 Given the following encoded text, find out whether this is a real text or randomly generated using some scheme. Attempting to decode the text doesn't count.

Code:
sedwhqjkbqjyedi oek xqlu tusetut jxyi junj jxqj mqi dej fqhj ev jxu fherbuc jxekwx ie oek wuj de feydji jxu vebbemydw yi qd unsuhfj vhec myayfutyq fherqrybyjo yi jxu cuqikhu ev jxu byaubyxeet jxqj qd uludj mybb esskh fherqrybyjo yi gkqdjyvyut qi q dkcruh rujmuud puhe qdt edu mxuhu puhe ydtysqjui ycfeiiyrybyjo qdt edu ydtysqjui suhjqydjo jxu xywxuh jxu fherqrybyjo ev qd uludj jxu cehu suhjqyd mu qhu jxqj jxu uludj mybb esskh q iycfbu unqcfbu yi jxu jeiiydw ev q vqyh kdryqiut seyd iydsu jxu seyd yi kdryqiut jxu jme ekjsecui xuqt qdt jqyb qhu ugkqbbo fherqrbu jxu fherqrybyjo ev xuqt ugkqbi jxu fherqrybyjo ev jqyb iydsu de ejxuh ekjsecu yi feiiyrbu jxu fherqrybyjo yi edu xqbv eh vyvjo fuhsudj ev uyjxuh xuqt eh jqyb yd ejxuh mehti jxu fherqrybyjo ev xuqt yi edu ekj ev jme ekjsecui qdt jxu fherqrybyjo ev jqyb yi qbie edu ekj ev jme ekjsecui jxuiu sedsufji xqlu ruud wylud qd qnyecqjys cqjxucqjysqb vehcqbypqjyed yd fherqrybyjo jxueho iuu fherqrybyjo qnyeci mxysx yi kiut mytubo yd iksx qhuqi ev ijkto qi cqjxucqjysi ijqjyijysi vydqdsu wqcrbydw isyudsu yd fqhjyskbqh fxoiysi qhjyvysyqb ydjubbywudsu cqsxydu buqhdydw secfkjuh isyudsu wqcu jxueho qdt fxybeiefxo je veh unqcfbu thqm ydvuhudsui qrekj jxu unfusjut vhugkudso ev uludji fherqrybyjo jxueho yi qbie kiut je tuishyru jxu kdtuhboydw cusxqdysi qdt huwkbqhyjyui ev secfbun ioijuci

10. SOLVED BY jbriggs444 A person is playing a game operated by a psychic, an entity presented as somehow being exceptionally skilled at predicting people's actions. It is known that the Psychic predicts people's actions correctly in approximately 99.9% of the cases. The player of the game is presented with two boxes, one transparent (labeled A) and the other opaque (labeled B). The player is permitted to take the contents of both boxes, or just the opaque box B. Box A contains a visible $1,000. The contents of box B, however, are determined as follows: At some point before the start of the game, the Psychic makes a prediction as to whether the player of the game will take just box B, or both boxes. If the Psychic predicts that both boxes will be taken, then box B will contain nothing. If the Psychic predicts that only box B will be taken, then box B will contain$1,000,000.

If the psychic predicts that the player will choose randomly, then box B will contain nothing.

By the time the game begins, and the player is called upon to choose which boxes to take, the prediction has already been made, and the contents of box B have already been determined. That is, box B contains either $0 or$1,000,000 before the game begins, and once the game begins even the Psychic is powerless to change the contents of the boxes. Before the game begins, the player is aware of all the rules of the game, including the two possible contents of box B, the fact that its contents are based on the Psychic's prediction, and knowledge of the Psychic's infallibility. The only information withheld from the player is what prediction the Psychic made, and thus what the contents of box B are.[/COLOR]

Thank you all for participating! I hope many of you have fun with this! Don't hesitate to post any feedback in the thread!

1. Invented myself
2. gato-docs.its.txstate.edu/mathworks/DistributionOfLongestRun.pdf
3. Feller "An introduction to probability theory and its applications Vol1" Chapter II "Elements of Combinatorial analysis"
4. MacKay "Information Theory, Inference and Learning algorithms" http://www.inference.phy.cam.ac.uk/itila/p0.html
5. http://www.math.uah.edu/stat/urn/OrderStatistics.html
6. https://en.wikipedia.org/wiki/Fisher's_exact_test
7. Feller "An introduction to probability theory and its applications Vol1" Chapter II "Elements of Combinatorial analysis"
8. Feller "An introduction to probability theory and its applications Vol1" Chapter II "Elements of Combinatorial analysis"

Last edited:

fresh_42
Mentor
2021 Award
2. The ##χ^2##-Test on the outcome gave me no informations. Therefore I considered the changes as random variable. For a fair coin the chances are ##50:50## to change or not. That costed only one observation, but ##198## are still fine.
The first sequence resulted in ##χ^2 = 6.5## which corresponds to an almost ##99\%## chance for not being random whereas the second got me ##0.3##, i.e. no statement about randomness by the ##χ^2##-Test can be made. So if I had no cut and paste errors, my answer is: The first sequence is hand made.

member 587159
4) If n is the total amount of fish

400/n must be equal to 100/400, therefor n = 1600. This is because you take 400 fish from the population randomly (uniformly distributed) and then you find 100 fish out of 400 that have been marked (again uniformly distributed). If you give more information about the liability I can give an interval.

fresh_42
Mentor
2021 Award
9. Just to make sure: You didn't give us a part of the Voynich manuscript, didn't you?

Edit:
I have taken the source text which is of 1342 bytes length and compressed it to 718 bytes.
Then I randomly choose texts of equal length (1342 bytes) from:
1. New York Times → compressed 816 bytes
2. Washington Post → compressed 817 bytes
3. San Francisco Chronicle → compressed 820 bytes
4. a Danish tourist site → compressed 810 bytes
5. Helsingin Sanomat (Finnish newspaper) → compressed 804 bytes
6. El País (Madrid) → compressed 882 bytes
The Spanish have had the longest sentences, too. Although I changed languages and content, the compressed files were all around 820 bytes long, except one which was longer. But none came even near the 718 bytes, so I didn't make any statistical test. My result: The text is likely artificial.

Last edited:
Staff Emeritus
Homework Helper
2. The ##χ^2##-Test on the outcome gave me no informations. Therefore I considered the changes as random variable. For a fair coin the chances are ##50:50## to change or not. That costed only one observation, but ##198## are still fine.
The first sequence resulted in ##χ^2 = 6.5## which corresponds to an almost ##99\%## chance for not being random whereas the second got me ##0.3##, i.e. no statement about randomness by the ##χ^2##-Test can be made. So if I had no cut and paste errors, my answer is: The first sequence is hand made.

That's interesting. I'll wait for some further analyses possibly by you or by others.

Staff Emeritus
Homework Helper
4) If n is the total amount of fish

400/n must be equal to 100/400, therefor n = 1600. This is because you take 400 fish from the population randomly (uniformly distributed) and then you find 100 fish out of 400 that have been marked (again uniformly distributed). If you give more information about the liability I can give an interval.

Very good. I will mark this as the correct answer.

Staff Emeritus
Homework Helper
9. Just to make sure: You didn't give us a part of the Voynich manuscript, didn't you?

Edit:
I have taken the source text which is of 1342 bytes length and compressed it to 718 bytes.
Then I randomly choose texts of equal length (1342 bytes) from:
1. New York Times → compressed 816 bytes
2. Washington Post → compressed 817 bytes
3. San Francisco Chronicle → compressed 820 bytes
4. a Danish tourist site → compressed 810 bytes
5. Helsingin Sanomat (Finnish newspaper) → compressed 804 bytes
6. El País (Madrid) → compressed 882 bytes
The Spanish have had the longest sentences, too. Although I changed languages and content, the compressed files were all around 820 bytes long, except one which was longer. But none came even near the 718 bytes, so I didn't make any statistical test. My result: The text is likely artificial.

That's an interesting analysis. I'll be waiting for more input before I spill the beans on this one.

Staff Emeritus
Homework Helper
9. Just to make sure: You didn't give us a part of the Voynich manuscript, didn't you?

Don't worry, there is a definite answer.

fresh_42
Mentor
2021 Award
That's interesting. I'll wait for some further analyses possibly by you or by others.
I've reviewed it. At a significance level of 2% then ##χ^2 = 6.5 > χ_{(98\%;1)}^2## and the null hypotheses (randomness with a fair coin) should be rejected. I have never trusted this test anyway ... or your coin.

member 587159
6) Define the stochast X "Correct guesses".
X ~ B(10,1/2)

We want to know how large the probability is that someone gives 8 correct guesses out of 10, when he has 1/2 chance of guessing correctly. We can do this using P-values:

Our zero-hypothesis H0: p = 1/2
The alternative hypothesis Ha (this is the claim): Ha: p>1/2

P-value = 1 - Binomcdf(10,1/2,7) = 0,0547.

The chance of getting 8 out of 10 correct guesses with 1/2 chance is 0,0547 or 5,47%. This is a rather small percentage. Therefor, we conclude that supposedly H0 is wrong and we say that Ha is better. So I would say that we believe his claim, since 5,47% chance is not that large.

PeroK
Homework Helper
Gold Member
2021 Award
For number 2:

I would say that the first sequence is human generated. Two reasons: First, the probability of getting another H after an H and a T after a T seems too high (for heads it's 67/107 and tails 51/92 by my counting). Second, there appear to be too many long sequences of Heads and too few Head singletons.

My guess is that this is someone trying to avoid too much HTHT and over-compensating. The giveaway, supposedly, for human generated sequences is too few long sequences of H and T. This looks like someone who knew this and over-compensated.

The second sequence appears to have a more normal correlation of H following H and T following T. The anomalies looks more believable.

I know too little statistics to analyse it any deeper.

Staff Emeritus
Homework Helper
6) Define the stochast X "Correct guesses".
X ~ B(10,1/2)

We want to know how large the probability is that someone gives 8 correct guesses out of 10, when he has 1/2 chance of guessing correctly. We can do this using P-values:

Our zero-hypothesis H0: p = 1/2
The alternative hypothesis Ha (this is the claim): Ha: p>1/2

P-value = 1 - Binomcdf(10,1/2,7) = 0,0547.

The chance of getting 8 out of 10 correct guesses with 1/2 chance is 0,0547 or 5,47%. This is a rather small percentage. Therefor, we conclude that supposedly H0 is wrong and we say that Ha is better. So I would say that we believe his claim, since 5,47% chance is not that large.

Two remarks:
1) Does it change anything if I knew beforehand that 5 cups would be pepsi and 5 would be coca cola? I believe this changes something, for example guessing correctly 9 out of 10 is then impossible.
2) You took the probability of guessing correctly 8 out of 10. But for the p-value, shouldn't you take the probability of guessing correctly 8 out of 10, and 9out of 10 and 10 out of 10?

member 587159
Staff Emeritus
Homework Helper
For number 2:

I would say that the first sequence is human generated. Two reasons: First, the probability of getting another H after an H and a T after a T seems too high (for heads it's 67/107 and tails 51/92 by my counting). Second, there appear to be too many long sequences of Heads and too few Head singletons.

My guess is that this is someone trying to avoid too much HTHT and over-compensating. The giveaway, supposedly, for human generated sequences is too few long sequences of H and T. This looks like someone who knew this and over-compensated.

The second sequence appears to have a more normal correlation of H following H and T following T. The anomalies looks more believable.

I know too little statistics to analyse it any deeper.

You gave such a neat solution to the "runs" question on the probability thread. Can you figure out the number of runs of order ##n## for each ##n## in a totally random sequence and compare it with what we have?

member 587159
Two remarks:
1) Does it change anything if I knew beforehand that 5 cups would be pepsi and 5 would be coca cola? I believe this changes something, for example guessing correctly 9 out of 10 is then impossible.
2) You took the probability of guessing correctly 8 out of 10. But for the p-value, shouldn't you take the probability of guessing correctly 8 out of 10, and 9out of 10 and 10 out of 10?

I did calculate for 8 out of 10, 9 out of 10, and 10 out of 10. It's BinomCDF, I do not know whether you know this but it is a command on the graphing calculator. But in fact I calculated this. I need to think about the first remark though, since I am out of time now. I will look at it soon. Intuitively, I would say that I would have to calculate the chances for 8 out of 10 and 10 out of 10 and then add them together. This might give the correct probability. A quick calculation gives then 0,0439 and this means there is even a better chance that his claim is true. But I might be missing something.

Staff Emeritus
Homework Helper
I did calculate for 8 out of 10, 9 out of 10, and 10 out of 10. It's BinomCDF, I do not know whether you know this but it is a command on the graphing calculator. But in fact I calculated this.

Oh ok. Good to know this!

member 587159
I edited my last post.

For number two (coinflips): Pick a random family of correlation functions e.g. ##\langle x_n, x_n+2 ,x_n+10\rangle##, with 'family' I mean n goes through all coinflips, where periodic boundary conditions are assumed.

The 'family' with the highest shannon-entropy will be the real one.

Last edited:
#5
I would expect the ball numbers (on average) to be evenly spaced through the range of possible ball numbers. The highest ball in this particular question is 213, so the average spacing between the numbers is 213/5. The total number of possible balls should include 1 average space above the highest ball, so that would make the most likely number of balls (6*213)/5, or 255.6.
Since I can't have .6 balls, I believe it's appropriate to round to the nearest integer (no pun intended), so my answer is 256.

PeroK
Homework Helper
Gold Member
2021 Award
You gave such a neat solution to the "runs" question on the probability thread. Can you figure out the number of runs of order ##n## for each ##n## in a totally random sequence and compare it with what we have?

What I get for the first sequence for runs of H is:

##0 \ - \ 51; \ \ 1 \ - \ 12^*; \ \ 2 \ - \ 15; \ \ 3 \ - \ 6; \ \ 4 \ - \ 3; \ \ 5 \ - \ 1; \ \ 6 \ - \ 2; \ \ 8 \ - \ 2^*##

And for the second sequence;

##0 \ - \ 43; \ \ 1 \ - \ 25; \ \ 2 \ - \ 8^*; \ \ 3 \ - \ 13^*; \ \ 4 \ - \ 5; \ \ 5 \ - \ 1##

And, you would expect (on average) using 96 games as a nice number:

##0 \ - \ 48; \ \ 1 \ - \ 24; \ \ 2 \ - \ 12; \ \ 3 \ - \ 6; \ \ 4 \ - \ 3; \ \ 5 \ - \ 1.5; \ \ 6 \ - \ 0.75; \ \ 8 \ - \ 0.19##

The ones marked * are the main anomalies. The second pair of anomalies looks more plausible.

The probability of getting 12 or fewer H singletons is about ##0.002## and getting 2 or more runs of 8 or more about ##0.02##.

Whereas, the probability of getting precisely 8 and 13 for runs of 2 and 3 is ##0.06## and ##0.003## respectively. This is more likely to be the random sequence.

Last edited:
jbriggs444
Homework Helper
10) Does not ask a question. The obvious question is what one should choose and why. Or, better, what strategy one should adopt and why.

The key difficulty is the problem of self-reference. The situation we are faced with depends on the decision process we (will) choose to deal with it. A decision process which is guaranteed to yield an optimal result for a fixed situation is not guaranteed to yield an optimal result when the situation depends on the choice of decision process.

The problem statement attempts to disguise the self-reference by combining the use of a psychic (whose behavior depends on future choices) with the notion of a fixed and immutable past (which cannot depend on the future choices).

In order to remove the problem of self-reference, re-cast the problem as a two player non-zero sum game where we play against our twin. Each player has two choices, "cooperate" or "defect". The payoff matrix is:

Code:
row  Us     Twin     Result for us
1 coop    coop     1,000,000
2 coop    defect           0
3 defect  coop     1,001,000
4 defect  defect        1000

The problem has been constructed to make mixed (aka random) strategies untenable. We can discard any such approaches out of hand.

If the psychic predictor were 100% accurate, our clone will make (or will have made) the same choice that we will. The relevant question is "what strategy, if adopted by both payers, will result in the highest average payout for us?" The relevant rows are 1 and 4 and a strategy of "cooperate" is optimal.

Since the psychic predictor is only 99.9% accurate, the effect is that 99.9% of the time we will be playing our twin, but 0.1% of the time we will instead be playing our evil step brother who always does the opposite. This time a choice of cooperate is now 99.9% likely to hit row 1 and 0.1% likely to hit row 2 for an average payout of $999,000. A strategy of defect is 0.1% likely to hit row 3 and 99.9% likely to hit row 4 for an average payout of$2009. A strategy of "cooperate" is still optimal.

PeroK
Homework Helper
Gold Member
2021 Award
Number 5:

I'll take a wild guess at ##282.5##. If that's close I can post later how I arrived at it!

Staff Emeritus
Homework Helper
#5
I would expect the ball numbers (on average) to be evenly spaced through the range of possible ball numbers. The highest ball in this particular question is 213, so the average spacing between the numbers is 213/5. The total number of possible balls should include 1 average space above the highest ball, so that would make the most likely number of balls (6*213)/5, or 255.6.
Since I can't have .6 balls, I believe it's appropriate to round to the nearest integer (no pun intended), so my answer is 256.

Number 5:

I'll take a wild guess at ##282.5##. If that's close I can post later how I arrived at it!

It's close, but mrspeedybob seems to be a lot closer, I believe he missed something essential though. I'm still very interested in seeing your method, so I would be very grateful if you would post it.

PeroK
Homework Helper
Gold Member
2021 Award
Number 5:

First, my interpretation of the problem. You pick a number ##n## at random with equal likelihood from ##1## to some large number ##N##. You put that many numbered balls in the bag and draw out ##5##. The event ##X##, as described, with a highest of ##213## is observed. What is the expected value of ##n##, given event ##X##?

Note that it doesn't matter whether the event ##X## represents the order the balls came out or rearranged in order of magnitude: the calculations all differ only by a factor of ##5## throughout, which cancels out. Assume the former. Also assume that event ##X## is ball ##213## plus any four others smaller. Assuming the precise numbers in the problem will also cancel out and give the same answer.

##n## must be at least ##213##. Let ##p(X_{n})## be the probability of event ##X## given ##n##.

##p(X_{213}) = \frac{1}{213}##

##p(X_{214}) = \frac{1}{214} \times \frac{212}{213} \times \frac{211}{212} \times \frac{210}{211} \times \frac{209}{210}= \frac{1}{214} \times \frac{209}{213}##

In general:

##p(X_{n}) = \frac{1}{n} \times F_{n} = \frac{1}{n} \times \frac{n-5}{n-1} \times F_{n-1}## where ##F_{213} = 1, F_{214} = \frac{209}{213} \dots##

And:

##p(X) = \frac{1}{N - 212} \sum_{n = 213}^{N} p(X_{n})##

Now, we have:

##p(n \ / \ X) = \frac{p(X_n) p(n)}{p(X)} = \frac{p(X_n)}{(N-212) p(X)}##

And

##E(n) = \sum_{n = 213}^{N} n \frac{p(X_n)}{(N-212)p(X)} = \frac{1}{(N-212) p(X)} \sum_{n = 213}^{N} n {p(X_n)} = \frac{1}{(N-212)p(X)} (\sum_{n = 213}^{N} F_{n})##

##E(n) = \frac{\sum_{n = 213}^{N} F_{n}}{\sum_{n = 213}^{N} \frac{F_{n}}{n}}##

At this point I just put ##N = 3000## into a calculation and got:

##(N-212)p(X) = 0.25## and ##E(n) = 282.6##

Last edited:
Samy_A
Staff Emeritus
Homework Helper
Very impressive approach PeroK. You essentially used a Bayesian approach to this question. I like your solution a lot. I will wait a bit for other inputs, but you'll definitely get some of the credit for this problem.

PeroK
PeroK
Homework Helper
Gold Member
2021 Award
Very impressive approach PeroK. You essentially used a Bayesian approach to this question. I like your solution a lot. I will wait a bit for other inputs, but you'll definitely get some of the credit for this problem.

It appears that:

##\sum_{n = k}^{\infty} \frac{F_{n}}{n} = \frac{1}{r-1}## where ##k## is the highest number picked and ##r## is the number of balls picked.

So:

##E(n) = (r-1)\sum_{n = k}^{\infty} F_{n}##

Where ##F_k = 1, \ F_n = \frac{n-r}{n-1}F_{n-1}##

Not that far from a formula now!

PeroK
Homework Helper
Gold Member
2021 Award
It also appears that:

##\sum_{n = k}^{\infty} F_{n} = \frac{k}{r-2}##

So:

##E(n) = \frac{k(r-1)}{r-2}##

E.g. ##k = 213, r = 5, E(n) = 284##

Staff Emeritus
Homework Helper
How did you find these formulas?

PeroK
Homework Helper
Gold Member
2021 Award
How did you find these formulas?

Just computationally. Looking at them analytically now.

For number two (coinflips): Pick a random family of correlation functions e.g. ##\langle x_n, x_n+2 ,x_n+10\rangle##, with 'family' I mean n goes through all coinflips, where periodic boundary conditions are assumed.

The 'family' with the highest shannon-entropy will be the real one.

I tried this for a few families: I made for example a list {n,n+30} from n from 0 to L(the length) and calculated the entropy of the list of couples. But the difference in entropy is always in the third significant number and which chain has the highest entropy is not the same for all chosen 'families' of tupels. It may be that an averaging over all possible families will give a definite result. I don't have the time to check that for now, if someone else wants to try this, feel free to do so. But if that works, it probably wouldn't be the most elegant way to solve this problem.

EDIT: with a bit more careful look I also think the first one is hand-made, it seems to have slightly lower entropies between nearby levels especially, which is consistent with a human having a 'short time memory'.

Last edited:
member 587159
6)

Define the stochast X "correct guesses". X can take any value, except 9 (if you have given 9 correct values, then the 10th is automatically correct too since you know there are 5 pepsi's and 5 regular cola's). Thus, in fact, 9 guesses are enough to know what we want to know.

We now see: X~B(9,1/2)

Zero-hypothesis: H0: p = 1/2
Alternative hypothesis (claim): Ha: p>1/2
x observed: 8

Using P values we get:

P-value = P(X>=8) = C(8,9)(1/2)^8*(1/2) + C(9,9)(1/2)^9 = 0,0195..

This means that the probability of someone guessing 8 out of 10 correctly (using H0), is 0,0195. This is a rather small probability. Therefor, I say that his claim is true.


text:
Corpus ID: 235458668

# Sturm-Liouville Theory and Decay Parameter for Quadratic Markov Branching Processes

@inproceedings{Chen2020SturmLiouvilleTA,
title={Sturm-Liouville Theory and Decay Parameter for Quadratic Markov Branching Processes},
author={Anyue Chen and Yong Chen and W. Gao and Xiaohan Wu},
year={2020}
}
For a quadratic Markov branching process (QMBP), we show that the decay parameter is equal to the first eigenvalue of a Sturm-Liouville operator associated with the PDE that the generating function of the transition probability satisfies. The proof is based on the spectral properties of the Sturm-Liouville operator. Both the upper and lower bounds of the decay parameter are given explicitly by means of a version of Hardy inequality. Two examples are provided to illustrate our results. The… Expand

#### References

SHOWING 1-10 OF 16 REFERENCES
Speed of stability for birth-death processes
This paper is a continuation of the study on the stability speed for Markov processes. It extends the previous study of the ergodic convergence speed to the non-ergodic one, in which the processesExpand
Spectral Theory and Differential Operators
• Mathematics
• 1987
Linear operations in Banach spaces Entropy numbers, s-numbers, and eigenvalues Unbounded linear operators Sesquilinear forms in Hilbert spaces Sobolev spaces Generalized Dirichlet and NeumannExpand
Weak convergence of conditioned processes on a countable state space
• Mathematics
• 1995
We consider the problem of conditioning a continuous-time Markov chain (on a countably infinite state space) not to hit an absorbing barrier before time T ; and the weak convergence of thisExpand
Quasi-stationary distributions for discrete-state models
• Mathematics, Computer Science
• Eur. J. Oper. Res.
• 2013
This paper contains a survey of results related to quasi-stationary distributions, which arise in the setting of stochastic dynamical systems that eventually evanesce, and which may be useful inExpand
The Generating Function Method for Quadratic Asymptotically Symmetric Birth and Death Processes
• Mathematics
• 1984
The general form of the generating function associated with quadratic asymptotically symmetric birth and death processes is given with no restriction but the positivity of the transition rates.TheExpand
SOLVING THE BIRTH AND DEATH PROCESSES WITH QUADRATIC ASYMPTOTICALLY SYMMETRIC TRANSITION RATES
• Mathematics
• 1982
Birth and death processes with quadratic transition rates are considered with the constraint $\lim _{n \to \infty } \lambda ( n )/\mu ( n ) = 1$. The partial differential equation governing theExpand
Uniqueness and extinction properties of generalised Markov branching processes
This paper focuses on the basic problems regarding uniqueness and extinction properties for generalised Markov branching processes. The uniqueness criterion is firstly established and aExpand


text:
# Solve without convergance?

Two days ago I recalled a problem I was given a long time ago. The problem is:

Four ants are placed on the vertices of a square with side 1. The ants start moving, each directed towards its left neighbour. What is length of each ant's path up to their meeting.

So obviously they will meet in the center of the square and each ant will have travelled the same path. I assumed that on each step each ant travels $1/n$ (in straight direction) of the distance to its neighbour. That way the path is $\frac{1}{n} + \frac{\sqrt{n^2-2n+2}}{n^2} + \frac{\sqrt{n^2-2n+2}^2}{n^3} + \dots = \sum_{i=1}^{\infty} {\frac{\sqrt{n^2-2n+2}^i}{n^i}=1}$ So I fanally each ant's path is of length equal 1.

That's ok but I do remember that when I was told the problem for first time somebody told me a quite logic solution not involving any convergence. Can anybody of you come up with that beatiful solution?

-
Previously: Four turtles/bugs puzzle –  Rahul Mar 20 at 22:37

The tangent vector of each ant at every time forms an angle of $3/4\pi=135°$ with the radius (can you see why? Because they are facing their neighbors!).

(In particular, the ants walk exactly along logarithmic spirals, directed towards the center. But we don't need to know this to perform the calculation. )

This means that $v_r$, the component of the velocity directed towards the center (the one that interests us) is $-|v|/\sqrt{2}$. For simplicity we take $|v|=1$, so $v_r=-1/\sqrt{2}$. In particular, it is constant.

So supposing it starts at $r_0=1/\sqrt{2}$, the half-diagonal of the unit square: $$r(t) = r_0 + v_rt = 1/\sqrt{2} - 1/\sqrt{2}\,t = 1/\sqrt{2}\,(1-t).$$

So we get to the origin ($r=0$) at $t=1$.

Now $|v|$ is constant, so the length of the path simply $L=|v|t$. Since the ants run for a time $t=1$, we get $L=1\cdot 1=1$.

-


text:
## Announcements:

Today we finish 5.3 and start 5.4. Read Section 5.4 for Wednesday. Work through recommended homework questions.

Tutorials: This week: review.
Office hour: Monday, 1:30-2:30, MC103B.
Help Centers: Monday-Friday 2:30-6:30 in MC 106.
Review Session: Friday in class; bring questions.

Final exam: Covers whole course, with an emphasis on the material in Chapters 4 and 5 (after the midterm). Our course will end with Section 5.4.

### Orthogonal Complements

Definition: Let $W$ be a subspace of $\R^n$. A vector $\vv$ is orthogonal to $W$ if $\vv$ is orthogonal to every vector in $W$. The orthogonal complement of $W$ is the set of all vectors orthogonal to $W$ and is denoted $W^\perp$. So $$\kern-4ex W^\perp = \{ \vv \in \R^n : \vv \cdot \vw = 0 \text{ for all } \vw \text{ in } W \}$$

### Orthogonal projection

Definition: Let $W$ be a subspace of $\R^n$ and let $\{ \vu_1, \ldots, \vu_k \}$ be an orthogonal basis for $W$. For $\vv$ in $\R^n$, the orthogonal projection of $\vv$ onto $W$ is the vector $$\proj_W(\vv) = \proj_{\vu_1}(\vv) + \cdots + \proj_{\vu_k}(\vv)$$ The component of $\vv$ orthogonal to $W$ is the vector $$\Perp_W(\vv) = \vv - \proj_W(\vv)$$

We showed that $\proj_W(\vv)$ is in $W$ and $\Perp_W(\vv)$ is in $W^\perp$.

Here and in the rest of Section 5.2, we assume that every subspace has at least one orthogonal basis.

Theorem 5.11: Let $W$ be a subspace of $\R^n$ and let $\vv$ be a vector in $\R^n$. Then there are unique vectors $\vw$ in $W$ and $\vw^\perp$ in $W^\perp$ such that $\vv = \vw + \vw^\perp$.

Theorem 5.13: If $W$ is a subspace of $\R^n$, then $$\dim W + \dim W^\perp = n$$

The Rank Theorem follows if we take $W = \row(A)$, since then $W^\perp = \null(A)$.

### The Gram-Schmidt Process

This is a fancy name for a way of converting a basis into an orthogonal or orthonormal basis. And it's pretty clear how to do it, given what we know.

Theorem 5.15 (The Gram-Schmidt Process): Let $\{ \vx_1, \ldots, \vx_k \}$ be a basis for a subspace $W$ of $\R^n$. Write $W_1 = \span(\vx_1)$, $W_2 = \span(\vx_1, \vx_2)$, $\ldots$, $W_k = \span(\vx_1, \ldots, \vx_k)$. Define: \kern-9ex \begin{aligned} \vv_1 &= \vx_1 \\ \vv_2 &= \Perp_{W_1}(\vx_2) = \vx_2 - \frac{\vv_1 \cdot \vx_2}{\vv_1 \cdot \vv_1} \vv_1 \\ \vv_3 &= \Perp_{W_2}(\vx_3) = \vx_3 - \frac{\vv_1 \cdot \vx_3}{\vv_1 \cdot \vv_1} \vv_1 - \frac{\vv_2 \cdot \vx_3}{\vv_2 \cdot \vv_2} \vv_2 \\ &\vdots \\ \vv_k &= \Perp_{W_{k-1}}(\vx_k) = \vx_k - \frac{\vv_1 \cdot \vx_k}{\vv_1 \cdot \vv_1} \vv_1 - \cdots - \frac{\vv_{k-1} \cdot \vx_k}{\vv_{k-1} \cdot \vv_{k-1}} \vv_{k-1} \end{aligned} Then for each $i$, $\{ \vv_1, \ldots, \vv_i \}$ is an orthogonal basis for $W_i$. In particular, $\{ \vv_1, \ldots, \vv_k \}$ is an orthogonal basis for $W = W_k$.

### New material

Notes: To compute $\Perp_{W_i}$ you have to use the orthogonal basis of $\vv_j$'s that you have constructed already, not the original basis of $\vx_j$'s.

The basis you get depends on the order of the vectors you start with. You should always do a question using the vectors in the order given, since that order will be chosen to minimize the arithmetic.

If you are asked to find an orthonormal basis, normalize each $\vv_j$ at the end. (It is correct to normalize earlier, but can be messier.)

Example 5.13: Apply Gram-Schmidt to construct an orthogonal basis for the subspace $W = \span(\vx_1, \vx_2, \vx_3)$ of $\R^4$ where $$\vx_1 = \collll 1 {-1} {-1} 1, \quad \vx_2 = \collll 2 {1} {0} 1, \quad \vx_3 = \collll 2 {2} {1} 2$$ On whiteboard, scaling intermediate results. We get $$\vv_1 = \collll 1 {-1} {-1} 1, \quad \vv'_2 = \collll 3 3 1 1, \quad \vv'_3 = \collll {-1} 0 1 2$$ If we want an orthonormal basis, we scale these: $$\kern-9ex \vq_1 = {\textstyle\frac{1}{\|\vv_1\|}} \! \vv_1 = \frac{1}{2} \! \collll 1 {\!-1} {\!-1} 1, \ \vq_2 = {\textstyle\frac{1}{\|\vv'_2\|}}\! \vv'_2 = \frac{1}{\sqrt{20}}\! \collll 3 3 1 1, \ \vq_3 = {\textstyle\frac{1}{\|\vv'_3\|}}\! \vv'_3 = \frac{1}{\sqrt{6}} \! \collll {\!-1} 0 1 2$$

Note: You don't need to check that the starting vectors are linearly independent. If they are dependent, then one or more of the $\vv_j$'s will be $\vec 0$, and you can just ignore it.

Example: Is $\vw = \collll 8 {-2} 2 0$ in $W$?

Solution: We can compute that $\proj_W(\vw) = 2 \vv_1 + \vv'_2 - \vv'_3 = \collll 6 1 {-2} 1$, so the answer is no.

Example: Compute the projection of $\vw = \collll 8 {-2} 2 0$ onto $\span(\vx_1, \vx_2)$.

Solution: We use that $\span(\vx_1, \vx_2) = \span(\vv_1, \vv'_2)$. So, by the work done for the previous example, we get $2 \vv_1 + \vv'_2$. (Do not try to work directly with $\vx_1$ and $\vx_2$.)

Example 5.14: Find an orthogonal basis for $\R^3$ that contains the vector $\vv_1 = \colll 1 2 3$.

Solution: Choose any two vectors $\vx_2$ and $\vx_3$ so that $\{ \vv_1, \vx_2, \vx_3 \}$ is a basis for $\R^3$. For example, you can take $$\vx_2 = \colll 0 1 0 \qtext{and} \vx_3 = \colll 0 0 1$$ Then apply Gram-Schmidt, using the vectors in that order, so $\vv_1$ doesn't change. (Details in text.)

### QR Factorization

Theorem 5.16: Let $A$ be an $m \times n$ matrix with linearly independent columns. Then $A$ can be factored as $A = QR$, where $Q$ is an $m \times n$ matrix with orthonormal columns and $R$ is an invertible upper triangular $n \times n$ matrix.

Note that we must have $m \geq n$. (Why?)

Explanation: Write $\va_1, \ldots, \va_n$ for the linearly independent columns of $A$. Apply Gram-Schmidt to produce orthonormal vectors $\vq_1, \ldots, \vq_n$ with $\span(\va_1, \ldots, \va_i) = \span(\vq_1, \ldots, \vq_i)$ for each $i$. Therefore we can find scalars $r_{ij}$ such that: \begin{aligned} \va_1 &= r_{11} \vq_1 \\ \va_2 &= r_{12} \vq_1 + r_{22} \vq_2 \\ &\vdots \\ \va_n &= r_{1n} \vq_1 + r_{2n} \vq_2 + \cdots + r_{nn} \vq_n \\ \end{aligned} That is, $$\kern-8ex A = [\, \va_1 \cdots \va_n \,] = [\, \vq_1 \cdots \vq_n \,] \bmat{cccc} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \emat = QR$$ One can also see that the diagonal entries $r_{ii}$ are non-zero. (Explain.) Therefore, $\det R \neq 0$ and $R$ is invertible.

Note that $r_{ij} = \vq_i \cdot \va_j$.

Example 5.15: Find a QR factorization of $A = \bmat{rrr} 1 & 2 & 2 \\ -1 & 1 & 2 \\ -1 & 0 & 1 \\ 1 & 1 & 2 \emat$.

Solution: The columns of $A$ are the vectors from Example 5.13, so we get the matrix $$Q = \bmat{ccc} \ph 1/2 & 3/\sqrt{20} & -1/\sqrt{6} \\ -1/2 & 3/\sqrt{20} & 0 \\ -1/2 & 1/\sqrt{20} & 1/\sqrt{6} \\ \ph 1/2 & 1/\sqrt{20} & 2/\sqrt{6} \\ \emat$$ We want to find $R$ such that $A = QR$. Since the columns of $Q$ are orthonormal, we have $Q^T Q = I$. So $Q^T A = Q^T Q R = R$ and one can compute $R$ by matrix multiplication to find $$R = Q^T A = \cdots = \bmat{ccc} 2 & 1 & 1/2 \\ 0 & \sqrt{5} & 3 \sqrt{5}/2 \\ 0 & 0 & \sqrt{6}/2 \emat$$ (See text for details.) Note that you can save some work, since you know that the entries below the diagonal must be zero.

Also note that this matrix multiplication is exactly working out the components of $\va_i$ with respect to the orthonormal basis of $\vq_j$'s, using that $r_{ij} = \vq_i \cdot \va_j$.

### Section 5.4: Orthogonal Diagonalization of Symmetric Matrices

In Section 4.4 we learned all about diagonalizing a square matrix $A$. One of the difficulties that arose is that a matrix with real entries can have complex eigenvalues. In this section, we focus on the case where $A$ is a symmetric matrix, and we will show that the eigenvalues of $A$ are always real and that $A$ is alway diagonalizable!

Recall that a square matrix $A$ is symmetric if $A^T = A$.

Examples: $\bmat{rr} 1 & 2 \\ 2 & 3 \emat$, $\bmat{rr} 3 & 2 \\ 2 & 3 \emat$, $\bmat{rr} 1 & 0 \\ 0 & 3 \emat$, $\bmat{rrr} 1 & 2 & 3 \\ 2 & 4 & 5 \\ 3 & 5 & 6 \emat$.

Non-examples: $\bmat{rr} 3 & -2 \\ 2 & 3 \emat$, $\bmat{rrr} 1 & 2 & 3 \\ 5 & 4 & 5 \\ 3 & 2 & 6 \emat$.

Definition: A square matrix $A$ is orthogonally diagonalizable if there exists an orthogonal matrix $Q$ such that $Q^T A Q$ is a diagonal matrix $D$.


text:
# 题目还是简单一点好

## 题目描述

• 1 u c$u$ 的颜色修改为 $c$
• 2 u 查询从点 $u$ 出发，能够到达多少个点。

## 输出格式

10 10 2
1 0 0 1 1 1 0 1 1 0
8 6
4 8
7 2
3 8
10 2
9 5
4 5
1 3
2 1
2 10
2 8
1 5 1
1 10 0
1 1 0
1 4 0
1 4 0
1 1 0
2 8
2 8

1
4
4
4

10 10 3
2 0 2 0 1 0 2 2 0 1
3 9
5 2
7 5
6 2
8 3
2 4
2 1
10 6
6 8
1 7 0
1 9 1
1 7 0
1 8 2
2 1
1 7 1
2 7
2 4
1 9 1
1 9 1

3
1
1

## 数据规模与约定

$1$ $n, q\leq 10 ^3$ $15$
$2$ $C = 1$ $5$
$3$ $C = 2$ $10$
$4$ $C = 3$ $15$
$5$ 不存在 $1$ 操作 $20$
$6$ $35$


text:
Integral Help

noblerare

I've been having trouble with the following three integrals. If anybody could give me a hint on how to get started, that would be greatly appreciated.

Problem 1.
1. The problem statement, all variables and given/known data

$$\int$$$$\frac{dx}{1+cos^2(x)}$$

2. The attempt at a solution

I've tried writing it in these ways:

$$\int\frac{dx}{2-sin^2(x)}$$

$$\int\frac{dx}{(secx+cosx)(cosx)}$$

Let u=cosx
$$\int\frac{-du}{\sqrt{1-u^2}(1+u^2)}$$

So far I've gotten nowhere. I've also tried to make the integral look like the integral for arctanx. I realize that I need to have a -sinx in the numerator but don't know how to make it work out.

Problem 2:
1. The problem statement, all variables and given/known data

$$\int$$$$\frac{dx}{sec^2(x)+tan^2(x)}$$

2. The attempt at a solution

I've tried writing it like:

$$\int$$$$\frac{cos^2(x)}{1+sin^2(x)}$$

U-substitution and trig-substition don't seem to work.

Problem 3:
1. The problem statement, all variables and given/known data

$$\int$$$$\frac{dx}{x^3+1}$$

2. The attempt at a solution

In this problem I actually got somewhere:

I split the denominator into two polynomials and used partial fractions.

I ended with:

$$\frac{1}{3}$$ln(x+1) - $$\frac{1}{3}$$$$\int$$$$\frac{(x-2)dx}{x^2-x+1}$$

Then:

$$\frac{1}{3}$$ln(x+1) - $$\frac{1}{6}$$$$\int$$$$\frac{(2x-4)dx}{x^2-x+1}$$

$$\frac{1}{3}$$ln(x+1) - $$\frac{1}{6}$$$$\int$$$$\frac{(2x-1)dx}{x^2-x+1}$$ - $$\int$$$$\frac{-3dx}{x^2-x+1}$$

$$\frac{1}{3}$$ln(x+1) - $$\frac{1}{6}$$ln(x^2-x+1)+3$$\int$$$$\frac{dx}{x^2-x+1}$$

Now I'm stuck.... don't know what to do.

Any help would be greatly appreciated!

Related Calculus and Beyond Homework News on Phys.org

Gib Z

Homework Helper
For the first two, trying $$t= \tan (x/2)$$ should work nicely =]

Third one, for the final integral, complete the square in the bottom and get it into the standard arctan form.

noblerare

Hey thanks for the help.

For the integral:

$$\int$$$$\frac{dx}{1+cos^2(x)}$$

I use u=tan(x/2) so, after much simplification, I get...

$$\int$$$$\frac{2(1+u^2)du}{(1+u^2)^2+(1-u^2)^2}$$

$$\int$$$$\frac{(1+u^2)du}{(1+u^4)}$$

Now I don't know exactly what I should do. If I try trig substituion, I end up with..

$$\frac{1}{2}$$$$\int$$$$\frac{d\theta}{\sqrt{tan\theta}}$$ + $$\frac{1}{2}$$$$\int$$$$\frac{tan\thetad\theta}{2\sqrt{tan\theta}}$$

Now I don't really know what I should do from here...

Gib Z

Homework Helper
You should check your simplification, i get $$\int \frac{ 2(u^2+1)}{1+ (u^2-1)^2} } du$$ which can be done with some more partial fractions.

tiny-tim

Homework Helper
Hi noblerare!

Yes, Gib Z's tan(x/2) method is a good one, which you should definitely remember, and it certainly works in this case.

But in this case, the square means that tanx might work even better (or cotx).

Alternatively:

Hint: mutiply both top and bottom by cosec^2(x) … now what does that remind you of … ?

noblerare

Yay! I finally got it. Thank you so much, Gib Z and tiny-tim!

"Integral Help"

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving


text:
## LaTeX forum ⇒ Graphics, Figures & Tables ⇒ Non-centered cells in table

Information and discussion about graphics, figures & tables in LaTeX documents.
Kotoschow
Posts: 28
Joined: Mon Apr 09, 2012 3:13 pm

### Non-centered cells in table

Hello everyone,

I'm trying to no avail to create a table every cell in the row starts at the same height. Right now, every two cells in a row are centralized with respect to each other. So instead of:

       Col1|Col2   Row1|    |bla       |bla |bla       |    |bla

I want:

       Col1|Col2   Row1|bla |bla       |    |bla       |    |bla

That is, the first line in every cell in the row starts at the same level.
Suggestions anyone?
Thanks!

Tags:

Johannes_B
Site Moderator
Posts: 4173
Joined: Thu Nov 01, 2012 4:08 pm
What you want is the LaTeX standard for p-columns. Are you using m-clumns by any chance? Don't.

To really help you, we need to see a minimal working example.
The smart way: Calm down and take a deep breath, read posts and provided links attentively, try to understand and ask if necessary.

Kotoschow
Posts: 28
Joined: Mon Apr 09, 2012 3:13 pm
Okay I tried p-columns and it solved my original problem but now it turns out I have a new problem: the table itself is centered with respect to the
\item
in a list. I provide a MWE which demonstrates this. This MWE produces a list with a table such that the table is centered with respect to the item label. However I want all of them to appear in the same line.

\documentclass{article} \begin{document} \begin{enumerate}\item \begin{tabular}{p{2pt}p{5cm}}* & This curriculum vitae template has been designed for an academic CV. The current structure provides a summary of academic history without going in-depth on any one constituent part but the  \\ \end{tabular}\end{enumerate} \end{document}

Johannes_B
Site Moderator
Posts: 4173
Joined: Thu Nov 01, 2012 4:08 pm
Very good example, the tabular is a box and gets typeset with its vertical center aligned with the baseline of the surrounding text. Use the optional argument to get the top of the box aligned.

\documentclass{article} \begin{document} \begin{enumerate}	\item \begin{tabular}[t]{p{2pt}p{5cm}}			* & This curriculum vitae template has been designed for			an academic CV. The current structure provides a summary			of academic history without going in-depth on any one			constituent part but the		\end{tabular}\end{enumerate} \end{document}

I hope you are not designing a template. By the way, what is your definition of a template? Personally, i am very confused.
The smart way: Calm down and take a deep breath, read posts and provided links attentively, try to understand and ask if necessary.

Kotoschow
Posts: 28
Joined: Mon Apr 09, 2012 3:13 pm
Sorry sorry sorry this text is just a filler! it has no meaning.

Anyway it worked, thanks a lot.


text:
Notifications in Mac from a Linux SSH server

Aim

As part of my work, I usually SSH into a Linux machine from my Mac, open Emacs, and do coding and other stuff in Emacs. Quite frequently, I execute commands to compile/execute something. These commands usually take some time to run. In the meantime, I switch to some other task and check the command's progress every once in a while.

Instead of having to check for the command's completion manually, I wanted to be notified whenever the command is done.

What I wanted is - when I run a long running command like in the following image -

I need a notification when the command finishes like so -

Execution

Suppose we want to display a notification whenever a command finishes after taking more than 20 seconds. To achieve this, we need someone to monitor the time taken by all the shell commands issued. If any command takes more than 20 seconds, we need a way to communicate it to the Mac. So, we have to answer the following questions to get this working -

1. How will we monitor all the commands issued?

2. How will we communicate a command's completion to Mac?

3. How will we display the notification?

Monitoring every command

In Emacs, I use a shell buffer as my shell. Since Emacs is the one proxying all the commands issued in this buffer to the actual shell process, it would be a perfect fit to monitor the commands.

Emacs's shell buffer emulates a terminal. Every command we issue in this buffer is passed on to the shell process with stdout and stderr bound to the buffer. Where this buffer differentiates itself from a terminal is that it is like any other Emacs's text buffer. This means we can search through the command history and output without requiring to grep, jump to previous commands just like jumping to the end of a function in Python code, etc. Basically, shell mode is a terminal with all of Emacs's text editing capabilities.

In Emacs, every keystroke invokes a function. In Emacs's shell mode, when we press the Enter key, the function comint-send-input runs sending the input to the shell process. Emacs allows customizing the behaviour of functions using hooks. Our function comint-send-input runs the functions in comint-input-filter-functions before sending the command to the shell process and the ones in comint-output-filter-functions after receiving the output.

So, before sending every command, we will note down the command and the timestamp. Once we receive the output from the command, we can do whatever we want based on the time it took for the command to complete. The following code is run on every command submission -

 (defun set-command-submission-time (command)    (ring-insert fifo (cons command (current-time)))    command)    (add-hook 'comint-input-filter-functions #'set-command-submission-time)

Since we can issue multiple commands at once to the shell, we need a collection data structure to store the timestamps. fifo is a ring object that implements a FIFO queue. On every command submission, this code inserts into fifo a cons of the actual command the timestamp.

The following code runs on every command completion -

 (defun check-message (msg)    (when (and (not (ring-empty-p fifo))               (string-match (concat comint-prompt-regexp "\$") msg))      (let* ((entry (ring-remove fifo))             (message (car entry))             (time-taken (float-time (time-since (cdr entry)))))        (when (>= time-taken 20)          (notify-command-to-user message time-taken))))    msg)    (add-hook 'comint-output-filter-functions #'check-message)

The function check-message is called every time some output is inserted into the buffer. In the let* block, we pop the message and timestamp from the fifo and in case the command was issued more than 20 seconds back, we notify the user using notify-command-to-user. How exactly we are going to do this is the topic of the next section.

One problem with this is - the function check-message is run every time some output is inserted into the buffer; not just at the end of a command execution. So, to figure out when a command has finished execution, I'm using the following heuristic - check if the output matches the command prompt regexp. If it does, the command has finished execution. This is just a heuristic and there are cases where this can fail.

One more detail involved here is - I frequently have multiple shells open. If all these shells use the same fifo, then a timestamp queued by one shell might be dequeued by another shell. To avoid this, we make fifo a buffer local variable.

Communication to Mac

We now have a way to find out when a command took more than 20 seconds to complete. Next task is to figure out how to communicate this to the SSH client (Mac). The only link between the Mac and the server is the SSH tunnel created. We are going to use this tunnel for communication. OpenSSH client has an amazing feature called remote port forwarding 1.

The command to do this looks something like

ssh -R localhost:8888:localhost:7777 <server>

This instructs the SSH client to start listening a port, 8888 in this case, on the server. This listener then forwards all the packets it receives to the client at port 7777. It uses the established SSH tunnel for the network path.

We now have a network path we can use to communicate to the client. Now we need to decide on a protocol - what data will we send to Mac? I went with HTTP. We'll make Emacs send a HTTP POST call to localhost:8888. SSH forwards this to Mac at port 7777. I will run a simple HTTP service in Mac that listens on port 7777 and displays the notification.

So, the notify-command-to-user function does the following -

 (defun notify-command-to-user (command time-taken)    (call-process "curl" nil nil nil "-X" "POST" "-d" (format "%d\n%s" time-taken command) "localhost:7777"))

Basically we are calling curl -X POST -d <command and time-taken> localhost:7777 from Elisp.

Following is the Python code that starts a HTTP server on port 7777 -

  import http   import http.server as server   import subprocess   import sys       class NotificationHandler(server.BaseHTTPRequestHandler):       def do_POST(self):           length = int(self.headers["Content-Length"])             # Since the socket is not an interactive socket, we can be           # sure that command contains the entire body. We don't           # bother with any Content-Encoding stuff.           try:               body = self.rfile.read(length)               body = body.decode("utf-8")               # time and command are separated by a newline               separator = body.index("\n")               time = int(body[:separator])               command = body[separator:]                 # We've to escape \ and " in the command. Otherwise, we               # may be vulnerable to accidental command injection.               command = command.replace("\\", "\\\\").replace('"', '\\"')             except Exception:               print(f"Failed to parse the body - {body}", file=sys.stderr)               self.send_error(http.HTTPStatus.BAD_REQUEST)               return             # Display a notification with this command now           try:               subprocess.check_output(                   [                       "osascript",                       "-e",                       f'display notification "{command}" with title "Command Finished" subtitle "Took {time}s"',                   ]               )           except subprocess.CalledProcessError as e:               print(f"Command {e.cmd} failed due to error {e.output}", file=sys.stderr)             self.send_response_only(http.HTTPStatus.ACCEPTED)           self.flush_headers()       if __name__ == "__main__":       server_address = ("", 7777)       httpd = server.HTTPServer(server_address, NotificationHandler)       httpd.serve_forever()

We first create a NotificationHandler class that can handle the POST call 2. This class's do_POST method is invoked for every POST request. In this, we read the body and sanitize the command by escaping double quotes and backslashes to prevent any accidental command injection.

We then use osascript command to display a notification.

So finally, Emacs figures out what commands to notify the users about, SSH provides the network path, and a HTTP server in Mac displays the notification.

Final Setup

To get this working without any configuration in future,

1. I added HTTP server to startup applications in my Mac.

2. Added the above Emacs scripts to my Emacs startup file.

3. Instead of SSHing to the machine like ssh <server>, I have to use ssh -R localhost:8888:localhost:7777 <server>.

That's it.

Security Concerns

1. We are now running a HTTP server in our Mac capable of displaying notifications. Anyone with a network path to our system can spam us with notifications. I'm not sure how best to avoid this. One way is to use iptables equivalent to restrict access to port 7777 only to localhost.

2. Adding to the above point, Python's http.server module explicitly mentions that this is not a secure HTTP server.

References

1

The Black Magic Of SSH / SSH Can Do That? https://vimeo.com/54505525

2

BaseHTTPRequestHandler https://docs.python.org/3/library/http.server.html#http.server.BaseHTTPRequestHandler

3

Running Shells in Emacs: An Overview https://www.masteringemacs.org/article/running-shells-in-emacs-overview


text:
# First order logic. Independent set of sentences.

Let $\Delta$ be a finite, consistent set of first-order sentences and $\Sigma$ be a finite signature. Prove that there exists such $\Delta_0 \subseteq \Delta$ that $\Delta_0 \models \Delta$ and : for every $\phi \in \Delta_0 , \Delta_0 \setminus \{\phi\} \not \models \Delta_0$

I tried to do it. I am asking for hint.

$$\Delta \text{ is independent iff for every } \phi \in \Delta_0, \Delta_0 \setminus \{\phi\} \not \models \Delta_0$$

Solution:

Base induction

Let $|\Delta| = 0, \Delta = \emptyset$. $\emptyset \models \Delta, \emptyset$ is indenpendent.

Induction step Let $|\Delta| = n$ and $\Delta_0 \subseteq \Delta, \Delta_0 \models \Delta, \Delta_0$ is independent. Let's consider two cases:

Let $\Delta' = \Delta \cup \{\phi\}$ for any $\phi$

1. $\Delta_0 \models \{\phi\}$. Then $\Delta_0 \models \Delta'$ and $\Delta_0$ is still independent

2. $\Delta_0 \not \models \{\phi\}$ Let $\Delta_0' = \Delta_0 \cup \{\phi\}$. Then $\Delta_0' \models \Delta'$ Now, let consider two cases:

2.1 $\Delta_0'$ is independent. Thesis.

2.2 $\Delta_0'$ is not independent. Therefore, there exists a such $\psi \in \Delta_0$ that $\Delta_0' \setminus \{\psi \} \models \Delta_0'$. Let $\Gamma = \Delta_0' \setminus \{\psi\}$. Note, that $|\Gamma| \le |\Delta|$. So, from the inductive assumption, we have that there exists a such $\sigma \subseteq \Gamma$ that $\sigma \models \Gamma$ and $\sigma$ is independent. $\sigma \models \Gamma, \Gamma \models \Delta_0'$ so $\sigma \models \Delta_0'$

Is it ok?

• Hello - welcome to the site. Posts that merely pose a problem, without context, are discouraged (indeed, they are often indistinguishable from copies of homework problems) There is some advice at this link about how to write a good post: meta.math.stackexchange.com/questions/9959/… . You can edit your post at any time to improve it. Information that could be included: where did the problem arise? What is your interpretation of it? What have you attempted already? – Carl Mummert Nov 19 '16 at 21:09
• The main hint I can think of is to use induction. What have you tried? – Carl Mummert Nov 19 '16 at 21:12
• Ok, good idea- I wil try to use induction, but why do I should- after all- sets are finite? – user376326 Nov 19 '16 at 21:14
• @Logic Carl means induction on the size of $\Delta$. – Noah Schweber Nov 19 '16 at 21:22
• @NoahSchweber, I edited. – user376326 Nov 20 '16 at 13:00

Let $P(n)$ stand for the claim that every finite, consistent set $\Delta$ of $n$ sentences from a first-order language with signature $\Sigma$ contains an independent subset $\Delta_0$. Your problem consists of proving $\forall n . P(n)$. Therefore induction is the natural approach to the proof. Each $n$ is finite, but you want a proof for all $n$.
• It's a good start. You may want to work on the wording. For instance, "Now let $n>0$ and $\Delta = \Delta' \cup \{\phi\}$ with $\phi \not\in \Delta'$. By the induction hypothesis,..." – Fabio Somenzi Nov 20 '16 at 15:10
• It's close. For instance, when you say, "Let \Delta' = \Delta \cup \{\phi\}$for any$\phi$," you actually mean "some$\phi$." Rewriting the proof as I suggested in my previous post would take care of some of these details. Also, switching from uppercase ($\Delta$,$\Gamma$) to lowercase ($\sigma$) is not a mistake, but should be avoided. – Fabio Somenzi Nov 20 '16 at 15:45 • Yes, I meant some instead any. So, generally it is ok, yeah? – user376326 Nov 20 '16 at 15:52 Among finite subsets of$\Delta$, there are some of them that satisfy$\Delta_0 \vDash \Delta$, and some of them that do not. Pick one that is minimal:$\Delta_0 \vDash \Delta$, but for all$\Delta_0' \subsetneq \Delta_0$,$\Delta_0' \not \vDash \Delta$. Now you have to prove that for any$\phi \in \Delta_0$,$\Delta_0 \setminus \{\phi\} \not \vDash \Delta_0$. Suppose towards contradiction that$\Delta_0 \setminus \{\phi\} \vDash \Delta_0$. Then we have$\Delta_0 \setminus \{\phi\} \vDash \Delta_0$and$\Delta_0 \vDash \Delta$, so$\Delta_0 \setminus \{\phi\} \vDash \Delta$. This contradicts the minimality of$\Delta_0\$.


text: Nawar , A. S., and H. M. Atallah. “On $$\delta\beta$$-Open Sets in Tri Topological Spaces”. Journal of Advanced Studies in Topology 12, no. 1-2 (July 27, 2022): 8–17. Accessed August 9, 2022. http://www.m-sciences.com/index.php/jast/article/view/284.


text:
# Homework Help: A type 2 superconductor is placed in a small magnetic field

1. Nov 7, 2011

### mkbh_10

A flux quantum is approx. equal to 2*(10)^(-7) gauss cm*cm. A type 2 superconductor is placed in a small magnetic field which is then slowly increased till the field starts penetrating the superconductor. THe strength of the field at this point is 2/pi*(10)^(5) gauss.

The penetration depth is

100 Angstrm
10 angstrm
1000 angstrm
314 angstrm

The applied field is further increased till superconductivity is completely destroyed. The strength of field is 8/pi*(10)^5 gauss. The correlation length of superconductor is

20 A
200 A
628 A
2000 A