Wikipedia:Reference desk/Archives/Mathematics/2018 December 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 6

Confidence intervals/error bars on fit parameters

Original problem: I have N experimental observations of a certain phenomenon; the i-th experimental observation consists of a certain number of repetitions of the experiment at a parameter $x=x_{i}$, and from that I extracted the sample mean and standard deviation of the result $y_{i},\sigma _{i}$. I know a predicted linear relationship between the parameter and the result: $y=k(x-x^{0})$. I want to use the experimental data to extract the parameters' values $k,x^{0}$ and the uncertainty affecting those.

What I tried so far: get the fit parameters by least squares weighted by the reverse of the uncertainty on each point; that is, find $k,x^{0}$ as the values that minimize $\sum _{i=1}^{N}{\frac {\left(k(x_{i}-x^{0})-y_{i}\right)^{2}}{\sigma _{i}^{2}}}$. That does give an estimation of the parameters, but not uncertainty bounds on them. Intuitively I would look at what $k+\delta k$ produces a "large" value for the weighted least squares but I do not really know how to properly do it and I am sure it has already been done before by my Google-fu was weak.

I have already read reduced chi-squared statistic which is close but not what I want. Tigraan^{Click here to contact me} 15:20, 6 December 2018 (UTC)

You are doing a weighted least squares estimation of $k$ and $x^{0}$ in

$y_{i}=kx_{i}-(kx^{0})$

with intercept term $kx^{0}.$ The estimate for k is simply the estimated coefficient of $x_{i},$ and its variance is the variance of that estimated coefficient, which is standard in regression output. We need to find the variance of $x^{0}$ given the variances of k and of the estimated intercept. I would think that you could state the variance of the estimated intercept as a probability-weighted average of the possible values of k times the variance of $x^{0}$:

$var(intercept)=\int _{-\infty }^{\infty }f(k)\cdot var(x^{0})dk=var(x^{0})\cdot \int _{-\infty }^{\infty }f(k)dk=var(x^{0}),$

where f(k) is the probability density of k, inferred from the regression by the estimated variance of k and a normality assumption on k. Then the only unknown in this equation is the desired var($x^{0}$), which the equation says equals the variance of the intercept. Does any of that make any sense? Loraof (talk) 19:53, 6 December 2018 (UTC)

I am not sure it makes sense, but the link to Weighted_least_squares#Parameter_errors_and_correlation was all I neeeded. Thanks! Tigraan^{Click here to contact me} 11:04, 10 December 2018 (UTC)

I think that you can find all answers in Simple linear regression. Ruslik_Zero 20:00, 8 December 2018 (UTC)

No, because it does not deal with the case of data with error bars. The fit parameters are the same for the dataset {(0,0±0.0001), (1,1±0.0001)} than for {(0,0±0.0001), (1,1±0.1)} but intuitively the latter should have a much larger uncertainty on the proportionality coefficient. (I could scrap the uncertainty and fit the whole set of experimental data with multiple points per parameter value, but I have some reason to expect measurement uncertainty to be higher for some values of the parameter than others.) Tigraan^{Click here to contact me} 11:04, 10 December 2018 (UTC)

See weighted least squares. Ruslik_Zero 20:48, 10 December 2018 (UTC)

Minimal CNF form

Is the following statement correct:

Let $\varphi$ be a formula in CNF form over the set of variables $X$.

Assume that:

1. For every clause all of its variables appear in their positive form. (that is, no $\neg x$ in the $\varphi$)
2. Every two clauses $c_{1},c_{2}$ of $\varphi$, satisfy $c_{1}\not \subseteq c_{2}$ ($c_{1}$ is not a subset of $c_{2}$)

Then $\varphi$ is in its minimal CNF form (there's no equivalent CNF formula with smaller size) David (talk) 18:58, 6 December 2018 (UTC)

I believe (A∨B)∧(¬A∨¬B)∧(A∨C)∧(¬A∨¬C)∧(B∨C)∧(¬B∨¬C) has the form you describe, but it's equivalent to False or (A)∧(¬A). Pretty sure that if there was a rule like this then you'd be able to solve SAT in polynomial time, and if such a scheme existed it's extremely unlikely it wouldn't have been found already. --RDBury (talk) 05:51, 7 December 2018 (UTC)

First, it's a good counterexample, so I changed my question, and replaced it with a stronger condition, under which I hope we can promise it's the minimal CNF form.

Second, I agree that one can't expect to get a method that works in general that decides whether or not a given formula is in its minimal CNF form (for then, SAT were in P). Nevertheless, there could be many methods for deciding in some special cases if they're in their minimal CNF form. David (talk) 12:48, 7 December 2018 (UTC)

Just for clarity, the original conditions were:

Assume that every two clauses $c_{1},c_{2}$ of $\varphi$, satisfy:

1. $c_{1}\not \subseteq c_{2}$ ($c_{1}$ is not a subset of $c_{2}$)
2. $\forall x\in X.c_{1}\Delta c_{2}\neq \{x,\neg x\}$ (the symmetric difference of $c_{1}$ and $c_{2}$ is not equal to any variable and its negation).

You may have had no way of knowing this, but in general it's better to just strikethrough material in your previous posts rather than deleting; especially if someone has already replied to the original. If you're just fixing a typo or something that doesn't change the meaning then don't worry about it; WP does have a habit of inserting typos into what people have written after they hit the 'Publish' button.

The example is basically just a Boolean version of the statement '2 divides 3', so not that hard to dome up with if you're used to this type of conversion. The new version of the question appears in a StackExchange post. The only response missed the 'positive' part of the question, so as far as I know it's still unanswered. --RDBury (talk) 15:16, 7 December 2018 (UTC)

PS. I think I have a proof that, given the positive condition, the minimal expression is unique. It's not that hard so I'm a bit surprised the StackExchange people didn't find it, or maybe it's just that my proof is incorrect. In any case I'll write it up and post it in a bit. --RDBury (talk) 15:50, 7 December 2018 (UTC)

Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {S_i} be the set of clauses in S and {T_j} be the set of clauses in T. Each S_i and T_j, in turn, correspondes to a subset of a set of Boolean variables {x_k}. Since S is minimal, no S_i is contained in S_j for j≠i, and similarly for T. For each assignment a:x_k → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause S_i evaluates to F iff S_i⊆Z(a) and the expression S evaluates to F iff S_i⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment a_i(x_k) to be 'T' when x_k is not in S_i, in other words a_i is the truth assignment so that Z(a_i) = S_i. The clause S_i evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore T_j⊆Z(a_i)= S_i for sime j. Similary, for each j there is k so that S_k ⊆ T_j.(I think another way of saying this is that S and T are refinements of each other.) If S_i is an element of S, then there is T_j in T so that T_j ⊆ S_i, and there is an S_k so that S_k ⊆ T_j. Then S_k ⊆ S_i and so, since S is minimal, i=k. We then have S_i ⊆ T_j ⊆ S_i, S_i = T_j ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T. --RDBury (talk) 17:04, 7 December 2018 (UTC)

The proof sounds great, so I beleive it's correct. Thank you! David (talk) 20:15, 10 December 2018 (UTC)