text:
## Probabilistic Proofs of Undecidable Sentences?

22 04 2009

As I suggested (though perhaps not made as clear as I would have liked) in my forthcoming paper “Probabilistic Proofs and Transferability”, I think that probabilistic proofs can be used to provide knowledge of mathematical facts, even though there are reasons why we might think they should remain unacceptable as part of mathematical practice. (Basically, even though mathematicians gain knowledge through testimony all the time, there may be reasons for a methodological insistence that all mathematical arguments not rely essentially on testimony, the way probabilistic proofs (just like experiments in the natural sciences) do.) Given that this allows for a non-deductive means of acquiring mathematical knowledge, a natural question would be whether probabilistic proofs can be used to settle questions that are undecided by standard axiom sets. Unfortunately, I think the answer is probably “no”.

The sort of probabilistic proofs that I endorse aren’t just any old argument that isn’t deductively valid. In my paper, I contrast probabilistic proofs of the primality of a given number with certain arguments in favor of the Goldbach Conjecture and the Riemann Hypothesis, as well as lottery arguments. The primality arguments work by showing that if n is prime, then a certain result is guaranteed, while if n is composite, then the probability of the same sort of result is at most 1/4k, where k can be made as large as one wants by generating more random numbers. As a result the evidence “tracks” the truth of the claim involved (that is, the evidence is very likely if the claim is true and very unlikely if the claim is false).

In the case of the Goldbach Conjecture, one of the pieces of “probabilistic” evidence that we have is that none of the first several million even numbers is a counterexample to the claim. However, although this evidence is very likely if the claim is true, we have no good a priori bounds on how likely this evidence would be if the claim were false. Thus, the evidence may give us some reason to believe the Goldbach Conjecture, but it’s hard to see just how much more evidence we’d need in order for this to give us knowledge that the Goldbach Conjecture is in fact true.

In the case of the Riemann Hypothesis, I don’t have room (or the knowledge) to state all the relevant pieces of evidence, but in this case the evidence is more of the type of “inference to the best explanation”, but again lacks any sort of probabilistic bounds on the possibility of it arising in misleading cases. This is not to say that this type of evidence can’t provide knowledge – in fact, we may already have enough evidence to count as knowing that the Riemann Hypothesis is true, though I’m definitely not certain of this. At any rate, if this does provide knowledge, it’s of a different sort than probabilistic proof, and may well have its own problems for acceptability in the mathematical canon.

In “lottery cases”, we have strong probabilistic evidence for the claim that a particular ticket will not win (in particular, that this ticket is in a fair lottery, and that there are a billion separate tickets, exactly one of which is a winner). However, most people want to say that we don’t have knowledge of this claim. Again, at least part of the reason is that our evidence doesn’t track the truth of the claim – nothing about our evidence is sensitive to the ticket’s status, and the evidence is just as likely if the claim is false (that is, the ticket is a winner) as if it’s true (that the ticket isn’t a winner).

Therefore, it seems that for any sort of evidence that we’d count as a “probabilistic proof” that gives us knowledge of some mathematical claim, we’d want to have good bounds on the probability of getting such evidence if the claim were true, as well as good bounds on the probability of getting such evidence if the claim were false. At the moment, I can’t really conceive of ways of generating mathematical evidence where there would be clear bounds on these probabilities other than by randomly sampling numbers from a particular bounded set. (There may be possibilities of sampling from unbounded sets, provided that the sampling method doesn’t rely on a non-countably-additive probability, but it’s a bit harder to see how these sorts of things could be relevant.)

Now let’s consider some claim that is independent of Peano Arithmetic, and see if there might be any way to come up with a probabilistic technique that would give evidence for or against such a claim, that had the relevant probabilistic bounds.

Unfortunately, I don’t think there will be. Consider two models of PA – one in which the claim is true, and one in which it’s false. We can assume that one of these models is the standard model (that is, it just consists of the standard natural numbers) while the other is some end-extension of this model. If our probabilistic method involves generating natural numbers through some random process and then checking their properties, then this method will have the same probabilities of generating the same numbers if applied in either one of these models (since presumably, the method will only ever generate standard natural numbers, and not any of the extra things in the non-standard model). Thus, any result of such a test will have the same probability whether the statement is true or false, and thus can’t be sensitive in the sense demanded above.

Now, one might worry that this argument assumes that conditional probabilities will have to be probabilities given by considering a particular non-standard model. This clearly isn’t what we’re doing in the case of primality testing however – we don’t consider the probabilities of various outcomes in a model where n is prime and in a model where n is not prime, not least because we have no idea what a model of the false one would even look like.

However, I think this is what we’d have to do for statements that could conceivably be independent of PA. Consider any process that involves sampling uniformly among the integers up to k, and then performing some calculations on them. Knowing the truth of PA, we can calculate what all the possible results of such a process could be, and verify that these will be the same whether our independent statement is true or false. Since this calculation will tell us everything we could possibly gain from running the probabilistic process, and it hasn’t given us knowledge about the independent statement, the probabilistic process can’t either, since it adds no new information, and therefore no new knowledge.

If we allow for probabilistic processes that sample from all natural numbers (rather than just sampling uniformly from a bounded range of them) I think we still can’t get any relevant knowledge. Assuming that the sampling process must have some countably additive probability distribution, then for any ε there must be some sufficiently large N that the probability that the process never generates a number larger than N is at most ε. By the above argument, the process can’t tell us anything about the independent statement if it never generates a number larger than N. Therefore, the difference in probability of various outcomes given the statement and its negation can’t be any larger than ε. But since ε was arbitrary, this means that the difference in probabilities must be 0. Thus, the process still fails to meet the sensitivity requirement, and therefore can’t give knowledge about the independent statement.

Thus, we can’t get probabilistic information about independent claims. Of course, since many people will be willing to say that we have good reason to believe the Goldbach Conjecture, and the Riemann Hypothesis, on the evidence mentioned above, we may be able to get arguments of those sorts for independent claims. But such arguments aren’t really “probabilistic” in the sense standardly discussed.

Additionally, there are many claims independent of Peano Arithmetic that we can prove using standard mathematical means. Some examples include Goodstein’s Theorem, the Paris-Harrington Theorem, and Borel Determinacy. (The latter is in fact so strong that it can’t be proven in Zermelo set theory, which is ZF set theory without the Axiom of Replacement.) In fact, the arguments given above show that probabilistic methods not only fail to decide claims that are undecided in PA, but in fact fail to decide claims that are independent of substantially weaker systems, like Robinson arithmetic and probably even Primitive Recursive Arithmetic. Since basically everything that is of mathematical interest is independent of PRA (basically all it can prove is statements saying that a recursive function has a specific value on specified inputs, like “376+91=467”) this means that probabilistic proofs really can’t do much. All they can do is give feasible proofs of claims that would otherwise take a very long time to verify, as in the primality of a particular number.

## Coding Truth and Satisfaction

23 07 2007

I just got back from a week visiting the Canada/USA Mathcamp, where I spent a few days teaching a class on Gödel’s theorems. I only got to the incompleteness theorems on the last day, when I introduced Gödel numbering, showed that some syntactic relations were definable, suggested that provability was therefore definable, and showed that truth (in the standard interpretation) is not definable. Thus, I didn’t get to anything like the full incompleteness theorems, but just showed that there is no recursive set of axioms such that truth in the standard interpretation corresponds to provability from those axioms.

The thing about showing that truth is not definable is that you normally go through satisfaction instead. Given the fact that syntactic relations are definable, we can define functions $NUMERAL(z)$ (which returns the code number for the numeral expressing $z$) and $SUBST(x,y)$ (which takes $x$ as the code of a formula with one free variable, and substitutes in the term that $y$ is the code of, and returns the code of the resulting sentence). Then $SAT(x,y)$ (which says that $x$ is the code of a formula satisfied by number $y$) can be defined in terms of $TRUE(x)$ by $TRUE(SUBST(x,NUMERAL(y)))$.

Then, it’s fairly straightforward to show that $SAT(x,y)$ is not definable. If it were, then we could define $\lnot SAT(x,x)$, which would have some code number $n$. But then $\lnot SAT(n,n)$ would be true iff $n$ didn’t satisfy $\lnot SAT(x,x)$, which is a contradiction. Therefore, $SAT(x,y)$ is not definable.

Afterwards, someone pointed out that this proof of the undefinability of $SAT(x,y)$ doesn’t make any assumption about how the coding works, which seems somewhat surprising. After all, I could take highly non-effective codings, and the undefinability of $SAT$ would still hold. This is surprising, because $TRUE(x)$ can be defined under certain encodings. One such encoding is just to separate the sentences into true and false ones, and code them respectively by even and odd numbers, using some sort of lexicographic ordering. Then, since being even and being odd are both definable, truth would be definable as well. But it turns out that no trick like this is going to let satisfaction be definable, because of the diagonalization argument I gave above.

My guess for why this is is because satisfaction requires something like a coding of some of the syntactic structure as well as some of the semantic structure. Standard codings make the syntax definable, but then the semantics fails. Certain bizarre codings let the semantics be definable, but they make the syntax fail. But since the syntax and semantics aren’t recursive in terms of each other, there’s no way to make them both recursive, the way satisfaction seems to require. (Of course, you could probably choose some awful coding that makes both sets of relations undefinable, but why would you want to do that?)

Anyway, going back to camp is always great for precisely this sort of reason – I get to try to teach something new and interesting that I haven’t taught before, and people ask questions that also help me understand the material in a new way.

## Penrose and Perry

17 07 2006

Last week, one of the campers asked me about Penrose’s arguments about the mind based on Gödel’s theorems. I wasn’t entirely sure about them, since it’s been years since I read Penrose, but I discussed it for about an hour with the camper and another staff member that was interested, and helped clarify (to myself as well) what seems to be going on here. In the process, I think I’ve found a connection between an issue of these arguments and John Perry’s “The Problem of the Essential Indexical”. (Of course, I should probably check out the book on Gödel’s theorem by the late Torkel Franzén for more about these arguments.)

Anyway, as far as I can remember (which may not be terribly accurate), Penrose’s arguments go something like the following. If humans were computational beings, then the set of mathematical truths knowable by humans would be recursively axiomatizable. The set of truths knowable by humans seems to include Peano arithmetic. Therefore, Gödel’s second incompleteness theorem tells us that the fact that this set of truths is consistent is independent of this set, and thus the consistency can’t be known. However, since we know that the truth is consistent, and we know this set of sentences to be true, this means that we know the set is consistent, which is a contradiction. Therefore, our initial assumption that humans are computational must be false.

Some versions of this argument might use some propositional attitude other than knowledge – I think those would generally be weaker arguments, because there’s no good reason to suppose that beliefs (or anything else) should be consistent. I will also bracket the contention by various non-classical logicians that the truth might not actually be consistent – I think all that we need is that 0=1 is not provable from the knowable truths, and that Gödel’s theorem tells us we can’t prove that. And besides, I can’t conceive of what it would mean for the truth to be inconsistent (except perhaps for some special cases like the liar paradox).

I think the important challenge to this argument comes when I say “we know this set of sentences to be true, [and thus] we know the set is consistent”. There seems to me to be an important ambiguity in knowing a set of sentences to be true. In particular, there is a difference between knowing, of each sentence in the set, that it is true, and knowing of the set as a whole, that all of its elements are true sentences. To know that the set is consistent, one needs the latter, rather than the former, because consistency is a property of the set as a whole, and not of its individual sentences, the way truth is.

In other words, although I might know that “the set of all mathematical truths that I know is a consistent set”, it seems plausible that if I was presented with this same set under a different mode of presentation, I might not recognize it as a consistent set. This seems to be an important step in this version of Penrose’s argument – I don’t think Gödel’s theorems would cause trouble for my knowledge of the statement “the set of all mathematical truths I know is consistent”, though it would cause trouble for any system S proving the statement “system S is consistent”, when system S is presented in some sort of transparent manner, say by listing its axioms. Presenting it as “my system” doesn’t let me prove much about its consequences, so I can know it to be consistent. Presenting it in a more extensional format lets me prove a lot about its consequences, perhaps at the cost of my knowing that it’s consistent. Penrose would need to bridge that gap in order for his argument to be valid. (At least as stated above – it seems quite plausible that he’s got a more subtle argument that gets around these points.)

Anyway, I found an interesting duality here to Perry’s point in “The Problem of the Essential Indexical”. In that paper, Perry points out the importance of learning some essentially indexical information in addition to purely descriptive information. In his example, one can be in a grocery store and see a trail of spilled sugar, and realize “someone has a leaky bag of sugar – I should go let him or her know”. After following the trail for a little bit, one realizes one is walking in a circle, and evetually gains the new information “I have a leaky bag of sugar”, at which point one can remedy the situation. This information must be presented with the indexical “I”, rather than with any description or other third-person presentation (unless one already has the connection between that description and the first person).

Conversely, in this case with the Penrose argument, it seems to me that one might have the indexical information, without the third-person description! That is, one can know “the set of mathematical truths I know is consistent” (because it is a set of truths), without knowing, “system S is consistent”, even if system S characterizes the set of mathematical truths I know. Perhaps all that’s important here is the difference between two different descriptions of the same set, but maybe there’s a role for Perry’s “essential indexical” as well, though the role is the opposite of the one he is concerned with.

## Church-Turing Theses

18 04 2006

On my way back from Austin, I visited my friend Bob McGrew in Palo Alto, and we caught up with each other a bit. At a certain point, when we were talking about our respective research, the subject of the Church-Turing Thesis came up (I don’t remember how, because it’s not really directly related to what either of us does, though not terribly far from either). In our discussion, we both clarified distinct versions of the CT Thesis that the other hadn’t realized.

The basic idea is that the CT thesis is an analysis of the pre-theoretic notion of computability – in this version the thesis approximately states: A problem is intuitively computable iff it can be solved by a Turing machine. However, it’s easy to forget that this is a conceptual analysis claim (especially if one isn’t a philosopher, and thus exposed to conceptual analyses all the time). There are only a few other equally widely accepted conceptual analyses – perhaps Tarski’s account of logical consequence (which has been disputed by John Etchemendy), and maybe one or two others. But in general, these are highly contentious claims, that are often disputed, the way Gettier disputed the justified true belief account of knowledge.

Because this particular analysis has been so successful, it’s easy for computer scientists to forget that it is one, and instead think the CT thesis is the following: A problem is physically computable iff it can be solved by a Turing machine. Now that we’re used to physical computers doing this sort of stuff all the time, it seems that this is what we’re talking about – but there was a notion of what an algorithm was, or an effective process, long before we had machines to carry them out. And people can still intuively recognize whether a sequence of instructions is algorithmic without trying to reduce it to a physically programmable algorithm. However, CS texts very often say something like, “the CT thesis is a statement that is not amenable to proof or verification, but is just a matter of faith”. This statement doesn’t accurately describe this second thesis though – after all, it’s a matter of empirical physical investigation whether relativity or quantum mechanics allow for any processes that are not Turing-computable. Perhaps more relevantly, it may also be an empirical matter whether a physical device with the full strength of a Turing machine can be created! After all, a Turing machine needs an unbounded tape, and actual computers have finite memory space – and every device that can only accept or reject finitely many strings is automatically computable on just about every sense of the word (including ones much weaker than Turing-computable, like finite-state-machine recognizable, and the like).

At any rate, one might want to make the three-way identity claim: The pre-theoretic notion of computability, Turing’s account of computability, and physical computability all coincide.

What Bob pointed out to me was that many computer scientists actually subscribe to a claim that’s much stronger than these ones. Rather than focusing on the general notion of what is computable, it deals with the speed of the computability. Roughly speaking, this thesis says: Every physically realistic model of computation is polynomially reducible to every other one. I believe that this thesis has lately been threatened by the feasibility of quantum computation – although it preserves the absolute notion of computability, quantum computation allows computations that could only be done in non-deterministic polynomial time (NP) to be done in deterministic polynomial time (P). I suppose if P=NP turns out to be true, then this doesn’t damage this thesis, but since most people believe that it’s false, this seems to be evidence against this thesis.

However, there is a slightly weaker version available, that is still much stronger than the earlier ones, saying: Every mathematical model of computation from a certain list is polynomially reducible to every other one. This seems to be true with register machines, Turing machines, and apparently lots of the other formalisms that have been developed, both in the 1930’s and later. Of course, the claim can’t be strengthened too much, because an oracle for Turing computability could solve all computable problem in constant time. We also need to specify an appropriate notion of time and/or space complexity for each notion of computing. But so far, the most natural-seeming notions have ended up having this feature. Which is really quite interesting when you think about it.

## More on Gödel, Structuralism, and Machines

4 06 2005

I was just talking to Fabrizio Cariani (one of the other students in my program here) about my earlier post on a version of structuralism that treats elementarily equivalent structures as the same, rather than just isomorphic ones. But he pointed out that although this would avoid the problems of the Löwenheim-Skolem theorems, it still wouldn’t avoid the problem of Gödel’s incompleteness theoresm. That is, we need to have a complete theory to specify a structure completely in this sense, but Gödel’s incompleteness theorems show that no recursive theory extending Peano arithmetic or ZFC is complete, so we can’t even pin down the natural numbers or the sets to this extent. It’s sort of nice that the platonist account of mathematical objects runs afoul of isomorphic models, the standard structuralist account runs afoul of the Löwenheim-Skolem theorems, and the “elementary equivalence structuralist” account runs afoul of the Gödel theorems.

Fabrizio had been thinking about this because he had just been looking at the result that there are continuum-many non-equivalent countable models of PA. This is because for any recursive, consistent theory T extending PA, Gödel shows that T+Con(T) and T+~Con(T) are both recursive, consistent theories extending PA. Thus, there is a complete binary tree of such theories, and by the compactness theorem, each infinitary branch of the tree is a consistent theory extending PA. Since any two such branches differ at some stage over whether they add Con(T) or ~Con(T), the models of the theories are going to be non-equivalent, so there are continuum many non-isomorphic models. (This is also the theoretical upper bound on the number of countable models for any theory in a finite language, because there are only countably many objects and tuples of objects, and for each of the finitely many predicates and relations in the language, there are two choices for each tuple of the appropriate size.)

Now, returning to yesterday’s post on mechanism, I think Lewis’ point is stronger than I had thought originally. In the comments, Peter McB suggests that there is a machine that takes any consistent, recursive theory T extending PA and outputs the sentence Con(T). Now that I think about it, I think the procedure Gödel himself used is amenable to this sort of recursive construction. Now, for any countable string of 0’s and 1’s, we can use this machine to recursively enumerate an axiomatization for some consistent extension of PA, by letting T_0 be PA, and using the machine to enumerate the axioms Con(T_i) or ~Con(T_i), depending on whether the ith bit of the string is 1 or 0. The fact that these enumerations are recursive in the string doesn’t violate Gödel’s theorem, because it just means that the theory PA + Con(PA) + Con(PA+Con(PA)) + … is itself not a complete theory. And similarly for the theory PA + ~Con(PA) + ~Con(PA+~Con(PA)) + …, and so on for any other theory given by some recursive string of 0’s and 1’s.

Now, it seems intuitive to me that no such theory is going to be complete, but Gödel’s theorem only tells us that the ones produced by recursive strings of 0’s and 1’s aren’t complete. Is it possible that some non-recursive string of 0’s and 1’s gives a complete theory? That would be weird. I suppose recursion theorists might have a better idea about this.

## Lewis on Lucas on Gödel

3 06 2005

I recently bought David Lewis’ Papers in Philosophical Logic and have been reading some of the essays recently, starting with the shorter ones. I hadn’t remembered how engaging his writing style is.

Anyway, I should probably read Roger Penrose again some time, but from what I remember of his theses in The Emperor’s New Mind and Shadows of the Mind, it looks like they were pretty soundly refuted long before he wrote the books. This was by Lewis in his two papers “Lucas against Mechanism” and “Lucas against Mechanism II”. The first one just makes the point that the inference rule from a theory to its consistency statement is in general infinitary, and thus can’t clearly be run in general. But the second one faces a tougher argument, because of the way Lucas seemed to moderate his position. (I haven’t actually read Lucas, or even heard of him before reading these two papers by Lewis, but it sounds like he was advocating the same position that Penrose did, that our ability to recognize Gödel statements proves that humans are not Turing machines.)

In the second paper, Lewis phrases Lucas’ argument as a challenge to the mechanist to produce a Turing machine that generates exactly the set of truths that Lucas recognizes to be true. Lucas can then find the Gödel statement of this machine and recognize it to be true, which shows Lucas not to be this actual machine. But Lewis points out that since this allows Lucas to respond to challenges, the machines proposed must also be the sort that can respond to challenges. So if the mechanist proposes that Lucas is the machine M, then Lucas might either be responding with the Gödel number of the machine M, or with the Gödel number of the machine M would turn into in response to a challenge with the number M. But Lewis claims that there are many machines that make the former response to any true accusation that they are M, and there are many machines that (falsely) make the latter response to any true accusation that they are M, so Lucas’ ability to give such a response doesn’t prove him not to be a machine.

This is where I would like a bit more clarification. At first Lewis’ claim sounded ridiculous, because it sounded like his response to the former was a machine that takes any input and responds with the Gödel number for that input, which sounds impossible to me. (Maybe I’m wrong about that?) Now I think that he actually meant something more like a machine that gives the same response to any challenge, and this response just happens to be its own Gödel number. After all, Lewis only required it to function right on true challenges to its identity. I wish I could link to the text of the article (it’s just 4 pages), but the Canadian Journal of Philosophy seems not to have its issues from 1979 online.

(The reason I filed this under the category “set theory” is because of the last few lines of the first “Lucas against Mechanism”:

We do not know how Lucas verifies theoremhood in Lucas arithmetic, so we do not know how many of its theorems he can produce as true. He can certainly go beyond Peano arithmetic, and he is perfectly justified in claiming the right to do so. But he can go beyond Peano arithmetic and still be a machine, provided that some sort of limitations on his ability to verify theoremhood eventually leave him unable to recognize some theorem of Lucas arithmetic, and hence unwarranted in producing it as true.

This is I think exactly what set theorists are doing – trying to see just how far beyond PA (and in fact, beyond ZFC) they can go.)

## Field on Consistency

2 02 2005

In “Realism, Mathematics, and Modality”, pp. 31-32, Hartry Field makes what seems to me to be a muddled argument about the consistency of set theory on platonistic grounds. He starts by suggesting that it is unproblematic that if a theory T is true, then it must be consistent. However, he then suggests that the Gödel and Henkin proofs of the completeness theorem, guaranteeing the existence of a model of T, are a sort of “accident of first order logic”, as if this were an argument for the platonist against identifying logical consistency with the existence of a model.

If S is a sentence that is false in set theory, then set theory shouldn’t imply S. But if no set – no proper part of the set-theoretical reality – could serve as a model for the entire set-theoretical reality, as seems prima facie possible, then set theory would Tarski-imply S. Again, if we are platonists we are saved from this possible extensional divergence between implication and Tarski-implication, by virtue of [the completeness theorem].

I suppose that here by “set theory” he means to refer to the collection of all true first-order statements in the language of set theory (working from a platonistic perspective). What makes this make sense is the fact that “set theory” is not recursively axiomatizable (the way ZFC or any of its standard extentions are), so Gödel’s Incompleteness Theorem doesn’t apply here. Thus, “set theory” can be a theory that implies its own consistency, and thus has models of itself inside any model. I don’t see why the Completeness Theorem is seen as somehow “accidental” and thus not reason enough for the platonist to accept the Tarski definition of implication.

Rather, what seems to me a better argument against the platonist set theorist using the Tarski definition of logical consequence (which relies on the existence of models, which are set-theoretic constructs) is that logical consequence should be prior even to set theory even for the platonist. This is certainly the case for the logicist, who says that the way we know things about the set-theoretic universe is because they are logical truths. Thus, to know that truths about sets are logical truths, we must have some way of recognizing logical truth independent of the existence of set-theoretic entities whose existence has not been justified.

I think even other non-logicist platonists would have to accept the primacy of logical consequence over set theory, because the ideas of model theory are taken to apply to models like “the actual universe of sets” rather than just set-theoretic models. This is an interesting recursivity in foundational mathematics that I have noted, that model theory talks about set-theoretic entities, while set theory assumes that we are working within a model. I think if both are taken literally, then it really is a vicious circle, but we can get out of it by making a move like the one Field argues for in a confused way, by saying that logical consequence is basic, and Tarski merely gave us an extensionally adequate analysis of it.


text:
stochastic connection相关的网络例句

# 查询词典stochastic connection

The Hausdorff measure for the level sets of multi-parameter symmetric stable processes has been obtained and the inner connection of the measures and local times for it has been demonstrated, which describes the fractal nature for the level sets of this kind of processes. As we know, it is always one of the focuses in the field of random fractal. The reasult of the existence and continuity of the local time for multi-parameter stochastic processes with stable components has been got in the project. Then we gained the measure for the random fractal sets such as the range and graph of this kind of processes. Furthermore, a progress besides the mentioned above in the project is that we have resolved the multifractal analysis of the sample paths for Brownian sheet, that is the multifractal decomposition of white noise in high dimension.

This paper developed Feynman-Kac theorem in connection with multidimensional Poisson jump-diffusion stochastic differential equation.

The distributary river course reservoir in the Lower Member of Minghuazhen Formation in an oilfield of Bohai Basin was modeled. The modeling units were divided using the integrated geological modeling method based on seismic, log and geological data. The sedimentary microfacies features of the modeling units were described. The geological knowledge base, including quantitative description of microfacies in every unit, probability function of facies, connection probability of sand body, was established. The geological model of reservoir was proposed on the basis of stochastic reservoir modeling by using an objectbased simulation method.

On the basis of exact stochastic nonlinear systems, the connection between the $L_2$-gain of the uncertain stochastic nonlinear systems and the solution to a certain HJI inequality is established.

The spread-spectrum code of CDMA isnt orthogonal strictly in a general way because the connection of the stochastic multi-user. The nonzero cross-correlation coefficient will cause multi-access interference.

I will go with you if you aren't care.

He rang the bell to call Barrymore,and asked him if he could explain the crying.

But,don't think it is the meal we need most.

5 ，但并不认为这是我们最需要的食物。

format: plain


text:
# Can I draw this diagram in Tikz?

I need to draw this (likely very simple) diagram shown in the image but I've never used Tikz before.

My problem is basiclly how to draw these vertical dotted lines and mainly arrange the math in blocks like this with these arrows pointing from one to the other - of course I have no problem writing the math, the needed structure is giving me problems. Any help would be very appreciated. Thanks in advance.

So far I was able to do this. I feel I'm almost there, but having problems with alignments. Any help?

\begin{tikzpicture}[square/.style={regular polygon,regular polygon sides=4}]

%Draw dashed lines
\draw  [dashed] (2.5,0) -- (2.5,2);
\draw  [dashed] (5,0) -- (5,2);
\draw  [dashed] (7.5,0) -- (7.5,2);

%Draw nodes of equations
\node at (1.25,1) [square,inner sep=-1.3em, draw] {
\begin{aligned} \vert \Psi \rangle &= \sum_{i}{c_i \vert a_i \rangle},\\ &\sum_{i}{\vert a_i \rangle \langle a_i \vert} = \mathds{1} \end{aligned}

};
\node at (3.75,1) [square,inner sep=-1.3em, draw] {};
\node at (6.25,1) [square,inner sep=-1.3em, draw] {};

%Draw title nodes

\node at (1.25,2) [square,inner sep=-1.3em, draw] {$\left( \mathcal{H}, \langle \cdot \vert \cdot \rangle \right)$};
\node at (3.75,2) [square,inner sep=-1.3em, draw] {$\left( \mathcal{H}_{Phys}, \langle \cdot \vert \cdot \rangle _{\eta _{+}} \right)$};
\node at (6.25,2) [square,inner sep=-1.3em, draw] {$\left( \mathcal{H}, \langle \cdot \vert \cdot \rangle \right)$};

\end{tikzpicture}

Also I don't know if this is a good approach to do what I want. Thanks.

• Welcome to TeX.SX! Please help us (and also you) and add a minimal working example (MWE). This isn't a "Please do my work for me" site! What do you have so far? Try to create ... It would help if you could just add the formula. Nov 11 '17 at 14:52
• You could use a matrix of math nodes from tikz. For details see section 57.1 of the tikz manual or search for examples on TeX.SX!
– user30471
Nov 11 '17 at 15:16
• Alright, I'm trying to work something out. Anything I'll post here. Thanks Nov 11 '17 at 15:51

With arydshln and a couple of tricks.

\documentclass{article}
\usepackage{amsmath,braket,rsfso,arydshln}

\newcommand{\blank}{{\,{\cdot}\,}}

\begin{document}

\begin{equation*}
\begin{array}{@{}c@{}c:c@{}c:c@{}}
% first column
\begin{gathered}[t]
(\mathcal{H},\braket{\blank|\blank}) \\
\ket{\psi}=\sum_i c_i\ket{a_i} \\
\sum_i \lvert a_i\times a_i\rvert = 1
\end{gathered}
&\makebox[0pt][l]{\raisebox{-2\normalbaselineskip}{$\:\longrightarrow$}}&
%second column
\begin{gathered}[t]
(\mathcal{H}_{\rho hy},\braket{\blank|\blank}_{\eta_+}) \\
\begin{aligned}
\ket{\psi}  &\to \ket{\psi'}=\sum_i c_i\rho^{-1}\ket{a_i} \\
\ket{\psi'} &\to \ket{\psi'(t)}=e^{-iHt/\hbar}\ket{\psi'}
\end{aligned}
\end{gathered}
&\makebox[0pt][l]{\raisebox{-2\normalbaselineskip}{$\:\longrightarrow$}}&
% third column
\begin{gathered}[t]
(\mathcal{H},\braket{\blank|\blank}) \\
\begin{aligned}
& \ket{\psi'} \to \ket{\psi(t)} = \rho\ket{\psi'(t)} \\
& \quad = \rho e^{-iHt/\hbar}\ket{\psi'} \\
& \quad = \rho e^{-iHt/\hbar}\rho^{-1}\ket{\psi} \\


text:
# MA 265: "Linear Algebra", Professor Alvarado, Fall 2012, Sections 011 and 071

If you create a page that belong to this course, please write

[[Category:MA265Fall2012Alvarado]]

at the bottom of the page.

OTHERWISE NO CREDIT ! (If you use the "Create a child page" button, this should happen automatically...)

Welcome!

## Homework

Please see our course webpage for homework details.

## How to get started

• Getting started
• To start, click the "Help" button above and read what's there.
• To edit pages, first log in (with your purdue account to create pages. Then click "edit" (under "Page" above) and remember to click "Save Page" after you are done editting.).
• To get a quick idea what works how, click "edit" on this page to see how to do the things visible on this page.
• Note that the "edit" mode has a spell-checking feature: look for red-underlined stuff.
• Creating pages
• To create a new page named "B" from a page A, go to edit page A and insert the text [[B]]. (Note that "B" is like a web address for a webpage. Each page also has a name, but you can call the link anything (like fancy_title) by typing [[B|fancy_title]] rather than just B. After saving, find the new red link on page A that appeared. When you click it, you'll note you are now on page B (which of course is empty at this point).
• NOTE: if the "new" link comes out blue, instead of red, you chose a title of an existing page and did not create a new one. The blue link gets you simply to the already existing one. Use distinctive names for your new creations!
• If you place "Category:MA265Fall2011Walther" enclosed by square brackets on top of a new page it will be parsed by the system as belonging to this course. It can then be searched (for) in a meaningful way.
• You can look at other Rhea pages by clicking "main page" and then "course pages". Especially the ECE pages will get you an idea where one can take Rhea...

## Your Turn! A bonus point opportunity

You have the opportunity to earn bonus points by contributing a Rhea page on a subject related to linear algebra. To pick a subject, simply write your name next to it. Please no more than one student per subject. Please do not simply copy the lecture notes and do not plagiarize. Read Rhea's copyright policy before proceeding.

Topic Number Topic Description Student Name Deadline
1 Matrix Multiplication and coordinate systems Eric Walsh At Final
2 The inverse of a matrix Your Name Here At Final
3 The determinant Dayle Alexander At Final
4 Linear dependence Your Name Here At Final
5 TESTING Your Name Here At Final
6 Subspace Jordyn McCord At Final

## Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.


text:
# Tagged: correlation

## Correlation Coeficient values lies between +1 and -1?

We know that the ratio of the explained variation to the total variation is called the coefficient of determination which is the square of the correlation coefficient. This ratio is non-negative, therefore denoted by $r^2$, thus

\begin{align*}
r^2&=\frac{\text{Explained Variation}}{\text{Total Variation}}\\
&=\frac{\sum (\hat{Y}-\overline{Y})^2}{\sum (Y-\overline{Y})^2}
\end{align*}

It can be seen that if the total variation is all explained, the ratio $r^2$ (Coefficient of Determination) is one and if the total variation is all unexplained then the explained variation and the ratio $r^2$ is zero.

The square root of the coefficient of determination is called the correlation coefficient, given by

\begin{align*}
r&=\sqrt{ \frac{\text{Explained Variation}}{\text{Total Variation}} }\\
&=\pm \sqrt{\frac{\sum (\hat{Y}-\overline{Y})^2}{\sum (Y-\overline{Y})^2}}
\end{align*}

and

$\sum (\hat{Y}-\overline{Y})^2=\sum(Y-\overline{Y})^2-\sum (Y-\hat{Y})^2$

therefore

\begin{align*}
r&=\sqrt{ \frac{\sum(Y-\overline{Y})^2-\sum (Y-\hat{Y})^2} {\sum(Y-\overline{Y})^2} }\\
&=\sqrt{1-\frac{\sum (Y-\hat{Y})^2}{\sum(Y-\overline{Y})^2}}\\
&=\sqrt{1-\frac{\text{Unexplained Variation}}{\text{Total Variation}}}=\sqrt{1-\frac{S_{y.x}^2}{s_y^2}}
\end{align*}

where $s_{y.x}^2=\frac{1}{n} \sum (Y-\hat{Y})^2$ and $s_y^2=\frac{1}{n} \sum (Y-\overline{Y})^2$

\begin{align*}
\Rightarrow r^2&=1-\frac{s_{y.x}^2}{s_y^2}\\
\Rightarrow s_{y.x}^2&=s_y^2(1-r^2)
\end{align*}

Since variances are non-negative

$\frac{s_{y.x}^2}{s_y^2}=1-r^2 \geq 0$

Solving for inequality we have

\begin{align*}
1-r^2 & \geq 0\\
\Rightarrow r^2 \leq 1\, \text{or}\, |r| &\leq 1\\
\Rightarrow & -1 \leq r\leq 1
\end{align*}

## Alternative Proof

Since $\rho(X,Y)=\rho(X^*,Y^*)$ where $X^*=\frac{X-\mu_X}{\sigma_X}$ and $Y^*=\frac{Y-Y^*}{\sigma_Y}$

and as covariance is bi-linear and X* ,Y* have zero mean and variance 1, therefore

\begin{align*}
\rho(X^*,Y^*)&=Cov(X^*,Y^*)=Cov\{\frac{X-\mu_X}{\sigma_X},\frac{Y-\mu_Y}{\sigma_Y}\}\\
&=\frac{Cov(X-\mu_X,Y-\mu_Y)}{\sigma_X\sigma_Y}\\
&=\frac{Cov(X,Y)}{\sigma_X \sigma_Y}=\rho(X,Y)
\end{align*}

We also know that the variance of any random variable is ≥0, it could be zero i.e .(Var(X)=0) if and only if X is a constant (almost surely), therefore

$V(X^* \pm Y^*)=V(X^*)+V(Y^*)\pm2Cov(X^*,Y^*)$

As Var(X*)=1 and Var(Y*)=1, the above equation would be negative if $Cov(X^*,Y^*)$ is either greater than 1 or less than -1. Hence $1\geq \rho(X,Y)=\rho(X^*,Y^*)\geq -1$.

If $\rho(X,Y )=Cov(X^*,Y^*)=1$ then $Var(X^*- Y ^*)=0$ making X* =Y* almost surely. Similarly, if $\rho(X,Y )=Cov(X^*,Y^*)=-1$ then X*=−Y* almost surely. In either case, Y would be a linear function of X almost surely.

We can see that the Correlation Coefficient values lie between -1 and +1.

## Descriptive Statistics Multivariate Data set

Much of the information contained in the data can be assessed by calculating certain summary numbers, known as descriptive statistics such as Arithmetic mean (a measure of location), an average of the squares of the distances of all of the numbers from the mean (variation/spread i.e. measure of spread or variation), etc. Here we will discuss descriptive statistics multivariate data set.

We shall rely most heavily on descriptive statistics which is a measure of location, variation, and linear association. For descriptive statistics multivariate data set, let us start with a measure of location, a measure of spread, sample covariance, and sample correlation coefficient.

### Measure of Location

The arithmetic Average of $n$ measurements $(x_{11}, x_{21}, x_{31},x_{41})$ on the first variable (defined in Multivariate Analysis: An Introduction) is

Sample Mean = $\bar{x}=\frac{1}{n} \sum _{j=1}^{n}x_{j1} \mbox{ where } j =1, 2,3,\cdots , n$

The sample mean for $n$ measurements on each of the p variables (there will be p sample means)

$\bar{x}_{k} =\frac{1}{n} \sum _{j=1}^{n}x_{jk} \mbox{ where } k = 1, 2, \cdots , p$

Measure of spread (variance) for $n$ measurements on the first variable can be found as
$s_{1}^{2} =\frac{1}{n} \sum _{j=1}^{n}(x_{j1} -\bar{x}_{1} )^{2}$ where $\bar{x}_{1}$ is sample mean of the $x_{j}$’s for p variables.

Measure of spread (variance) for $n$ measurements on all variable can be found as

$s_{k}^{2} =\frac{1}{n} \sum _{j=1}^{n}(x_{jk} -\bar{x}_{k} )^{2} \mbox{ where } k=1,2,\dots ,p \mbox{ and } j=1,2,\cdots ,p$

The Square Root of the sample variance is sample standard deviation i.e

$S_{l}^{2} =S_{kk} =\frac{1}{n} \sum _{j=1}^{n}(x_{jk} -\bar{x}_{k} )^{2} \mbox{ where } k=1,2,\cdots ,p$

### Sample Covariance

Consider n pairs of measurement on each of Variable 1 and Variable 2
$\left[\begin{array}{c} {x_{11} } \\ {x_{12} } \end{array}\right],\left[\begin{array}{c} {x_{21} } \\ {x_{22} } \end{array}\right],\cdots ,\left[\begin{array}{c} {x_{n1} } \\ {x_{n2} } \end{array}\right]$
That is $x_{j1}$ and $x_{j2}$ are observed on the jth experimental item $(j=1,2,\cdots ,n)$. So a measure of linear association between the measurements of  $V_1$ and $V_2$ is provided by the sample covariance
$s_{12} =\frac{1}{n} \sum _{j=1}^{n}(x_{j1} -\bar{x}_{1} )(x_{j2} -\bar{x}_{2} )$
(the average of product of the deviation from their respective means) therefore

$s_{ik} =\frac{1}{n} \sum _{j=1}^{n}(x_{ji} -\bar{x}_{i} )(x_{jk} -\bar{x}_{k} )$;  i=1,2,..,p and k=1,2,\… ,p.

It measures the association between the kth variable.

Variance is the most commonly used measure of dispersion (variation) in the data and it is directly proportional to the amount of variation or information available in the data.

### Sample Correlation Coefficient

The sample correlation coefficient for the ith and kth variable is

$r_{ik} =\frac{s_{ik} }{\sqrt{s_{ii} } \sqrt{s_{kk} } } =\frac{\sum _{j=1}^{n}(x_{ji} -\bar{x}_{j} )(x_{jk} -\bar{x}_{k} ) }{\sqrt{\sum _{j=1}^{n}(x_{ji} -\bar{x}_{i} )^{2} } \sqrt{\sum _{j=1}^{n}(x_{jk} -\bar{x}_{k} )^{2} } }$
$\mbox{ where } i=1,2,..,p \mbox{ and} k=1,2,\dots ,p$

Note that $r_{ik} =r_{ki}$ for all $i$ and $k$, and $r$ lies between -1 and +1. $r$ measures the strength of the linear association. If $r=0$ the lack of linear association between the components exists. The sign of $r$ indicates the direction of the association.

# High Correlation does not Indicate Cause and Effect

The correlation is a measure of the co-variability of variables. It is used to measure the strength between two quantitative variables. It also tells the direction of a relationship between the variables. The positive value of the correlation coefficient indicates that there is a direct (supportive or positive) relationship between the variables while the negative value indicates there is negative (opposite or indirect) relationship between the variables.

By definition, the correlation is interdependence between two quantitative variables. The causation (known as) cause and effect, is when an observed event or action appears to have caused a second event or action. Therefore, It does not necessarily imply any functional relationship between variables concerned. Correlation theory does not establish any causal relationship between the variables as it is interdependence between the variables. Knowledge of the value of the coefficient of correlation r alone will not enable us to predict the value of Y from X.

Sometimes there is the high correlation between unrelated variable such as the number of births and numbers of murders in a country. This is a spurious correlation.

For example, suppose there is a positive correlation between watching violent movies and violent behavior in adolescence. The cause of both these could be a third variable (extraneous variable) say, growing up in a violent environment which causes the adolescence to watch violence related movies and to have violent behavior.

Other Examples

• The number of absences from class lecture decreases the grades.
• As the weather gets colder, air conditioning costs decrease.
• As the speed of the train (car, bus, or any other vehicle) is increased the length of time to get to the final point will also decrease.
• As the age of a chicken increases the number of eggs it produces also decreases.

## Partial Correlation: Another measure of relationship

It measures the relationship between any two variables, where all other variables are kept constant i.e. controlling all other variables or removing the influence of all other variables. The purpose of partial correlation is to find the unique variance between two variables while eliminating the variance from the third variable. The technique of partial correlation is commonly used in “causal” modeling fewer variables. The partial correlation canadian pharmacy coefficient is determined in terms of the simple correlation coefficient among the various variables involved in multiple relationships. The assumption for partial correlation is the usual assumptions of Pearson Correlation:

1. Linearity of relationships
2. The same level of relationship throughout the range of the independent variable i.e. homoscedasticity
3. Interval or near-interval data, and
4. Data whose range is not truncated.

We typically conduct correlation analysis on all variables so that you can see whether there are significant relationships amongst the variables, including any “third variables” that may have a significant relationship to the variables under investigation.

This type of analysis helps to find the spurious correlations (i.e. correlations that are explained by the effect of some other variables) as well as to reveal hidden correlations – i.e correlations masked by the effect of other variables. The partial correlation coefficient $r_{xy.z}$ can also be defined as the correlation coefficient between residuals dx and dy in this model.

Suppose we have a sample of n observations $(x1_1,x2_1,x3_1),(x1_2,x2_2,x3_2),\cdots,(x1_n,x2_n,x3_n)$ from an unknown distribution of three random variables and we want to find the coefficient of partial correlation between $X_1$ and $X_2$ keeping $X_3$ constant which can be denoted by $r_{12.3}$ is the correlation between the residuals $x_{1.3}$ and $x_{2.3}$. The coefficient $r_{12.3}$ is a partial correlation of the 1st order.

$r_{12.3}=\frac{r_{12}-r_{13} r_{23}}{\sqrt{1-r_{13}^2 } \sqrt{1-r_{23}^2 } }$

The coefficient of partial correlation between three random variables X, Y and Z can be denoted by $r_{x,y,z}$ and also be defined as the coefficient of correlation between $\hat{x}_i$ and $\hat{y}_i$ with
\begin{align*}
\hat{x}_i&=\hat{\beta}_{0x}+\hat{\beta}_{1x}z_i\\
\hat{y}_i&=\hat{\beta}_{0y}+\hat{\beta}_{1y}z_i\\
\end{align*}
where $\hat{\beta}_{0x}$ and $\hat{\beta_{1x}}$ are the least square estimators obtained by regressing $x_i$ on $z_i$ and $\hat{\beta}_{0y}$ and $\hat{\beta}_{1y}$ are the least square estimators obtained by regressing $y_i$ on $z_i$. Therefore by definition, the partial correlation between of $x$ and $y$ by controlling $z$ is $r_{xy.z}=\frac{\sum(\hat{x}_i-\overline{x})(\hat{y}_i-\overline{y})}{\sqrt{\sum(\hat{x}_i-\overline{x})^2}\sqrt{\sum(\hat{y}_i-\overline{y})^2}}$

The partial correlation coefficient is determined in terms of the simple correlation coefficients among the various variables involved in a multiple relationship.

Reference
Yule, G. U. (1926). Why do we sometimes get non-sense correlation between time series? A study in sampling and the nature of time series. J. Roy. Stat. Soc. (2) 89, 1-64.


text:
# [10,20] is a Problem!

Algebra Level 4

$\displaystyle S_n = \sum _{ r=1 }^{ n }{ \big[(r-10)(r-20) \big] }$

Given the above function of $$S_n$$, what does the summation below equal to?

$\displaystyle \sum _{ r=1 }^{ 50 } \big|(r-10)(r-20)\big|$

×


text:
# SOLUTION: Prove by induction that 2^n>=n^2. I was stocked at the induction step when 2^(k+1)>=2k^2

Algebra ->  Algebra  -> Geometry-proofs -> SOLUTION: Prove by induction that 2^n>=n^2. I was stocked at the induction step when 2^(k+1)>=2k^2      Log On

 Ad: Algebra Solved!™: algebra software solves algebra homework problems with step-by-step help! Ad: Algebrator™ solves your algebra problems and provides step-by-step explanations!

 Geometry: Proofs in Geometry Solvers Lessons Answers archive Quiz In Depth

 Question 527962: Prove by induction that 2^n>=n^2. I was stocked at the induction step when 2^(k+1)>=2k^2Answer by richard1234(5390)   (Show Source): You can put this solution on YOUR website!The induction basically claims that if for some k > 1, if , then . Since , we can construct the inequality The inequality is equivalent to It factors to , which is true for sufficiently large k (it doesn't hold for k = 0,1,2 but we can check these cases separately).


text:
## Archive for the ‘MySQL’ Category

### RIGHT OUTER JOIN example

Thursday, July 5th, 2018

Another simple query. I have a list of vocabulary words with their definitions. I found a usage that clearly expressed the meaning of the word and put it in a different table. When I was nearly done I wanted to make sure that all of the words had at least one usage example. This is the code that does it.

SELECT words.word, words_usage.word
FROM words_usage
RIGHT OUTER JOIN words
ON words_usage.word = words.word
WHERE words_usage.word IS NULL
ORDER BY words_usage.word ASC

### Updating table with values from another table

Friday, January 19th, 2018

I have a database of interesting words on my server that has pronunciations and definitions. On another server, I want to create a database of boring words. Since there is some overlap, I thought I would save some time and populate the new database with pronunciation and definitions from the old one. It is fairly straightforward, just remember to put in the commas to separate the where conditions. I’m using phpMyAdmin and while I don’t think the backtics are required, I go in the habit of using them from writing PHP code. Even though you are only updating one table, you need to put both in the update line.

UPDATE boring_words,  interesting_words
SET boring_words.pronunciation = interesting_words.pronunciation,
boring_words.definition = interesting_words.definition,
boring_words.comment = interesting_words.comment
WHERE boring_words.word = interesting_words.word;

### A note on PDO prepared statements

Friday, May 13th, 2016

It wasn’t obvious to me that you need to have a different bindParameter statement each time you use a variable in the query. This won’t work.

// query for title information
$qry = "SELECT * ";$qry .= "FROM website_database.product, website_database.product_instance ";
$qry .= "WHERE product.id = :productID ";$qry .= "AND product_instance.product_id = :productID";

$stmt =$dbWG->prepare($qry);$stmt->bindParam(':productID', $productID);$stmt->execute();

MySql doesn’t look for every instance of :productID in the query and substitute $productID. This is how you do it:  // query for title information$qry  = "SELECT * ";
$qry .= "FROM website_database.product, website_database.product_instance ";$qry .= "WHERE product.id = :productID1 ";
$qry .= "AND product_instance.product_id = :productID2";$stmt = $dbWG->prepare($qry);
$stmt->bindParam(':productID1',$productID);
$stmt->bindParam(':productID2',$productID);
$stmt->execute(); ### Sanitizing Database Query Input Friday, May 13th, 2016 As part of my site rewrite and migration to MySQL PDO I am making sure that all of the input is sanitized before using—which has the side effect of stopping injection attempts, as discussed in the previous post—and either using prepared statements or whitelisted inputs. Here’s the sanitizing portion of a crossword solver page. The input is the number of letters in the word and up to 14 letters. There should only be one letter in each space, the space can be empty, and the numbers can be from 1 to 14. I haven’t had any attacks on my forms yet, so I’ll assume any invalid input is due to fat fingers and make reasonable changes.  <?php$MAX_LETTERS = 14;
$letters = array(); // Read in the letters and number of letters first so you can repopulate the fields. // If it’s not a single letter in the letter field, or a valid number in the number field, // don’t let it into the query. // Log it in case we get lots of injection attempts. if(isset($_POST)) {
$submitType =$_POST['submitType'];

if ($submitType != 'Clear') { // Get and validate letters for($i = 1; $i <=$MAX_LETTERS; $i++) {$letters[$i] =$_POST['letter' . $i];$letters[$i] = str_replace(" ","",$letters[$i]); if (!preg_match("/^[a-zA-Z]$/",$letters[$i]) && ($letters[$i] <> '') ) {
if ($showError) error_log("Not a letter {$letters[$i]} in$calledFileName");
$letters[$i] = "";
}
}
// Get and validate the number of letters
$num_letters = (integer)$_POST['num_letters'];
if (!is_integer($num_letters) ) { if ($showError) error_log("Not a number in $calledFileName"); }$num_letters = (integer)$num_letters; if ($num_letters > $MAX_LETTERS ) {$num_letters = $MAX_LETTERS; if ($showError) error_log("Too many numbers in $calledFileName"); } else if ($num_letters < 0 ) {
$num_letters =$num_letters * -1;
if ($showError) error_log("Negative number in$calledFileName");
}
}
}

Note that I don’t use htmlspecialchars or mysql_real_escape_string when getting input because I explicitly allow only letters or numbers when validating the output. I don’t think that they would hurt anything, but they aren’t necessary.

$letters[$i] = htmlspecialchars($_POST['letter' .$i]);
$letters[$i] = mysql_real_escape_string($_POST['letter' .$i]);

Some of my pages allow more than one letter in each input space. I just add .* to the pre_match to allow more than one letter. I also allow a wildcard, *, in the web page so I need to escape it in the pre_match.

if (!preg_match("/[a-zA-Z\*].*/",$letters[$i]) && ($letters[$i] <> '') ) {

The safest way to sanitize input is to whitelist the query. There are lots of ways to do this. One way is to construct the query based on the input.

switch ($loc) { case "I": case "i":$location = "Initial";
$searchString = "^{$letters}[A-Z ]*";
break;
case "M":
case "m":
$location = "Medial";$searchString = "[A-Z ]+{$letters}[A-Z ]+"; break; case "F": case "f":$location = "Final";
$searchString = "[A-Z ]*{$letters}\$"; break; ..... The user provides a location—initial, medial, or final—and I construct the search string based on their input. No injection is possible because the user input is not seen by the search query. Another example of whitelisting is to only allow certain values. It works if the list is small and not changed often.  if ($input == 'first value' || $input == 'second value' ||$input == 'third value') {
-- do stuff with the database
} else {
include_once('dieInAFire');
}

You can do something similar by checking whether the input is part of a hard-coded array. The problem with the last two approaches is that they only work well if the list of acceptable values doesn’t change often. They can work to sanitize user input for things like states and provinces, occupation, and taxable status.

### More Thoughts on SQL Injection Attacks

Friday, May 13th, 2016

As I discussed in an earlier post, my sites are frequently attacked by malicious actors trying to get into my database by using SQL injection techniques. I stopped most of them by doing input validation and if the input fails validation, returning a 404 not found. I didn’t do this on all of my pages so from time to time they find a page that does”t fail with bad input and send thousands of page requests to it.

I recently updated my sites and took the opportunity to familiarize myself with the latest best practices for mitigating attacks. I added a line to my database initialization script, sanitize all inputs, and use either prepared statements or queries that use whitelisted terms. Here’s my current initialization script.

<?php

$user = 'mysql_user';$pass = 'supersecurepasswors';
$host = 'localhost';$db_name = 'website_database';

try {
$dbWG = new PDO("mysql:host=$host;db_name=$dbname",$user, $pass, array(PDO::MYSQL_ATTR_INIT_COMMAND => "SET NAMES utf8") );$dbWG->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
$dbWG->setAttribute(PDO::ATTR_DEFAULT_FETCH_MODE, PDO::FETCH_ASSOC);$dbWG->setAttribute(PDO::ATTR_EMULATE_PREPARES, false);
}
catch(PDOException $e) {$e->getMessage();

The only way I found to get attacks to stop is to return a 404 not found message to the bot. After a few tries they usually give up. Otherwise they will try thousands of times.

So first I sanitize the input. Here’s a simple one where the input has to be a digit:

$number_of_letters = (isset($_GET['n']) ? $_GET['n'] : 1); if ( !is_numeric($number_of_letters) ) {
include_once('dieInAFire.inc');
}

I have a $showError variable in my header that lets me turn off and on information on attacks. I usually leave it on and peruse the error log to make sure legitimate requests aren’t accidentally blocked. I wrote this include file to use after sanitizing inputs fails.  <?php$url = isset($_SERVER['REQUEST_URI']) ?$_SERVER['REQUEST_URI']  : '';
$ref = isset($_SERVER['HTTP_REFERER']) ? $_SERVER['HTTP_REFERER'] : '';$ip  = isset($_SERVER['REMOTE_ADDR']) ?$_SERVER['REMOTE_ADDR']  : '';

if ($showError == TRUE) { error_log("Long string in$calledFileName: URL is $url and IP is$ip & ref is $ref"); } header("HTTP/1.0 404 Not Found"); die(); ?> Note that this has to be called before the statement. If it is a legitimate request, I make then use a prepared statement to execute it. $qry.=  "HAVING COUNT(sorted_letters) > :number_of_letters ";

$stmt =$dbWG->prepare($qry);$stmt->bindParam(':number_of_letters', $number_of_letters);$stmt->execute();


text:
# Tag Info

70

Probably you already have it, and just didn't know it. If you are driving a motor with a half-bridge or H-bridge and PWM or similar, you have regenerative braking. Let's consider a half-bridge, since for this analysis we will run the motor in only one direction: First, let's consider non-regenerative braking. If the bridge output is high (S1 closed, S2 open)...

42

In short: You have linear control of the 'speed' by applying a pwm signal, now the frequency of that signal has to be high enough so that your DC Motor only passes the DC component of the PWM signal, which is just the average. Think of the motor as a low pass filter. If you look the transfer function or relationship angular speed to voltage, this is what ...

19

For low voltages, it seems like the DRV8837 is pretty good: - With an 800mA load, the volt drop is: - $I_O\cdot R_{OS(ON)}$ = 800mA x 0.33 ohms = 0.264 volts. At this current, the power dissipation will be 0.8 x 0.8 x 0.33 watts = 211 mW. Compare this with the L293 power dissipation at about 800mA - maybe about 3V is lost giving rise to a power ...

19

Not a ground loop. But a short circuit: Always use fuses with batteries. Instead, you can make it like this, so that there is only one common ground: Drawback is unbalanced load on the battery. Meaning the left battery depletes faster, possible damaging it when the set is deep discharged. I recommend a battery balancer, or a 24V-12V power supply instead.

16

Each pin on an Arduino can handle 40 milli amperes, not 40 Amperes. That too in ideal conditions (temperature, Vcc), actual allowable current can be a fair bit lower. Besides current limitation of the Arduino pins, a key failure condition is the LDO voltage regulator on the Arduino board, which will overheat and can get destroyed if it is made to source high ...

16

The PWM frequency supplied to a (presumably) brushed DC motor needs to be high enough that the combination of mechanical inertia and inductance of the coils is sufficient to smooth out the mechanical impulses of each pulse. This minimum would differ from motor to motor. Too low a frequency, and the motor motion will be perceived as a series of jerks, or a ...

15

The triangle is a symbol for a buffer, driver or amplifier, whatever you call it. The transistors drawn inside the triangle are there to let you know what is the type of your output. Thanks to this drawing you can see that the outputs are switched via BJTs between the power supply rails using some kind of Push-Pull topology. Knowledge about the type of ...

15

Flogging the FREDs Voltage fed converters with transformer isolation will exhibit ringing in the secondary. Ringing is caused by parasitic inductances and capacitances in the circuit, with the dominant elements will being the transformer leakage inductance ($L_ {\text {Lk}}$) and junction capacitance ( $C_j$)of the bridge diodes. The diode data ...

15

Recently, I bought the H-Bridge VNH7070BAS from ST because it would drive up to 15A It will not drive anything like this level of current for anything more than a few micro seconds before the automatic current limit circuit operated. The internal transistors together contribute circa 0.1 ohm impedance in the current path and, at (say) 10 amps continuous, ...

12

I think you will encounter two challenges in designing this. The first is getting the high side to turn on. The source of the high-side moves up and down relative to ground, so a voltage source referenced to ground won't be able to drive it without exceeding the maximum gate-to-source voltage $V_{GS}$. For RFG50N06, this is 20V. The second is that you ...

12

Try probing on the power supply rail. I bet you see those spikes on there. It'll be due to the lead length between your bench supply and the MOSFETs. Clearly you won't see it on the lower FET side because your scope is referenced to that rail but, if you probed back at the power supply I bet you would. Try a 1uF or 10uF ceramic across the power rails close ...

12

The diodes serve two distinct purposes. Under regenerative braking, they return the generated voltage to the power supply (where with suitable electronics, it can be used to recharge the battery). Note that unless the motor is being run above its normal speed, the generated voltage will be no more than the supply voltage, so it is within the voltage rating ...

11

Your first concern in selecting a gate driver is to find one that can drive enough current to switch your selected MOSFETs fast enough for your application. As a rough estimation, you can divide the total gate charge of your MOSFET by the current the driver can sink/supply. $$t_{on}=\frac{Q_g}{I_g}$$ Using the worst-case values for IRF1405 and the slower ...

11

At minimum, you need to use a frequency so that the motor "sees" the average and doesn't react to individual pulses. That is usually a few 100 Hz. However, there are other effects that the motor doesn't care about but you might. Individual sections of wire in the windings may vibrate slightly with the PWM frequency, which causes audible whine. This is ...

11

How are you decoupling the 12V supply? One possible failure mode is that inductive spikes from switching off the motor current (i.e. at the PWM rate) are dumped into the 12V supply via the flyback diodes. Yes, that's supposed to happen, but... If the 12V supply is not decoupled, and is sourced from a PSU not a rechargeable battery, or is sourced via a long ...

11

Your motor is likely geared down, because 150 rpm is only 2.5 revolutions per second. At 50 rpm, your motor will require more than a second to perform one revolution. That having been said, the switches in your h-bridge don't dissipate much power when they are on (essentially zero volts) or when they are off (zero current). They only have both voltage and ...

10

A TEC is polarized in the sense that how it is connected matters. If you want to be able to heat and cool an element then a full Hbridge will work. This will allow you to pump current both directions across a TEC's terminals. If you apply a positive voltage to a TEC in one polarization then side A will get warm and side B will cool. If you then reverse ...

10

I first saw the following circuit in a TI app note many years ago. It works well and is robust. I have used it or variations of it in several projects (and products). simulate this circuit – Schematic created using CircuitLab There are a couple of things to consider: 1) This circuit inverts the drive signal. 2) R3 is added to ensure the FET drive ...

10

To use this circuit with a 12V supply R5 & R6 must be rated for at least 0.25W power and the 100 ohm resistors must be rated for at least 2W power. Depending on the transistors used these 4 resistors (100 ohm) may need recalculation to avoid excessive base current and power dissipation. However this circuit will not work. One problem is that it ...

10

If the motor is producing power, the net power into the motor must be positive, so the net current out of the batteries must be in the direction that drains them, so you are fine. If the motor is being regeneratively braked, then power can flow out of the motor and can push the supply voltage up and charge the batteries (this is used to advantage in ...

10

On your layout the decoupling cap (finger-painted red) is very far away from the chip, there is a 5R resistor in series (purple) and the current loop area (highlighted in yellow) is quite large. This large loop area adds inductance to the power supply impedance as seen from the chip. Wet finger in the wind, about 10-20 nH. With a di/dt around 1A per 1-2ns ...

9

This is a classic snubbering problem. A diode can't instantaneously go from conduction to blocking; the charge in the PN junction needs to get swept out, and an RC snubber across each diode should help this. I used to design industrial soft starters and on the medium-voltage units we had a lot of design work around this particular aspect. It's been a long ...

9

The reasons are different depending on if it is a BJT or a MOSFET. The effect, though, is the same - it's there to reduce current and protect the IO pins on the controller that are driving the transistors. On the BJT the base -> emitter junction is essentially like a diode, and without a resistor would be like a near short circuit. The resistor stops the ...

9

P-channel MOSFETs tend to have a higher Rds(on), making them less efficient (for the same price). For a small H-bridge, the simplicity of using them makes them practical However, for high power applications, the extra complexity of driving N channel FETs can be justified by improved efficiency from lower Rds(on).

9

Your P channel MOSFETs are connected upside down: - Notice the little diode symbols inside the MOSFETs? They will permanently conduct current and the MOSFETs will not switch off.

9

Those old bipolar processes could only be used to make crummy lateral PNP transistors with quite low gain so not very good for high current. Using all NPN, especially those NPN, transistors is bad (because of the extra Vbe drop), but not as bad as it would be with monolithic PNPs. Popular? Probably for legacy applications and hobbyists, but I doubt any ...

8

Can it be done? Yes Has it been done? Yes Will it do as expected? half the switching losses? Yes & if care was taken over the right-leg device selection trading speed for conduction losses then you could further improve the powerCore losses. Quick model with some REALLY badly optimised output filter & not really tuned, just to prove a point &...

8

A practical motor behaves roughly like a resistor and inductor in series with a real motor. For efficient operation you need should switch between connecting the motor to the supply and shorting it out. While the motor is connected to the supply, the current will become more positive. When shorted, it will become more negative. Efficiency will go ...

8

Your o-scope time base is set to 1.00 seconds and, by the looks of it your control signals will be switching at 0.5 Hz. This is waaaaaaaaaaay too low in frequency. You have (in your driver circuit) bootstrap components that help give good drive signals to your upper N channel MOSFETs but, these bootstrap circuits can only work when you have sufficient drive ...

7

That is just a notation, not by any means a schematic. The "triangles" themselves symbolise high current drivers, the two "transistors" drawn there are just to symbolise what the circuit is doing. There more components "inside the triangle", that for sake of brevity are not displayed. This is similar to pseudocode and real source code in a given ...

Only top voted, non community-wiki answers of a minimum length are eligible