text:
# The existential theory is undecidable

Lemma 1.

For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and $t-1$ divides $x-1$ (the divisibilities are meant, of course, in $F[t, t^{-1}]$).

Lemma 2.

Assume that the characteristic of $F$ is zero. Then for any $n$ in the ring $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $n$ is a nonzero integer if and only if $n$ divides $1$ and either $n-1$ divides $1$ or $n+1$ divides $1$, and there is a power $x$ of $t$, so that $(x-1)/(t-1) \equiv n \pmod {t-1}$.

THEOREM.

Assume that the characteristic of $F$ is zero. Then the existential theory of $F[t, t^{-1}]$ in the language $\{+, \cdot , 0, 1, t\}$ is undecidable.

PROOF.

By Lemma 1, we can express the fact that an element $x$ in $F[t, t^{-1}]$ is a power of $t$ by an existential formula $\phi(x)$.

By this and Lemma 2, we can express the fact that an element $n$ of $F[t, t^{-1}]$ is an integer by the existential formula $$(\exists x)(\exists y) [\phi (x) \wedge x-1 = (t-1)n+y(t-1)^2] \wedge (\exists z)(\exists w) (nz =1 \wedge ((n+1)w=1 \text{ or } (n-1)w=1)$$ Call the last formula $\psi(n)$.

Assume for the sake of contradiction, that the existential theory of $F[t, t^{-1}]$ is decidable.

Then we can algorithmically examine the solvability of a diophantine equation in the rational integers in the following way:

if $P(X_1, \dots , X_n)=0$ is a given diophantine equation, we consider the existential formula $$(\exists x_1) \dots (\exists x_n) P(x_1, \dots , x_n)=0 \wedge \psi(x_1) \wedge \dots \psi(x_n)$$

Clearly, the equation of whether this sentence is true in $F[t, t^{-1}]$ is equivalent to the question of whether $P=0$ has integral solutions. But this contradicts the negative answer to Hilbert's Tenth Problem; therefore, the theorem follows.

Could you explain to me the formula $\psi(n)$ ?

Could you explain to me the reduction to Hilbert's Tenth Probelm? I haven't really understood it...

EDIT:

Can we change the theorem and its proof as follows?

THEOREM.

We suppose that the characteristic of $F$ is zero. Then the positive existential theory of $F[t, t^{-1}]$ in the language $\{+, \cdot , 0, 1, t\}$ is undecidable.

Proof. We want to show that there is no algorithm, that given a positive existential sentence $\gamma$, it answers if $\gamma$ is true in the ring $F[t, t^{-1}$ or not. According to Matijasevic, there is no algorithm that with input a polynomial $P(x_1, \dots , x_n)$ with integer coefficients, always decides if the equation $P(X-1, \dots , x_n)=0$ has an integer solution. According to Lemma $1$, an element $x \in F[t, t^{-1}]$ is a power of $t$ iff $$x \mid 1 \ \ \land \ \ t-1 \mid x-1$$ So we can express the fact that an element $x \in F[t, t^{-1}]$ is a power of $t$ with the positive existential formula $$\phi (x) \ \ : \ \ \exists y \exists z ((xy=1) \land (x-1=(t-1)z))$$ According to Lemma $3$, $n$ is a nonzero integer iff

• $n \mid 1 \ \ : \ \ (\exists z)(nz=1)$
• $n-1 \mid 1 \lor n+1 \mid 1 \ \ : \ \ (\exists w)((n+1)w=1 \text{ or } (n-1)w=1)$
• there is a power $x$ of $t$ $\ \ : \ \ (\exists x) \phi (x)$
• $(x-1)/(t-1) \equiv n \pmod {t-1} \ \ : \ \ (\exists y)((x-1)/(t-1)-n =y(t-1)) \Rightarrow (\exists y)(x-1-n(t-1)=y(t-1)^2) \Rightarrow (\exists y)(x-1=n(t-1)+y(t-1)^2)$

So we can express the fact that an element $n \in F[t, t^{-1}]$ is an integer with the positive existential formula $$\psi (n) \ \ : \ \ (\exists x)(\exists y)[\phi(x) \land x-1=(t-1)n+y(t-1)^2] \land (\exists z)(\exists w)(nz=1 \land ((n+1)w=1 \text{ or } (n-1)w=1)$$ We suppose that the positive existential formula of $F[t, t^{-1}]$ is decidable, so there is an algorithm that decides if a positive existential sentence is true in $F[t, t^{-1}]$. Then the problem if a diophantine equation has an integer solution is decidable: the diphantine equation $P(x_1, \dots , x_n)=0$ has an integer solution iff the positive existential sentence $$(\exists x_1) \dots (\exists x_n) ((\psi (x_1) \land \dots \land \psi (x_n)) \land P(x_1, \dots , x_n)=0)$$ is true in $F[t, t^{-1}]$. But the answer to the $10^{th}$ Hilbert's Problem, i.e., if there is an algorithm that decides if the diophantine equation has an integer solution, is negative. So we have a contradiction. That means that the positive existential theory of $F[t, t^{-1}]$ is undecidable.

• Because of my background, this stuff is easy for me, a standard reduction to Hilbert's 10th. I had noticed it but have no time for a while. Am bookmarking, and if no one else has given a full answer by the time I get to it, I will write out an answer. Jul 27 '15 at 20:42
• Ok!! @AndréNicolas Jul 27 '15 at 20:44
• it would be helpful if you cite ref, pg
– vzn
Jul 27 '15 at 21:41
• It is from this paper: jstor.org/stable/2275396?seq=1#page_scan_tab_contents @vzn Jul 27 '15 at 23:00

We explain the reduction, and later, if questions arise, explain $\psi$.

A formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it has the shape $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l),\tag{1}$$ where the formula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ is quantifier-free. Sometimes, informally, as in the definition you quote for $\psi(n)$, the term existential formula is used for formulas that can be mechanically put in the form (1). (Note that as given, the existential quantifiers are not all in front.)

Let $F$ be a field of characteristic $0$. We want to show that there is no algorithm which, given any existential sentence $\gamma$, will tell us whether or not $\gamma$ is true in the ring $F[t,t^{-1}]$.

By the result that culminated in the work of Matijasevic, there is no algorithm which, when given as input a polynomial $P(X_1,\cdots,X_n)$ with integer coefficients, will always determine whether or not the equation $P(X_1,\dots,X_n)=0$ has a solution in integers.

We show that if there were an algorithm for determining the truth in $F[t,t^{-1}]$ of existential sentences, then there would be an algorithm for determining the solvability of Diophantine equations in the integers. But there is no such algorithm.

The reduction strategy is in principle simple. Given any Diophantine equation $P(X_1,\dots,X_n)=0$, we show how to construct explicitly an existential sentence $\alpha_P$ such that $\alpha_P$ is true in $F[t,t^{-1}]$ if and only if $P(X_1,\cdots,X_n)=0$ has a solution in integers. Now suppose we had an algorithm to determine the truth of existential sentences in $F[t,t^{-1}]$. Then by applying the algorithm to $\gamma_P$, we could determine whether or not the Diophantine equation $P(X_1,\dots,X_n)=0$ has a solution, contradicting the (negative) solution of Hilbert's $10$-th Problem.

By Lemmas 1 and 2, there is an existential formula $\psi(w)$ such that $w\in F[t,t^{-1}]$ satisfies the formula $\psi$ if and only if $w$ is an ordinary integer. Thus $P(X_1,\dots,X_n)=0$ has an integer solution if and only if the sentence $$\exists x_1\cdots,\exists x_n((\psi(x_1)\land\dots\land \psi(x_n))\land P(x_1,\dots,x_n)=0)\tag{2}$$ is true in $F[t,t^{1}]$. In the sentence (2), the existential quantification ranges over $F[t,t^{-1}]$. The subformulas $\psi(x_i)$ informally say "$x_i$ is an ordinary integer."

Note that the subformulas $\psi(x_i)$ are existential, involving $4$ existential quantifiers each. We need to use $4n$ distinct existentially quantified variables for the $\psi(x_i)$, and we need to bring them to the front in (2) so that the resulting sentence will be genuinely existential.

That's all there is to the reduction. Suppose further that $-1$ is never a sum of squares in the field $F$. This is true in particular if $F$ is a subfield of the reals. Then by a trick you are by now familiar with, we say a little more. Given any polynomial $P(X_1,\dots,X_n)$ with integer coefficients, we can construct a polynomial $P^\ast(x_1,\dots, x_n,y_1,\dots,y_m)$ with integer coefficients such that the Diophantine equation $P(X_1,\dots,X_n)=0$ has a solution in the integers if and only if the equation $P^\ast(x_1,\dots, x_n,y_1,\dots,y_m)=0$ has a solution in $F[t,t^{-1}]$.

• I will (perhaps tomorrow, busy time, long term visitors), deal with $\psi$, it is the subject of another of your questions. The stuff about $-1$ was really not relevant to your main question, about existential definability, it was just a side comment. When we write (i) $P_1(\bar{u})=0)\land P_2(\bar{v})=0$ (with existential quantifiers in front) we have an existential formula. If the sum of squares is $0$ iff each term is $0$ (true in the rationals, the reals, but not the complexes) we can replace the $\land$ by $P_1^2+P_2^2=0$, which makes it look more Diophantine. Jul 29 '15 at 3:22
• By the way, the big open problem in this game, that people have been working on for more than 40 years, is whether there is an algorithm for determining solvability of Diophantine equations in rationals. Jul 29 '15 at 3:29
• I imagine you are gathering a bibiliography on the subject. An active person has been Bjorn Poonen. Jul 29 '15 at 3:42
• I should also mention Alexandra Shlapentokh (my spelling may be off). Jul 29 '15 at 3:47
• What is your fundamental issue with $\psi$? Is it (i) the algebraic lemmas that precede it, which lead to the fact that the ordinary integers are the polynomials in $F[t,t^{-1}]$ that have certain special algebraic properties, or is it (ii) the expression of these properties into a specific existential formula? Jul 29 '15 at 20:18

format: plain


text:
# Freakonometrics

## Tag - normal

Tuesday, October 30 2012

## Le passage au log dans les modèles linéaires

Un billet rapide pour compléter et illustrer le passage au log dans un modèle linéaire (que l'on abordera cette semaine en cours). Le point de départ est le modèle linéaire, où on suppose que, conditionnellement à $X$$Y$ suit une loi normale. Pour rappel, si on a une loi normale, $Y\sim \mathcal{N}(\mu,\sigma^2)$, alors $\mathbb{E}(Y)=\mu$ et $\text{Var}(Y)=\sigma^2$. Les intervalles de confiance à 90% et 95% sont symétriques par rapport à la moyenne (qui est aussi la médiane, soit dit en passant),

Dans un modèle Gaussien avec homoscédasiticité, $Y|X\sim \mathcal{N}(\beta_0+\beta_1X,\sigma^2)$ i.e. $\mathbb{E}(Y|X)=\beta_0+\beta_1X$ alors que $\text{Var}(Y|X)=\sigma^2$. On a alors les bandes de confiance suivantes, pour un modèle de régression linéaire,

Bon, maintenant, que se passe-t-il si on prend l'exponentiel ? Pour la loi normale, rappelons que l'on obtient une loi lognormale, i.e. $\exp(Y)\sim LN(\mu,\sigma^2)$, les deux paramètres étant liés à la loi normale sous jacente, car désormais

$\mathbb{E}(\exp(Y))=\exp\left(\mu+\frac{\sigma^2}{2}\right)$

alors que

$\text{Var}(\exp(Y))=(\exp[\sigma^2]-1)\cdot\exp[2\mu+\sigma^2]$

Graphiquement, on a la loi suivante, avec les intervalles de confiance à 90% et 95% représentés ci-dessous. Le point noir est $\exp(\mu)$  alors que le point bleu est l'espérance de la loi lognormale.

On notera que le quantile de la loi log-normale est l'exponentiel du quantile de la loi normale. En effet, si $\mathbb{P}(Y\leq q)=\alpha$ alors $\mathbb{P}(\exp(Y)\leq \exp(q))=\alpha$. En particulier, $\exp(\mu)$ n'est pas la moyenne de $\exp(Y)$, mais la médiane (puisque $\mu$ était la médiane de $Y$).

Mais il n'est pas rare de voir utilisé un intervalle de confiance de la forme

$\mathbb(\exp(Y))\pm q_{1-\alpha/2}\sqrt{\text{Var}(\exp(Y))}$

qui est la forme classique de l'intervalle de confiance Gaussien (symétrique autour de la moyenne). Ici, on aurait les niveaux suivants

Notons qu'il n'y a aucune raison ici d'avoir une probabilité $1-\alpha$ d'être dans l'intervalle de confiance obtenu avec les quantiles $q_{1-\alpha/2}$ de la loi normale.

Maintenant, si on prend l'exponentiel d'un modèle linéaire (i.e. le logarithme de la variable d’intérêt est modélisé par un modèle linéaire) on a

$\mathbb{E}(\exp(Y)|X)=\exp\left(\beta_0+\beta_1X+\frac{\sigma^2}{2}\right)$

avec une variance (conditionnelle) qui dépend de la variable explicative

$\text{Var}(\exp(Y)|X)=(\exp[\sigma^2]-1)\cdot\exp[2(\beta_0+\beta_1X)+\sigma^2]$

Là encore, le plus naturel est d'utiliser comme bornes de l'intervalle de confiance des quantiles associés à la loi lognormale,

mais il n'est pas rare de voir utilisé des intervalles de type Gaussiens,

On perd là encore en interprétation car les bornes n'ont plus rien à voir avec les quantiles.

Thursday, September 27 2012

## Bounding sums of random variables, part 1

For the last course MAT8886 of this (long) winter session, on copulas (and extremes), we will discuss risk aggregation. The course will be mainly on the problem of bounding  the distribution (or some risk measure, say the Value-at-Risk) for two random variables with given marginal distribution. For instance, we have two Gaussian risks. What could be be worst-case scenario for the 99% quantile of the sum ? Note that I mention implications in terms of risk management, but of course, those questions are extremely important in terms of statistical inference, see e.g. Fan & Park (2006).

This problem, is sometimes related to some question asked by Kolmogorov almost one hundred years ago, as mentioned in Makarov (1981). One year after, Rüschendorf (1982) also suggested a proof of bounds calculation. Here, we focus in dimension 2. As usual, it is the simple case. But as mentioned recently, in Kreinovich & Ferson (2005), in dimension 3 (or higher), "computing the best-possible bounds for arbitrary n is an NP-hard (computationally intractable) problem". So let us focus on the case where we sum (only) two random variable (for those interested in higher dimension, Puccetti & Rüschendorf (2012) provided interesting results for a dual version of those optimal bounds).

Let $\Delta$ denote the set of univariate continuous distribution function, left-continuous, on $\mathbb{R}$. And $\Delta^+$ the set of distributions on $\mathbb{R}^+$. Thus, $F\in\Delta^+$ if $F\in\Delta$ and $F(0)=0$. Consider now two distributions $F,G\in\Delta^+$. In a very general setting, it is possible to consider operators on $\Delta^+\times \Delta^+$. Thus, let $T:[0,1]\times[0,1]\rightarrow[0,1]$ denote an operator, increasing in each component, thus that $T(1,1)=1$. And consider some function $L:\mathbb{R}^+\times\mathbb{R}^+\rightarrow\mathbb{R}^+$ assumed to be also increasing in each component (and continuous). For such functions $T$ and $L$, define the following (general) operator, $\tau_{T,L}(F,G)$ as

$\tau_{T,L}(F,G)(x)=\sup_{L(u,v)=x}\{T(F(u),G(v))\}$

One interesting case can be obtained when $T$is a copula, $C$. In that case,

$\tau_{C,L}(F,G):\Delta^+\times\Delta^+\rightarrow\Delta^+$

and further, it is possible to write

$\tau_{C,L}(F,G)(x)=\sup_{(u,v)\in L^{-1}(x)}\{C(F(u),G(v))\}$

It is also possible to consider other (general) operators, e.g. based on the sum

$\sigma_{C,L}(F,G)(x)=\int_{(u,v)\in L^{-1}(x)} dC(F(u),G(v))$

or on the minimum,

$\rho_{C,L}(F,G)(x)=\inf_{(u,v)\in L^{-1}(x)}\{C^\star(F(u),G(v))\}$

where $C^\star$ is the survival copula associated with $C$, i.e. $C^\star(u,v)=u+v-C(u,v)$. Note that those operators can be used to define distribution functions, i.e.

$\sigma_{C,L}(F,G):\Delta^+\times\Delta^+\rightarrow\Delta^+$

and similarly

$\rho_{C,L}(F,G):\Delta^+\times\Delta^+\rightarrow\Delta^+$

All that seems too theoretical ? An application can be the case of the sum, i.e. $L(x,y)=x+y$, in that case $\sigma_{C,+}(F,G)$ is the distribution of sum of two random variables with marginal distributions $F$ and $G$, and copula $C$. Thus, $\sigma_{C^\perp,+}(F,G)$ is simply the convolution of two distributions,

$\sigma_{C^\perp,+}(F,G)(x)=\int_{u+v=x} dC^\perp(F(u),G(v))$

The important result (that can be found in Chapter 7, in Schweizer and Sklar (1983)) is that given an operator $L$, then, for any copula $C$, one can find a lower bound for $\sigma_{C,L}(F,G)$

$\tau_{C^-,L}(F,G)\leq \tau_{C,L}(F,G)\leq\sigma_{C,L}(F,G)$

as well as an upper bound

$\sigma_{C,L}(F,G)\leq \rho_{C,L}(F,G)\leq\rho_{C^-,L}(F,G)$

Those inequalities come from the fact that for all copula $C$, $C\geq C^-$, where $C^-$ is a copula. Since this function is not copula in higher dimension, one can easily imagine that get those bounds in higher dimension will be much more complicated...

In the case of the sum of two random variables, with marginal distributions $F$ and $G$, bounds for the distribution of the sum $H(x)=\mathbb{P}(X+Y\leq x)$, where $X\sim F$ and $Y\sim G$, can be written

$H^-(x)=\tau_{C^- ,+}(F,G)(x)=\sup_{u+v=x}\{ \max\{F(u)+G(v)-1,0\} \}$

for the lower bound, and

$H^+(x)=\rho_{C^- ,+}(F,G)(x)=\inf_{u+v=x}\{ \min\{F(u)+G(v),1\} \}$

for the upper bound. And those bounds are sharp, in the sense that, for all $t\in(0,1)$, there is a copula $C_t$ such that

$\tau_{C_t,+}(F,G)(x)=\tau_{C^- ,+}(F,G)(x)=t$

and there is (another) copula $C_t$ such that

$\sigma_{C_t,+}(F,G)(x)=\tau_{C^- ,+}(F,G)(x)=t$

Thus, using those results, it is possible to bound cumulative distribution function. But actually, all that can be done also on quantiles (see Frank, Nelsen & Schweizer (1987)). For all $F\in\Delta^+$ let $F^{-1}$ denotes its generalized inverse, left continuous, and let $\nabla^+$ denote the set of those quantile functions. Define then the dual versions of our operators,

$\tau^{-1}_{T,L}(F^{-1},G^{-1})(x)=\inf_{(u,v)\in T^{-1}(x)}\{L(F^{-1}(u),G^{-1}(v))\}$

and

$\rho^{-1}_{T,L}(F^{-1},G^{-1})(x)=\sup_{(u,v)\in T^\star^{-1}(x)}\{L(F^{-1}(u),G^{-1}(v))\}$

Those definitions are really dual versions of the previous ones, in the sense that $\tau^{-1}_{T,L}(F^{-1},G^{-1})=[\tau_{T,L}(F,G)]^{-1}$ and $\rho^{-1}_{T,L}(F^{-1},G^{-1})=[\rho_{T,L}(F,G)]^{-1}$.

Note that if we focus on sums of bivariate distributions, the lower bound for the quantile of the sum is

$\tau^{-1}_{C^{-},+}(F^{-1},G^{-1})(x)=\inf_{\max\{u+v-1,0\}=x}\{F^{-1}(u)+G^{-1}(v)\}$

while the upper bound is

$\rho^{-1}_{C^{-},+}(F^{-1},G^{-1})(x)=\sup_{\min\{u+v,1\}=x}\{F^{-1}(u)+G^{-1}(v)\}$

A great thing is that it should not be too difficult to compute numerically those quantities. Perhaps a little bit more for cumulative distribution functions, since they are not defined on a bounded support. But still, if the goal is to plot those bounds on $[0,10]$, for instance. The code is the following, for the sum of two lognormal distributions $LN(0,1)$

> F=function(x) plnorm(x,0,1)
> G=function(x) plnorm(x,0,1)
> n=100
> X=seq(0,10,by=.05)
> Hinf=Hsup=rep(NA,length(X))
> for(i in 1:length(X)){
+ x=X[i]
+ U=seq(0,x,by=1/n); V=x-U
+ Hinf[i]=max(pmax(F(U)+G(V)-1,0))
+ Hsup[i]=min(pmin(F(U)+G(V),1))}

If we plot those bounds, we obtain

> plot(X,Hinf,ylim=c(0,1),type="s",col="red")
> lines(X,Hsup,type="s",col="red")

But somehow, it is even more simple to work with quantiles since they are defined on a finite support. Quantiles are here

> Finv=function(u) qlnorm(u,0,1)
> Ginv=function(u) qlnorm(u,0,1)

The idea will be to consider a discretized version of the unit interval as discussed in Williamson (1989), in a much more general setting. Again the idea is to compute, for instance

$\sup_{u\in[0,x]}\{F^{-1}(u)+G^{-1}(x-u)\}$

The idea is to consider $x=i/n$ and $u=j/n$, and the bound for the quantile function at point $i/n$ is then

$\sup_{j\in\{0,1,\cdots,i\}}\left\{F^{-1}\left(\frac{j}{n}\right)+G^{-1}\left(\frac{i-j}{n}\right)\right\}$

The code to compute those bounds, for a given $n$ is here

> n=1000
> Qinf=Qsup=rep(NA,n-1)
> for(i in 1:(n-1)){
+ J=0:i
+ Qinf[i]=max(Finv(J/n)+Ginv((i-J)/n))
+ J=(i-1):(n-1)
+ Qsup[i]=min(Finv((J+1)/n)+Ginv((i-1-J+n)/n))
+ }

Here we have (several $n$s were considered, so that we can visualize the convergence of that numerical algorithm),

Here, we have a simple code to visualize bounds for quantiles for the sum of two risks. But it is possible to go further...

Thursday, February 23 2012

## Visualization in regression analysis

Visualization is a key to success in regression analysis. This is one of the (many) reasons I am also suspicious when I read an article with a quantitative (econometric) analysis without any graph. Consider for instance the following dataset, obtained from http://data.worldbank.org/, with, for each country, the GDP per capita (in some common currency) and the infant mortality rate (deaths before the age of 5),
> library(gdata)
/NY.GDP.PCAP.PP.CD_Indicator_MetaData_en_EXCEL.xls", sheet = 1)
> data1=XLS1[-(1:28),c("Country.Name","Country.Code","X2010")]
> names(data1)[3]="GDP"
/SH.DYN.MORT_Indicator_MetaData_en_EXCEL.xls", sheet = 1)
> data2=XLS2[-(1:28),c("Country.Code","X2010")]
> names(data2)[2]="MORTALITY"
> data=merge(data1,data2)
Country.Code         Country.Name       GDP MORTALITY
1          ABW                Aruba        NA        NA
2          AFG          Afghanistan  1207.278     149.2
3          AGO               Angola  6119.930     160.5
4          ALB              Albania  8817.009      18.4
5          AND              Andorra        NA       3.8
6          ARE United Arab Emirates 47215.315       7.1

If we estimate a simple linear regression -   - we get
> regBB=lm(MORTALITY~GDP,data=data)
> summary(regBB)

Call:
lm(formula = MORTALITY ~ GDP, data = data)

Residuals:
Min     1Q Median     3Q    Max
-45.24 -29.58 -12.12  16.19 115.83

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 67.1008781  4.1577411  16.139  < 2e-16 ***
GDP         -0.0017887  0.0002161  -8.278 3.83e-14 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 39.99 on 167 degrees of freedom
(47 observations deleted due to missingness)
Multiple R-squared: 0.2909,	Adjusted R-squared: 0.2867
F-statistic: 68.53 on 1 and 167 DF,  p-value: 3.834e-14
We can look at the scatter plot, including the linear regression line, and some confidence bounds,
> plot(data$GDP,data$MORTALITY,xlab="GDP per capita",
+ ylab="Mortality rate (under 5)",cex=.5)
> text(data$GDP,data$MORTALITY,data$Country.Name,pos=3) > x=seq(-10000,100000,length=101) > y=predict(regBB,newdata=data.frame(GDP=x), + interval="prediction",level = 0.9) > lines(x,y[,1],col="red") > lines(x,y[,2],col="red",lty=2) > lines(x,y[,3],col="red",lty=2) We should be able to do a better job here. For instance, if we look at the Box-Cox profile likelihood, > boxcox(regBB) it looks like taking the logarithm of the mortality rate should be better, i.e. or : > regLB=lm(log(MORTALITY)~GDP,data=data) > summary(regLB) Call: lm(formula = log(MORTALITY) ~ GDP, data = data) Residuals: Min 1Q Median 3Q Max -1.3035 -0.5837 -0.1138 0.5597 3.0583 Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) 3.989e+00 7.970e-02 50.05 <2e-16 *** GDP -6.487e-05 4.142e-06 -15.66 <2e-16 *** --- Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 Residual standard error: 0.7666 on 167 degrees of freedom (47 observations deleted due to missingness) Multiple R-squared: 0.5949, Adjusted R-squared: 0.5925 F-statistic: 245.3 on 1 and 167 DF, p-value: < 2.2e-16 > plot(data$GDP,data$MORTALITY,xlab="GDP per capita", + ylab="Mortality rate (under 5) log scale",cex=.5,log="y") > text(data$GDP,data$MORTALITY,data$Country.Name)
> x=seq(300,100000,length=101)
> y=exp(predict(regLB,newdata=data.frame(GDP=x)))*
+ exp(summary(regLB)$sigma^2/2) > lines(x,y,col="red") > y=qlnorm(.95, meanlog=predict(regLB,newdata=data.frame(GDP=x)), + sdlog=summary(regLB)$sigma^2)
> lines(x,y,col="red",lty=2)
> y=qlnorm(.05, meanlog=predict(regLB,newdata=data.frame(GDP=x)),
+ sdlog=summary(regLB)$sigma^2) > lines(x,y,col="red",lty=2) on the log scale or > plot(data$GDP,data$MORTALITY,xlab="GDP per capita", + ylab="Mortality rate (under 5) log scale",cex=.5) on the standard scale. Here we use quantiles of the log-normal distribution to derive confidence intervals. But why shouldn't we take also the logarithm of the GDP ? We can fit a model or equivalently . > regLL=lm(log(MORTALITY)~log(GDP),data=data) > summary(regLL) Call: lm(formula = log(MORTALITY) ~ log(GDP), data = data) Residuals: Min 1Q Median 3Q Max -1.13200 -0.38326 -0.07127 0.26610 3.02212 Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) 10.50192 0.31556 33.28 <2e-16 *** log(GDP) -0.83496 0.03548 -23.54 <2e-16 *** --- Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 Residual standard error: 0.5797 on 167 degrees of freedom (47 observations deleted due to missingness) Multiple R-squared: 0.7684, Adjusted R-squared: 0.767 F-statistic: 554 on 1 and 167 DF, p-value: < 2.2e-16 > plot(data$GDP,data$MORTALITY,xlab="GDP per capita ", + ylab="Mortality rate (under 5)",cex=.5,log="xy") > text(data$GDP,data$MORTALITY,data$Country.Name)
> x=exp(seq(1,12,by=.1))
> y=exp(predict(regLL,newdata=data.frame(GDP=x)))*
+ exp(summary(regLL)$sigma^2/2) > lines(x,y,col="red") > y=qlnorm(.95, meanlog=predict(regLL,newdata=data.frame(GDP=x)), + sdlog=summary(regLL)$sigma^2)
> lines(x,y,col="red",lty=2)
> y=qlnorm(.05, meanlog=predict(regLL,newdata=data.frame(GDP=x)),
+ sdlog=summary(regLL)$sigma^2) > lines(x,y,col="red",lty=2) on the log scales or > plot(data$GDP,data\$MORTALITY,xlab="GDP per capita ",
+ ylab="Mortality rate (under 5)",cex=.5)

on the standard scale. If we compare the last two predictions, we have

with in blue is the log model, and in red is the log-log model (I did not include the first one for obvious reasons).

Thursday, January 12 2012

## MAT8886 Fisher-Tippett theorem and limiting distribution for the maximum

Tomorrow, we will discuss Fisher-Tippett theorem. The idea is that there are only three possible limiting distributions for normalized versions of the maxima of i.i.d. samples . For bounded distribution, consider e.g. the uniform distribution on the unit interval, i.e. on the unit interval. Let and . Then, for all and ,

i.e. the limiting distribution of the maximum is Weibull's.

set.seed(1)
s=1000000
n=100
M=matrix(runif(s),n,s/n)
V=apply(M,2,max)
bn=1
an=1/n
U=(V-bn)/an
hist(U,probability=TRUE,,col="light green",
xlim=c(-7,1),main="",breaks=seq(-20,10,by=.25))
u=seq(-10,0,by=.1)
v=exp(u)
lines(u,v,lwd=3,col="red")

For heavy tailed distribution, or Pareto-type tails, consider Pareto samples, with distribution function . Let and , then

which means that the limiting distribution is Fréchet's.

set.seed(1)
s=1000000
n=100
M=matrix((runif(s))^(-1/2),n,s/n)
V=apply(M,2,max)
bn=0
an=n^(1/2)
U=(V-bn)/an
hist(U,probability=TRUE,col="light green",
xlim=c(0,7),main="",breaks=seq(0,max(U)+1,by=.25))
u=seq(0,10,by=.1)
v=dfrechet(u,shape=2)
lines(u,v,lwd=3,col="red")

For light tailed distribution, or exponential tails, consider e.g. a sample of exponentially distribution variates, with common distribution function . Let and , then

i.e. the limiting distribution for the maximum is Gumbel's distribution.

library(evd)
set.seed(1)
s=1000000
n=100
M=matrix(rexp(s,1),n,s/n)
V=apply(M,2,max)
(bn=qexp(1-1/n))
log(n)
an=1
U=(V-bn)/an
hist(U,probability=TRUE,col="light green",
xlim=c(-2,7),ylim=c(0,.39),main="",breaks=seq(-5,15,by=.25))
u=seq(-5,15,by=.1)
v=dgumbel(u)
lines(u,v,lwd=3,col="red")

Consider now a Gaussian sample. We can use the following approximation of the cumulative distribution function (based on l'Hopital's rule)

as . Let and . Then we can get

as . I.e. the limiting distribution of the maximum of a Gaussian sample is Gumbel's. But what we do not see here is that for a Gaussian sample, the convergence is extremely slow, i.e., with 100 observations, we are still far away from Gumbel distribution,

and it is only slightly better with 1,000 observations,

set.seed(1)
s=10000000
n=1000
M=matrix(rnorm(s,0,1),n,s/n)
V=apply(M,2,max)
(bn=qnorm(1-1/n,0,1))
an=1/bn
U=(V-bn)/an
hist(U,probability=TRUE,col="light green",
xlim=c(-2,7),ylim=c(0,.39),main="",breaks=seq(-5,15,by=.25))
u=seq(-5,15,by=.1)
v=dgumbel(u)
lines(u,v,lwd=3,col="red")

Even worst, consider lognormal observations. In that case, recall that if we consider (increasing) transformation of variates, we are in the same domain of attraction. Hence, since , if

then

i.e. using Taylor's approximation on the right term,

This gives us normalizing coefficients we should use here.

set.seed(1)
s=10000000
n=1000
M=matrix(rlnorm(s,0,1),n,s/n)
V=apply(M,2,max)
bn=exp(qnorm(1-1/n,0,1))
an=exp(qnorm(1-1/n,0,1))/(qnorm(1-1/n,0,1))
U=(V-bn)/an
hist(U,probability=TRUE,col="light green",
xlim=c(-2,7),ylim=c(0,.39),main="",breaks=seq(-5,40,by=.25))
u=seq(-5,15,by=.1)
v=dgumbel(u)
lines(u,v,lwd=3,col="red")

Credit: illustration is from Maurice Sendak's popular book where the wild things are, translated in French as Max et les Maximonstres.

Tuesday, February 15 2011

## In statistics, having too much information might not be a good thing

A common idea in statistics is that if we don't know something, and we use an estimator of that something (instead of the true value) then there will be some additional uncertainty.

For instance, consider a random sample, i.i.d., from a Gaussian distribution. Then, a confidence interval for the mean is

where is the quantile of probability level of the standard normal distribution . But usually, standard deviation (the something is was talking about earlier) is usually unknown. So we substitute an estimation of the standard deviation, e.g.
and the cost we have to pay is that the new confidence interval is
where now is the quantile of the Student distribution, of probability level , with degrees of freedom.
We call it a cost since the new confidence interval is now larger (the Student distribution has higher upper-quantiles than the Gaussian distribution).
So usually, if we substitute an estimation to the true value, there is a price to pay.
A few years ago, with Jean David Fermanian and Olivier Scaillet, we were writing a survey on copula density estimation (using kernels,  here). At the end, we wanted to add a small paragraph on the fact that we assumed that we wanted to fit a copula on a sample i.i.d. with distribution , a copula, but in practice, we start from a sample with joint distribution (assumed to have continuous margins, and - unique - copula ). But since margins are usually unknown, there should be a price for not observing them.
To be more formal, in a perfect wold, we would consider
but in the real world, we have to consider
where it is standard to consider ranks, i.e. are empirical cumulative distribution functions.
My point is that when I ran simulations for the survey (the idea was more to give illustrations of several techniques of estimation, rather than proofs of technical theorems) we observed that the price to pay... was negative ! I.e. the variance of the estimator of the density (wherever on the unit square) was smaller on the pseudo sample than on perfect sample .
By that time, we could not understand why we got that counter-intuitive result: even if we do know the true distribution, it is better not to use it, and to use instead a nonparametric estimator. Our interpretation was based on the discrepancy concept and was related to the latin hypercube construction:

With ranks, the data are more regular, and marginal distributions are exactly uniform on the unit interval. So there is less variance.
This was our heuristic interpretation.
A couple of weeks ago, Christian Genest and Johan Segers proved that intuition in an article published in JMVA,

Well, we observed something for finite , but Christian and Johan obtained an analytical result. Hence, if we denote
the empirical copula in the perfect world (with known margins) and
the one constructed from the pseudo sample, they obtained that, everywhere
with nice graphs of ,
So I was very happy last week when Christian show me their results, to learn that our intuition was correct. Nevertheless, it is still a very counter-intuitive result.... If anyone has seen similar things, I'd be glad to hear about it !


text:
# Use a calculator to find the value of the trigonometric function sin((3pi)/10) to four decimal places.

Question
Trigonometric Functions
Use a calculator to find the value of the trigonometric function $$\displaystyle{\sin{{\left(\frac{{{3}\pi}}{{10}}\right)}}}$$ to four decimal places.

2021-02-01
Here
Use a calculator to find the value of the given trigonometric function up-to four decimal places.
$$\displaystyle{\sin{{\left(\frac{{{3}\pi}}{{10}}\right)}}}={0.8090}$$
Hence, the value of the given trigonometric function up to four decimal places is 0.8090

### Relevant Questions

Use a calculator to find the value of the trigonometric function csc 1 to four decimal places.
To further justify the Cofunction Theorem, use your calculator to find a value for the given pair of trigonometric functions. In each case, the trigonometric functions are cofunctions of one another, and the angles are complementary angles. Round your answers to four places past the decimal point.
$$\displaystyle{{\sec{{6.7}}}^{\circ},}{\cos{{e}}}{c}{83.3}^{\circ}$$
The question asks for the exact value of the trigonometric function at the given real number:
$$\displaystyle{\sin{{\left(\frac{{{3}\pi}}{{4}}\right)}}}$$
Use the figures to find the exact value of the trigonometric function $$\displaystyle{\tan{{2}}}\theta$$.
Sketch a right triangle corresponding to the trigonometric function of the acute angle theta. Use the Pythagorean Theorem to determine the third side and then find the other five trigonometric functions of theta. $$\displaystyle{\cos{\theta}}=\frac{{21}}{{5}}$$
$$\displaystyle{\sin{{t}}}=\frac{{3}}{{4}}{\quad\text{and}\quad}{\cos{{t}}}=\frac{\sqrt{{7}}}{{4}}$$
Find derivative of trigonometric function $$\displaystyle{y}=\frac{{{3}{\left({1}-{\sin{{x}}}\right)}}}{{{2}{\cos{{x}}}}}$$
Find derivative of trigonometric function $$\displaystyle{y}=\frac{{{3}{\left({1}-{\sin{{x}}}\right)}}}{{{2}{\cos{{x}}}}}$$
Find the exact value of the trigonometric function $$\displaystyle{\sec{{\left(\frac{{-{9}\pi}}{{4}}\right)}}}$$ .
Find the exact value of the trigonometric function $$\displaystyle\frac{{\cos{{\left({9}\pi\right)}}}}{{4}}$$.


text:
## Winter 1993

Problem Statement: Suppose that $\{f_n\}$ converges to $f$ uniformly and $\{g_n\}$ converges to $g$ uniformly on $[a,b]$ where each $f_n,g_n$ is continuous on $[a,b]$. Prove that $f_ng_n$ converges uniformly to $fg$ on $[a,b]$.

Proof: Since $[a,b]$ is a compact set and $f_n,g_n$ are each continuous on $[a,b]$ it follows that each $f_n,g_n$ is bounded on $[a,b]$. So, there exist $M,P\in\mathbb{R}$ such that $|f_n(x)|\leq M$ and $|g_n(x)|\leq P$ for every $x\in [a,b]$ and for every $n\in\mathbb{N}$.

Let $\varepsilon>0$. Then there exists $N_1\in\mathbb{N}$ such that $|f_n(x)-f(x)|<\dfrac{\varepsilon}{2P}$ for every $n\geq N_1$ and for every $x\in [a,b]$ since $f_n\rightarrow f$ uniformly. Similarly, there exists $N_2\in\mathbb{N}$ such that $|g_n(x)-g(x)|<\dfrac{\varepsilon}{2M}$ for every $n\geq N_2$ and for every $x\in [a,b]$.

Let $N=max\{N_1,N_2\}$. Then for $n\geq N$ and $x\in [a,b]$ it follows that

$|f_ng_n(x)-fg(x)|=|(f_n(x)-f(x))g_n(x)+f(x)(g_n(x)-g(x))|$

$\leq |f_n(x)-f(x)|P+M|g_n(x)-g(x)|$ for every $x\in [a,b]$

$<\dfrac{\varepsilon}{2P}P+\dfrac{\varepsilon}{2M}M$

$=\dfrac{\varepsilon}{2}+\dfrac{\varepsilon}{2}=\varepsilon$

Thus, $f_ng_n$ converges to $fg$ uniformly on $[a,b]$.

$\Box$

Reflection: This one really followed straight from the definitions. The key being in that we knew each of the functions was bounded. Also, we used a little bit of “math magic” to make the inside of the absolute values look like things we knew about. The thing to keep in mind when doing all of these problem is what you know information about. You can never make a conclusion about some inequality if you don’t have any information about it!


text:
View Single Post
HW Helper
P: 2,953
 Quote by mathwonk d of a one form IS the "curl" of that one form. i.e. no matter WHAT coordinates u,v are, the curl of fdu + gdv is ALWAYS df^du + dg^dv, in THOSE coordinates. e.g. the curl of the angle form dtheta, in polar coords, is ddtheta = 0. d of a one form, i.e. the curl, is always computed the same way, in all coordinates. there is no need to transform anything. all i was doing was proving this. there is nothing else to memorize. by introducing hodge duals you are just making life needlessly more complicated. the only time a metric is needed is when one wants to study harmonic functions, i.e.laplacians. somehow i feel we are still not communicating. you are trying to express something which is natural in all coordinate systems, i.e. exterior derivatives d, in terms of something less natural, i.e. components gij using a metric. perhaps you have a need for this, but i do not see it.

I think that it's because we are talking about different curls.

My goal (and it may be that the goal in itself seems useless but that's a different discusssion) is to recover, from a differential form approach, the following expression that we learned in elementary calculus:

$$\nabla \times \vec{A} = \frac{1}{r sin \theta} \bigl( \frac{\partial ( sin \theta A_{\phi})}{\partial \theta} - \frac{\partial A_{\theta}}{\partial \phi} \bigr) \hat{r} + \ldots$$

This is what I am trying to obtain starting from differential forms.

regards


text:
# R studio cannot make xtable

library(xtable)
library(magrittr)
library(moonBook)
options(ztable.type="html")
a
x = xtable(a)
x

i cannot make xtable, just use mytable... want to use xtable, but output like this.. what is problem?? i installed latex progrem.. help me i cannot find good result in googling..

     Descriptive Statistics
--------------------------------
N     Total
--------------------------------
Sepal.Length    6   5.0 ± 0.3
Sepal.Width     6   3.4 ± 0.3
Petal.Length    6
- 1.3             1  (16.7%)
- 1.4             3  (50.0%)
- 1.5             1  (16.7%)
- 1.7             1  (16.7%)
Petal.Width     6
- 0.2             5  (83.3%)
- 0.4             1  (16.7%)
Species         6
- setosa         6  (100.0%)
- versicolor       0  (0.0%)
- virginica        0  (0.0%)
--------------------------------
% latex table generated in R 3.6.1 by xtable 1.8-4 package
% Fri Sep 27 14:45:14 2019
\begin{table}[ht]
\centering
\begin{tabular}{rllll}
\hline
& name & N & stats & class \\
\hline
1 & Sepal.Length   & 6 & 5.0 ± 0.3 & continuous \\
2 & Sepal.Width    & 6 & 3.4 ± 0.3 & continuous \\
3 & Petal.Length   & 6 &    & categorical \\
4 &   - 1.3        &  & 1  (16.7\%) &  \\
5 &   - 1.4        &  & 3  (50.0\%) &  \\
6 &   - 1.5        &  & 1  (16.7\%) &  \\
7 &   - 1.7        &  & 1  (16.7\%) &  \\
8 & Petal.Width    & 6 &    & categorical \\
9 &   - 0.2        &  & 5  (83.3\%) &  \\
10 &   - 0.4        &  & 1  (16.7\%) &  \\
11 & Species        & 6 &    & categorical \\
12 &   - setosa     &  & 6  (100.0\%) &  \\
13 &   - versicolor &  & 0  (0.0\%) &  \\
14 &   - virginica  &  & 0  (0.0\%) &  \\
\hline
\end{tabular}
\end{table}

xtable() is working perfectly well in your example. The output since from % latex table ... to \end{table} is the LaTeX code that make a LaTeX table, but the R output is not a LaTeX document, is only a text which only in part is a chunk of LaTeX code that is not compilable "as is".

So you have two options:

1) Copy & paste that code in a complete LaTeX (.tex) document:

\documentclass{article}
\begin{document}

% paste your LaTeX table code here

\end{document}

That you must compile with pdflatex, xelatex or lualatex (e.g.: pdflatex mytable.tex)

2) Make a Sweave (.Rnw) document, that is nearly the same LaTeX document, but instead of paste the LaTeX table, you include the R code to obtain that table, but supplying also some output options:

\documentclass{article}
\begin{document}

<<mytable,echo=FALSE,results="asis">>=
# paste your R code here
@

\end{document}

When edited with Rstudio, simply click the "Compile PDF" button to obtain the same result.

Compilable working example:

\documentclass{article}
\begin{document}
<<mytable,echo=FALSE,results='asis'>>=
library(xtable)
a <- matrix(c(1,2,3,4,5,6,7,8,9),nrow=3)
xtable(a)
@
\end{document}

• An additional possibility would be a Rmarkdown document. Might be easier for people not used to LaTeX syntax. Sep 27 '19 at 9:27
• Thanks Fran, i did and i satisfies your pretty answer, I'm a beginner for use R, but It's good luck to meet you with this site. i `m S korean, asked the Korea site but there was no answer. and I bookmarked this site, and i will remember you Fran. thank you and you are really really good person!! Sep 28 '19 at 0:51


text:
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /nfs/c02/h01/mnt/26954/domains/protegido24.com/html/wp-content/plugins/smart-slider-3/nextend/library/libraries/localization/pomo/plural-forms.php on line 224

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /nfs/c02/h01/mnt/26954/domains/protegido24.com/html/wp-content/themes/Divi/includes/builder/functions.php on line 4813
solving multi step equations worksheet answers Pulmonol Cough Syrup In Pregnancy, Approaches To Old Testament Theology, Best Dog Brush For Two Coats, 6th Grade School Supplies List 2020-21, Professional Performing Arts High School, Another Word For Feeling Frightened, " /> Pulmonol Cough Syrup In Pregnancy, Approaches To Old Testament Theology, Best Dog Brush For Two Coats, 6th Grade School Supplies List 2020-21, Professional Performing Arts High School, Another Word For Feeling Frightened, " />
Seleccionar página

Math. [CDATA[ var trackcmp_email = ''; var trackcmp = document.createElement("script"); trackcmp.async = true; trackcmp.type = 'text/javascript'; trackcmp.src = '//trackcmp.net/visit?actid=475142227&e='+encodeURIComponent(trackcmp_email)+'&r='+encodeURIComponent(document.referrer)+'&u='+encodeURIComponent(window.location.href); var trackcmp_s = document.getElementsByTagName("script"); if (trackcmp_s.length) { trackcmp_s[0].parentNode.appendChild(trackcmp); } else { var trackcmp_h = document.getElementsByTagName("head"); trackcmp_h.length && trackcmp_h[0].appendChild(trackcmp); } // ]]>. I wish I had this guy as my teacher. …we found the solution. Join the ILT for any last minute questions. Choose an answer and hit 'next'. Required fields are marked *, Copyright © 2020 | MathTeacherCoach.com | Terms and Conditions| Privacy Policy | About | Contact, 4th Grade Math | 5th Grade Math | 6th Grade Math| Pre-Algebra | Algebra 1 | Geometry | Algebra 2 & Trigonometry | Pre-Calculus. They can see complicated things, such as some algebraic expressions, as single objects or as being composed of several objects. Halloween Geometry Activities High School. They are also interactive and will give you immediate feedback, Number, fractions, addition, subtraction, division, multiplication, order of operations, money and time worksheets, with video lessons, examples and step-by-step solutions. Solving multi-step equations . Also, a number of exercise pdfs on translating two-step equations, MCQs and word problems based on geometric shapes are given here for additional practice for 7th grade and 8th grade students. For this exercise, I have prepared seven (7) multi-step equations for you to practice. Arithmetic Sequences and Series Worksheet, Introduction to Vectors – Navigating the Seas, 12-7 Theoretical and Experimental Probability, Absolute Value Equations and Inequalities, Unit 6 - Systems of Equations and Inequlities, Unit 7 - Exponents and Exponential Functions, Unit 9 - Quadratic Functions and Equations, Unit 10 - Radical Expressions and Equations, Unit 11 - Rational Expressions and Functions. However, most linear equations require more than one step in order to find their solution. Check out iTeachly: // < ! Next, add 2 to both sides, then subtract 3x, and finally finish it off by dividing 5 to both sides. Displaying top 8 worksheets found for - Practice Multi Step Equations 1. Simple Algebra Word Problems (4.OA.A.3) - The goal here is to write each problem in an equation form. Check your answer in the space provided. Complete the Number Conversions Worksheet Solutions December 2: Equations Review. Children practice two-digit addition and subtraction with this worksheet. 5th grade. Solve a mix of equation types involving like terms. The Distributive Property Activity - Cupcakes and Algebra, How to Teach Patterns and Linear Functions. Remember to always perform the same operation on both sides of the equation. This worksheet is a fun way for your students to practice solving Multi-Step Equations with a fun Halloween theme! Two-step equation worksheets have a huge collection of printable practice pages to solve and verify the equations involving integers, fractions and decimals. 1) Solve the multi-step equation for \large{c}. Algebraic Expressions Worksheet and Activity – Mazing! But first they'll need to use their reading comprehension skills to decide on the important pieces of information needed to solve each problem. Multi-step Equation Worksheets Come to Mathpoint.net and learn about graphing linear equations, subtracting rational expressions and numerous other algebra topics Only positive whole numbers are featured in the equations and all of the answers are positive as well. Mixed Basic Operations Word Problems (4.OA.A.3) - Remember PEMDAS when you are approaching these problems. 6) p − 1 = 5p + 3p − 8 {1} 7) 5p − 14 = 8p + 4 {−6} 8) p − 4 = −9 + p No solution. Challenge your second grader to review addition and subtraction facts by solving the equations … Your email address will not be published. We offer some free worksheets … Solving Multi-Step Equations. Properties of Real Numbers – The Importance of Differentiating Directions in Algebra, Absolute Value Functions and Graphs – Real World Applications, Rational Functions and Their Graphs – Group Activity. - \left( { - 8 - 3x} \right) = - 2\left( {1 - x} \right) + 6x. ... Write and Solve Equations From Word Problems. Solve word problems involving dollar bills, quarters, dimes, nickels, and pennies, using $and ¢ symbols appropriately. Don't forget to check your answers using the answer sheet. Are you looking for Great Science Lessons as well? 6n + 9n – 6n = -24 + 6. Finally, divide both sides by the coefficient of 4 c 4c 4 c which is 4 4 4 to get c = 6 c=6 c = 6. Test and worksheet generators for math teachers. Practice Solving Equations. We would like to show you a description here but the site won’t allow us. Some worksheets are dynamically generated to give you a different set to practice each time. This exercise will assess students’ abilities to solve two-step addition and subtraction word problems with mixed operations. 1) Solve the multi-step equation for. Right from online free multi step equation problem solver calculator to solving systems, we have got all the pieces discussed. Practice 1: Two-Step Equations. A different set to practice each time 1 followed by dividing 5 to both sides the! Are included in this section for 7th grade and 8th grade students offer some free worksheets … solving solving multi step equations worksheet answers... Their equation solving skills equation Form positive as well the same operation apply the Property! Exercise will assess students ’ abilities to Solve two equations before you arrive to an answer using. \Left ( { 4 - y } equation has multiple like terms on the side! 2\Left ( { 1 - x solving multi step equations worksheet answers as single objects or as being composed several... Free multi step equations worksheets with answers together with 167 Best math on! 5 ) Solve the multi-step equation for \large { c } ¢ symbols appropriately Solve the multi-step for... 4.Oa.3 ) - this is the main page for the division worksheets square...$ 900 last week ) - this is the first step would be to get c=6, square root,. Practice solving multi step equations worksheet answers addition and subtraction with this worksheet want to practice each time - and! Equation Form forget to check your answers using the equation 3x + =! Two-Step equations with Rational numbers from Tom Grodek 3x, and pennies, the. Value of x 9 and… two of the same side of the worksheet then assured... An equation Form and 8th grade students Solve two equations before you arrive to an.... Another look at 2-Steps: Intro to two-step equations with multiple steps but they always resolve integers., we get: 9n = -18 Calculators in Class simplified correctly are featured in the and. This site with cookies two-step addition and multiplication principles level of the equation 3x + 5 11... As some algebraic expressions, as single objects or as being composed several! Given here for abundant practice must do is recognize that like terms on the same side of the 3x. Lessons as well finally finish it off by dividing 5 to both sides of the equal side - }. We perform the additions and subtractions, we have got all the discussed! On CTLS ) Solutions complete for the division worksheets additions and subtractions, have. Thought-Out worksheets, square root worksheets, which have helped many classes quickly develop competency with their equation solving.! Solving two step Eqations - Displaying top 8 worksheets found for this concept that require you make...... understand the different steps that are involved in solving equations that match story... The site to Eat is in the following practice problems, students will write two step -. Problems ( 4.OA.A.3 ) - 3\left ( { 1 - x } last week bills, quarters dimes! Quarters, dimes, nickels, and finally finish it off by dividing to! Online free multi step equations worksheets involving integers, fractions and decimals as coefficients are given here for practice... On Pinterest given here for abundant practice students will Solve equations using addition! Of k which is 4 to get the constant values of the excellence that students will write step! Solving multi-step word problems worksheets will help your students will write two step Eqations - Displaying top 8 worksheets for! The first step would be to get the constant values of the same side the. Two of the equation, including combining like terms be careful when multiplying expressions with the same side the! The first step would be to get the constant values of the equation a mix of equation types involving terms! It might have two different operations ( like multiplication and division worksheets, which have helped many quickly... Following practice problems, students will see in word based problems solving two-step equations with Rational numbers from Tom.. Being composed of several objects from online free multi step equations happens when a linear has! To do now is to write each problem in an equation Form of over! Bills, quarters, dimes, nickels, and pennies, using the addition and subtraction with worksheet. Sides, then remain assured of the equal sign 4 solving two step equations to match problems like James. Case 5 and 11 are our constants step practice problems, students will write two Eqations. Property of multiplication over addition to the left side of the equal side 4.OA.3 ) - goal. Applications in geometry and MCQs are included in this case 5 and 11 are our.. Or SCROLL DOWN to use this site with cookies dividing 5 to both by... The excellence that students will see in word based problems some worksheets are dynamically generated to you... By 9 and… or SCROLL DOWN to use this worksheet division worksheets, multiple digit division worksheets, have. Work with time and money two-step equations from Khanacademy.com here is to solving multi step equations worksheet answers each in. Most linear equations require more than one step in order to find their solution equations Maze Displaying. Printable multi-step equations some more, use the free worksheets … solving multi-step word problems ( 4.OA.A.3 -! 167 Best math Images on Pinterest same side of the equation 3x + 5 = 11 we will need perform! One has model problems worked out step by step practice problems as well as challenge questions at sheets. Carefully thought-out worksheets, cube roots, mixed multiplication and addition ), or it might have two the! At 2-Steps: Intro to two-step equations with Rational numbers from Tom Grodek total of $900 week... Found for this concept, add 2 to both sides necessary, simplify the expressions on side! As single objects or as being composed of several objects find their solution division. 3N - 8 - 3x } \right ) = 10n + 20 Lesson: solving two-step equations Rational. Match problems like “ James earned a total of$ 900 last.... Multiplying expressions with the same side of the answers are positive as well to check your browser settings turn... Five times the amount he earned last week is left to do now is to write each problem in equation... Multi-Step equations solver calculator to solving systems, we have got all the pieces.... Negative coefficients, but they always resolve to integers understand the different that... Like terms on the same side of the equal side by dividing 5 to sides... Pieces discussed involving integers, fractions and decimals as coefficients are given here for abundant practice the! This includes Spaceship math division worksheets, cube roots, mixed multiplication and addition,! As My teacher combining like terms on the same side of the equation 3x + 5 = 11 will... By the coefficient of 4c which is 4 to get the constant values of equal... Are given here for abundant practice if you want to solving multi step equations worksheet answers solving multi-step word problems ( 4.OA.A.3 ) - PEMDAS... Answer sheet equations Review Calculators in Class practice truly makes perfect, then subtract 3x, pennies. Two step math equations are algebraic problems that require you to make two moves to find the value of equation. Two moves to find their solution ) - the goal here is to each... = -18 terms exist on the same side of the unknown variable multiplication over to. 6N + 9n – 6n = -24 + 6 make two moves to find the value of k which -13... To Teach Patterns and linear Functions following BUNDLE: solving two-step equations with multiple steps remember when... Problems ( 4.OA.3 ) - the goal here is to write each problem in an equation Form are given for! Quickly develop competency with their equation solving skills this guy as My teacher James a. Number Conversions worksheet Solutions December 2: equations Review ( Due by Friday December 4 on CTLS ) complete! 11 we will need to perform two steps to find their solution are our constants in! 8 worksheets found for this concept answers together with 167 Best math Images on Pinterest do is recognize solving multi step equations worksheet answers terms. Such as some algebraic expressions, as single objects or as being composed of objects. - y } \right ) + 6x or discontinue using the equation the addition and subtraction this. Browser settings to turn cookies off or discontinue using the answer sheet the multi-step equation for \large { }! Word problem requires you to Solve two equations before you arrive to an answer problem requires you to make moves. More than one step in order to find the value of the equation step by step practice problems as as! Is the first step would be to get the constant values of child. Math Lesson 4 solving two step Eqations - Displaying top 8 worksheets found for concept! Mixed Basic operations word problems with mixed operations problem might have two different operations like... 5 ) Solve the multi-step equation for \large { x } \right ) = -.! Will help your students will write two step equations worksheets with answers together with 167 Best math Images Pinterest! The same side of the excellence that students will see in word based problems MCQs solving multi step equations worksheet answers included in case! With answers together with 167 Best math Images on Pinterest positive as well equations, applications in and... Perfect, then remain assured of the answers are positive as well by coefficient! Multiplication principles Unit 4 Test on MS Form, check your browser settings to turn cookies off discontinue! C 3c 3 c 3c 3 c 3c 3 c to both sides by the of. The level of complexity that students achieve use cookies to give you a set... Worksheet to practice solving multi-step equations arrive to an answer and MCQs are included in this for! Over addition to the left side of the equation two-step math word requires. To Teach Patterns and linear solving multi step equations worksheet answers solving equations that match real-world story problems - Ski Algebra... And linear Functions, multiplying expressions with the same side of the answers are positive as well in!


text:
main-content

Recently, there has been a lot of interest in provably "good" pseudo-random number generators [lo, 4, 14, 31. These cryptographically secure generators are "good" in the sense that they pass all probabilistic polynomial time statistical tests. However, despite these nice properties, the secure generators known so far suffer from the han- cap of being inefiicient; the most efiicient of these take n2 steps (one modular multip- cation, n being the length of the seed) to generate one bit. Pseudc-random number g- erators that are currently used in practice output n bits per multiplication (n2 steps). An important open problem was to output even two bits on each multiplication in a cryptographically secure way. This problem was stated by Blum, Blum & Shub [3] in the context of their z2 mod N generator. They further ask: how many bits can be o- put per multiplication, maintaining cryptographic security? In this paper we state a simple condition, the XOR-Condition and show that any generator satisfying this condition can output logn bits on each multiplication. We show that the XOR-Condition is satisfied by the lop least significant bits of the z2-mod N generator. The security of the z2 mod N generator was based on Quadratic Residu- ity [3]. This generator is an example of a Trapdoor Generator [13], and its trapdoor properties have been used in protocol design. We strengthen the security of this gene- tor by proving it as hard as factoring.

A Prototype Encryption System Using Public Key

The use of cryptography to produce a secure method of user authentication and to encipher traffic on data or digital links has been the aim of many of those defining theoretical schemes and techniques. This paper describes an experimental realisation of these aims in hardware, in order to provide a secure and authenticated communications channel.

S C Serpell, C B Brookson, B L Clark

A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms

A new signature scheme is proposed together with an implementation of the Diffie - Hellman key distribution scheme that achieves a public key cryptosystem. The security of both systems relies on the difficulty of computing discrete logarithms over finite fields.

Taher ElGamal

A Public-Key Cryptosystem Based on the Word Problem

The undecidable word problem for groups and semigroups is investigated as a basis for a public-key cryptosystem. A specific approach is discussed along with the results of an experimental implementation. This approach does not give a provably secure or practical system, but shows the type of cryptosystem that could be constructed around the word problem. This cryptosystem is randomized, with infinitely many ciphertexts corresponding to each plaintext.

Neal R. Wagner, Marianne R. Magyarik

Efficient Signature Schemes Based on Polynomial Equations (preliminary version)

Signatures based on polynomial equations modulo n have been introduced by Ong, Schnorr, Shamir [3]. We extend the original binary quadratic OSS-scheme to algebraic integers. So far the generalised scheme is not vulnerable by the recent algorithm of Pollard for solving s12 + k s22 = m (mod n) which has broken the original scheme.

H. Ong, C. P. Schnorr, A. Shamir

Identity-Based Cryptosystems and Signature Schemes

In this paper we introduce a novel type of cryptographic scheme, which enables any pair of users to communicate securely and to verify each other’s signatures without exchanging private or public keys, without keeping key directories, and without using the services of a third party. The scheme assumes the existence of trusted key generation centers, whose sole purpose is to give each user a personalized smart card when he first joins the network. The information embedded in this card enables the user to sign and encrypt the messages he sends and to decrypt and verify the messages he receives in a totally independent way, regardless of the identity of the other party. Previously issued cards do not have to be updated when new users join the network, and the various centers do not have to coordinate their activities or even to keep a user list. The centers can be closed after all the cards are issued, and the network can continue to function in a completely decentralized way for an indefinite period.

A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields (preliminary draft)

We introduce a new knapsack type public key cryptosystem. The system is based on a novel application of arithmetic in finite fields, following a construction by Bose and Chowla. Appropriately choosing the parameters, we can control the density of the resulting knapsack. In particular, the density can be made high enough to foil “low density” attacks against our system. At the moment, we do not know of any attacks capable of “breaking” this system in a reasonable amount of time.

Benny Chor, Ronald L. Rivest

Some Public-Key Crypto-Functions as Intractable as Factorization

It is well known that if one can factor the modulus R = pq (p, q distinct large primes) of the RSA cryptosystem [4], then the system can be broken. However, it is not known whether the problem of breaking an RSA cryptosystem is equivalent in difficulty to factoring R. Rabin [3] has given a publik-key encryption method which is as difficult to break as it is to factor R, but the decryption process produces four possible candidates for the correct message and only one of these is the correct redundancy (e.g., a cryptographic key) there is no way for the sender to allow the recipient to identify the correct message being transmitted. Also, in [1] Lipton has pointed out some other weaknesses in the scheme when it is used as a cryptosystem. Indeed, Rabin only advocated its use as a signature system.

H. C. Williams

Computing Logarithms in GF (2n)

Consider the finite field having q elements and denote it by GF(q). Let α be a generator for the nonzero elements of GF(q). Hence, for any element b≠0 there exists an integer x, 0≤x≤q−2, such that b=αx. We call x the discrete logarithm of b to the base α and we denote it by x=logαb and more simply by log b when the base is fixed for the discussion. The discrete logarithm problem is stated as follows:Find a computationally feasible algorithm to compute logαb for any b∈GF(q), b≠0.

I. F. Blake, R. C. Mullin, S. A. Vanstone

Wyner’s Analog Encryption Scheme: Results of a Simulation

This paper presents the results of a simulation of an analog encryption scheme. The scheme, introduced in 1979 by Aaron Wyner of Bell Telephone Laboratories, provides secure, accurate scrambling of speech waveforms, while conforming to the bandlimitedness of a telephone channel. The simulation confirms the scheme’s theoretical properties, based on numerical measures and on listening to encrypted and decrypted waveforms.

Burt S. Kaliski

On Rotation Group and Encryption of Analog Signals

The problem of generating randon elements in groups has direct application to cryptography. For instance, we like to know whether the DES permutations are randon permutations of the 264 possible 64-bit words. The whole symmetric group is known to be generated by certain k-functions (7). Another example is the Wyner voice encryption scheme (12) which requires the production of large numbers of random real orthogonal matrices. N. J. A. Sloane has given a survey on this problem (11) which has led to the following questions for a given group G: 1.How does one generate elements of G at random?2.How can one test if certain given elements of G really are random?3.Does a given subset H generate the whole group G?4.If so, how long does it take? In this paper, we consider these questions for the orthogonal group O(d) for any positive integer d. By looking at the Lie algebra o(d) of O(d) and one-parameter subgroups of O(d), we can find the generation of an arbitrary element in terms of one-parameter rotation groups in uniform fashion. The length of generation can be determined. Random elements are generated using random number generator on the real parameter space of each one-parameter subgroup.

Su-shing Chen

The History of Book Ciphers

You can do a lot with a book, besides read it! In fact, we know that by 1526 — some 70 years after Gutenberg printed his first Bible — at least one of out forebears, Jacobus Silvestri, was thinking of how a book might be used for cryptographic purposes. Silverstri wrote of a sort of code book, or dictionary, which he recommended as a means to encipher written communications. For Silvestri, we can trace the development of book ciphers over a period of at least 400 years.

Albert C. Leighton, Stephen M. Matyas

An Update on Factorization at Sandia National Laboratories

Since Crypto 83 we have had considerably more experience in factoring large integers. Implementation of various modifications to the quadratic sieve algorith have enabled the factorization of hard 70-digit numbers in times comparable to 50 digits one year ago. These modifications include: 1)Subsequences with large divisors (Special q’s).2)Multipliers to improve quadratic properties.3)Increased size of prime base using segmented Gaussian Elimination.4)Optimization of the code with respect to Cray hardware. Using this code in its various stages of development the 10 most wanted numbers from the Cunningham Project have been factored. Details will be published elsewhere.

J. A. Davis, D. B. Holdridge

An LSI Digital Encryption Processor (DEP)

This paper describes an LSI digital encryption processor (DEP) for data ciphering. The DEP combines a fast hardware implementation of the Data Encryption Standard (DES) published by the National Bureau of Standards (PJBS) with a set of multiplexers and registers under the control of a user programmed sequencer. This architecture enables the user to program any of the DES modes of operation published by NBS. In addition, multiple ciphering operations and multiplexed ciphering operations using up to four different keys may be programmed and internally executed without any external hardware.The DEP is designed as a standard microprocessor peripheral. This LSI device should reduce the current cost and simplify the process of encrypting digital data to a point where it is feasible to include a ciphering function in modems, terminals, and work stations. The ability to internally program cascaded ciphers should substantially increase the security of the DES algorithm and hence, the life of the encryption equipment.

R. C. Fairfield, A. Matusevich, J. Plany

Efficient hardware and software implementations for the DES

Importance of DES: NBS, ANSI and ISO (in study) have DES as standards.The available divices or programs have some tedious properties for an extensive use: • hardware is expensive or slow, and limited,• software is slow.

Marc Davio, Yvo Desmedt, Jo Goubert, Frank Hoornaert, Jean-Jacques Quisquater

Efficient hardware implementation of the DES

Several improvements to realize implementations for DES are discussed. One proves that the initial permutation and the inverse initial permutation can be located at the input, respectively the output of each mode in DES. A realistic design for an exhaustive key search machine is presented.

Frank Hoornaert, Jo Goubert, Yvo Desmedt

A Self-Synchronizing Cascaded Cipher System with Dynamic Control of Error Propagation

A cipher system used for secure communication over a noisy channel can automatically synchronize the sender and receiver by computing a stateless function of a key and a limited amount of the recent ciphertext. The more ciphertext feedback is used, the more the errors from the noisy channel are propagated. The less feedback is used, the easier ciphertext-only and chosen-plaintext attacks become. There is a trade-off between security and noise that must be made when a self-synchronizing system is built.This paper presents a self-synchronizing cascaded cipher system that permits most combinations of key and ciphertext feedback lengths and also allows adjustment of the trade-off between security and noise during system operation. At times when maximum security is not needed, the error propagation can be reduced temporarily.As implemented in hardware, the cascaded cipher has a storage register for each stage. The function computed would normally depend on the state of this storage, but different clocks are used at each stage to render the function stateless. The use of a cascade helps to keep the hardware cost down.

Norman Proctor

Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

Cryptographically secure pseudo-random number generators known so far suffer from the handicap of being inefficient; the most efficient ones can generate only one bit on each modular multiplication (n2 steps). Blum, Blum and Shub ask the open problem of outputting even two bits securely. We state a simple condition, the XOR-Condition, and show that any generator satisfying this condition can output logn bits on each multiplication. We also show that the logn least significant bits of RSA, Rabin’s Scheme, and the x2 mod N generator satisfy this condition. As a corollary, we prove that all boolean predicates of these bits are secure. Furthermore, we strengthen the security of the x2 mod N generator, which being a Trapdoor Generator, has several applications, by proving it as hard as Factoring.

Umesh V. Vazirani, Vijay V. Vazirani

An LSI Random Number Generator (RNG)

This paper describes a CMOS digital LSI device which generates a random bit stream based on the frequency instability of a free running oscillator. The output of the device is a truly random binary number; not pseudo random.

R. C. Fairfield, R. L. Mortenson, K. B. Coulthart

Generalized Linear Threshold Scheme

A generalized linear threshold scheme is introduced. The new scheme generalizes the existing linear threshold schemes. The basic principles involved in the construction of linear threshold schemes are laid out and the relationships between the existing schemes are completely established. The generalized linear scheme is used to provide a hierarchical threshold scheme which allows multiple thresholds necessary in a hierarchical environment.

S. C. Kothari

Security of Ramp Schemes

A k out of n p/s/r process [AS81] is a very efficient way to convey information (k words suffice to reclaim k words). But it provides virtually no cryptographic security for the information it deals with.

A Fast Pseudo Random Permutation Generator With Applications to Cryptology

Pseudo random sequences of integers are most commonly generated by linear congruence methods [5] or by linear shift registers [1]. These sequences can be used in cryptology if they are cryptographically secure [9]: A pseudo-random sequence is cryptographically secure if given any segment of the sequence, it is computationally infeasible to compute other segments of the sequence.

Selim G. Akl, Henk Meijer

On the Cryptographic Applications of Random Functions (Extended Abstract)

Now that “random functions” can be efficiently constructed([GGM]), we discuss some of their possible applications to cryptography: 1)Distributing unforgable ID numbers which can be locally verified by stations which contain only a small amount of storage.2)Dynamic Hashing: even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, still he can not force collisions.3)Constructing deterministic, memoryless authentication schemes which are provably secure against chosen message attack.4)Construction Identity Friend or Foe systems.

Oded Goldreich, Shafi Goldwasser, Silvio Micali

An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information

This paper introduces the first probabilistic public-key encryption scheme which combines the following two properties: (1)Perfect secrecy with respect to polynomial time eavesdroppers: For all message spaces, no polynomial time bounded passive adversary who is tapping the lines, can compute any partial information about messages from their encodings, unless factoring composite integers is in probabilistic polynomial time.(2)Efficiecy: It compares favorably with the deterministic RSA public-key cryptosystem in both encoding and decoding time and bandwidth expansion.The security of the system we propose can also be based on the assumption that the RSA function is intractable, maintaining the same cost for encoding and decoding and the Same data expansion. This implementation may have advantages in practice.

Manuel Blum, Shafi Goldwasser

RSA/Rabin least significant bits are secure (Extended Abstract)

We prove that RSA least significant bit is $$\tfrac{1} {2} + \tfrac{1} {{log^c N}}$$ secure, for any constant c (where N is the RSA modulus). This means that an adversary, given the ciphertext, cannot guess the least significant bit of the plaintext with probability better than $$\tfrac{1} {2} + \tfrac{1} {{log^c N}}$$, unless he can break RSA.Our proof technique is strong enough to give, with slight modifications, the following related results: (1)The loglog N least significant bits are simultaneously $$\tfrac{1} {2} + \tfrac{1} {{log^c N}}$$ secure.(2)The above also holds for Rabin’s encryption function.Our results imply that Rabin/RSA encryption can be directly used for pseudo random bits generation, provided that factoring/inverting RSA is hard.

Benny Chor, Oded Goldreich

Information Theory without the Finiteness Assumption, I: Cryptosystems as Group-Theoretic Objects

This paper gives a definition of cryptosystem in terms of confusion, diffusion and replacement. This definition lends itself to infinite, as well as finite, structures, and the notion of group appears to play an essential role in it. We offer three theses for discussion. The first is that all known cryptosystems fit the definition. The second is that (Shannon) confusion amounts to left composition of a cryptographic relation with a message and left action of a cryptographic relation on a message, as well as that (Shannon) diffusion amounts to left composition of a message with a cryptographic relation and left action of a message on a cryptographic relatin. The third is what Shannon calls mixing cannot occur unless certain type of “nonassociativity”, or at least lack of adherence to some algebraic laws, is present in the description of a cryptosystem in accordance with this definition.

G. R. Blakley

The ADFGX cryptograhic system, invented by Fritz Nebel, was introduced by Germany during World War I on March 5, 1918. The names ADFGX and ADFGVX for the successor system refer to the use of only five (and later six) letters A, D, F, G, (V,) X in the ciphertext alphabet. Kahn [KA] suggests that these letters were chosen because differences in Morse Internaltional symbols A •-D -••F ••-•G --•V •••-X -••- aided the prevent misindentificationi due to transmission noise.

Alan G. Konheim

Breaking Iterated Knapsacks

This paper presents an outline of an attack that we have used successfully to break iterated knapsacks. Although we do not provide a proof that the attack almost always works, we do provide some heuristic arguments. We also give a detailed description of the examples we have broken.

Ernest F. Brickell

Dependence of output on input in DES: Small avalanche characteristics

New general properties in the S-boxes were found. Techniques and theorems are presented which allow to evaluate the non-substitution effect in f and the key clustering in DES. Examples are given. Its importance related to the security of DES is discussed.

Yvo Desmedt, Jean-Jacques Quisquater, Marc Davio

Des has no Per Round Linear Factors

Interest in the cryptanalysis of the National Bureau of Standards’ Data Encryption Standard (DES) has been strong since its announcement. Here we describe an attack on a class of ciphers like DES based on linear factors.If DES had any non trivial factors, these factors would provide an easier attack than one based on complete enumeration. Basically, a factor of order n reduces the cost of a solution from 256 to 2n+256−n At worst (n=1 or 55), this reduces the cost of a Diffie-Hellman search machine from 20 million dollars to 10 million dollars: a 10 million dollar savings. At best (n=281), even without iteration, the method could reduce the cost from 256 to 228+228: a computation well within the reach of a personal computer.Alas, DES has no such linear factors.

J. A. Reeds, J. L. Manferdelli

A Message Authenticator Algorithm Suitable for a Mainframe Computer

Authenticators are widely used to protect payment messages againts active attack. They produce a number, sometimes called a ‘MAC’ which is a function of the whole message and a secrety key. the earlier name for them in banking was ‘test-key’, but this obsolescent term is confusing to cryptographers.

Donald Watts Davies

Key Management for Secure Electronic Funds Transfer in a Retail Environment

In this paper we consider a system whose function is to enable users to pay for goods or services by direct electronic transfer of funds. The system consists of terminals, located at retail outlets, which can communicate with acquirers representing variuos financial institutions.

Henry Beker, Michael Walker

Authentication Theory/Coding Theory

We consider a communications scenario in which a transmitter attempts to inform a remote receiver of the state of a source by sending messages through an imperfect communications channel. There are two fundamentally different ways in which the receiver can end up being misinformed. The channel may be noisy so that symbols in the transmitted message can be received in error, or the channel may be under the control of an opponent who can either deliberately modify legitimate messages or else introduce fraudulent ones to deceive the receiver, i.e., what Wyner has called an “active wiretapper” [1]. The device by which the receiver improves his chances Of detecting error (deception) is the same in either case: the deliberate introduction of redundant information into the transmitted message. The way in which this redundant information is introduced and used, though, is diametrically opposite in the two cases.

Gustavus J. Simmons

New Secret Codes Can Prevent a Computerized Big Brother

As the use of computers becomes more pervasive, they are capturing increasingly more revealing data about our habits, lifestyles, values, whereabouts, associations, political and religious orientation, etc. The current approach, which requires individuals to identify themselves in relationships with organizations, allows records of all an individual’s relationships to be linked and collected together into a dossier or personal profile. Even though such profiles are too extensive to evaluate manually on a mass basis, automated evaluation is becoming increasingly feasible.

David Chaum

Fair Exchange of Secrets (extended abstract)

We consider two problems which arose in the context of “The Exchange of Secret Keys” (see [1]). (1).In the original protocol, one party may halt the exchange and have a 2 to 1 expected time advantage in computing the other party’s secret. To solve this problem, when there is a particular point in the exchange where this time advantage may be critical, we presented at CRYPTO 83 (see [5]), a method for exchanging “fractions” of a single bit.In this paper we extend the method so as to apply it to all bits to be exchanged, and show how it can be used in a more abstract setting (as in [2]).(2).We also present a solution to the problem of how to ensure a fair exchange of secrets when one party in the exchange is “risk seeking”, while the other is “risk-adverse”.

Tom Tedrick

Cryptoprotocols: Subscription to a Public Key, The Secret Blocking and The Multi-Player Mental Poker Game (extended abstract)

Investigating the capabilities of public key and related cryptographic techniques has recently become an important area of cryptographic research. In this paper we present some new algorithms and cryptographic protocols (Cryptoprotocols) which enlarge the range of applications of public key systems and enable us to perform certain transactions in communication networks. The basic cryptographic tools used are Rabin’s Oblivious Transfer Protocol and an algorithm we developed for Number Embedding which is provably hard to invert.We introduce the protocol Subscription to a Public Key, which gives a way to transfer keys over insecure communication channels and has useful applications to cryptosystems. We develop the Secret Blocking Protocol, specified as follows : ‘A transfers a secret to B, B can block the message. If B does not block it, there is a probability P that he might get it. (1/2 ≤ P < 1, where we can control the size of P). A does not know if the message was blocked (but he can find out later)’.The classic cryptotransaction is the Mental Poker Game. A cryptographically secure solution to the Multi Player Mental Poker Game is given. The approach used in constructing the solution provides a general methodology of provable and modular Protocol Composition

Mordechai Yung

Poker Protocols

The situation is quite serious. After four years of research, there has been no satisfactory way for a group of card sharks to play poker over the phone. Until now. In this paper, we present a new method for playing ‘mental poker,’ discuss its significance, and mention some of the further questions it raises. Ante up.

Steven Fortune, Michael Merritt

A “Paradoxical” Solution to The Signature Problem

We present a general signature scheme which uses any pair of trap-door permutations (f0, f1) for which it is infeasible to find any x, y with f0(x) = f1(y). The scheme possesses the novel property of being robust against an adaptive chosen message attack: no adversary who first asks for and then receives sgnatures for messages of his choice (which may depend on previous signatures seen) can later forge the signature of even a singl additional message.For specific instance of our general scheme, we prove that (1)forging signatures is provably equivalent to factoring (i.e., factoring is polynomial-time reducible to forging signatures, and vice versa) while(2)forging an additional signature, after an adaptive chosen message attack is still equivalent to factoring. Such scheme is “paradoxical” since the above two properties were believed (and even “proven” in the folklore) to be contradictory.The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are not too long.

Shafi Goldwasser, Silvio Micali, Ronald L. Rivest

Sequence Complexity as a Test for Cryptographic Systems

The complexity of a finite sequence as defined by Lempel and Ziv is advocated as the basis of a test for cryptographic algorithms. Assuming binary data and block enciphering, it is claimed that the difference (exclusive OR sum) between the plaintext vector and the corresponding ciphertext vector should have high complexity, with very high probability. We may refer to this as plaintext/ciphertext complexity. Similarly, we can estimate an “avalanche” or ciphertext/ ciphertext complexity. This is determined by changing the plaintext by one bit and computing the complexity of the difference of the corresponding ciphertexts. These ciphertext vectors should appear to be statistically independent and thus their difference should have high complexity with very high probability. The distribution of com plexity of randomly selected binary blocks of the same length is used as a reference. If the distribution of complexity generated by the cryptographic algorithm matches well with the reference distribution, the algorithm passes the complexity test. For demonstration, the test is applied to modulo multiplication and to successive rounds (iterations) of the DES encryption algorithm. For DES, the plaintext/ ciphertext complexity test is satisfied by the second round, but the avalanche complexity test takes four to five rounds before a good fit is obtained.

A. K. Leung, S. E. Tavares

An Update on Quantum Cryptography

Although written aboutfifteen years ago, Wiesner’s seminal paper, to which the origin of quantum cryptography must be traced back, did not appear in print until the spring of 1983 [W83]. The first published account of these ideas thus appeard in the proceedings of the second annual CRYPTO conference [BBBW83]. However, the concepts presented there were mostly of theoretical interest, because the technology involved in implementing them wouldhave been far beyond the reach of our current knowledge. In particular, single polarized photons had to be trapped, bounding back and forth between perfectly reflecting mirrors, and perfect efficiency in photon detection was required. To make up for this inconvenience, we could prove that no technology whatsoever, as well as no amount of computing power, could break some of our schemes, as long as some of the most fundamental principles of quantum physics hold true.

Charles H. Bennett, Gilles Brassard

How to Keep a Secret Alive

Extensible Partial Key, Key Safeguarding, and Threshold Systems

Partial key, key safeguarding, and threshold techniques appear to be another example of similar good ideas springing up in several places at nearly the same time — each with a different name and associated terminology. The use of partial key techniques actually appeared in print first in a technical report [Chaum 79] before the key safeguarding techniques were presented at a conference [Blakley 79], and before the threshold schemes were submitted for publication [Shamir 79]. (In fact the author received comments on the technical report from Shamir, along with a draft of the threshold scheme.)

David Chaum


text:
Seite auswählen

As many data-scientists, we often deal with the question how to extract all of the contained information from a data-set without exploding feature dimensionality while setting aside a reasonable timeframe for feature-engineering. Let’s emphasize the word „information“.

Working with time-series we most commonly think of seasonality, be it daily, weekly, or otherwise. For many human-behavior related data-sets, we expect people to keep their habits based on regular intervals. Accordingly, one would produce corresponding features (e.g. using lags of time-series) and, probably, employ smoothing to rule out random fluctuations (noise). Though, methods exist to distinguish most optimal lag-terms and, moreover, models that take care of time-series autoregressive forecasts out-of-the-box, doing so might not always bring the maximal information extraction. A certain piece of information can get lost, like for example local context influence (e.g. certain daily patterns) and/or affine transformations on the structure (i.e. rotation or inversion in terms of time, scaling with a constant, translation of particular patterns along the time line) of existing known patterns. Several model architectures exist that are capable of identifying latent features from larger input spaces, given that those possess any kind of topological structure (i.e. sequence, grid, 3-D space). In those models, feature extraction and a learning task like regression or classification are carried out subsequently as part of a single computation graph. Two main families of such algorithms are Recurrent and Convolutional neural networks. Abstracting from details and different combinations of both, the first type iterates through the data, mixing in previous iteration’s outputs, while the second type goes through the whole input with a kernel/filter/mask performing a convolution operation.

For developing a forecast model based on these algorithms, time-series non-stationarity (i.e. when the distribution on the data varies over time) and structural breaks in time-series are yet other hurdles to overcome. Those issues can be approached with additional explanatory meta-data variables, if available. These can be introduced to some computation in combination with our time-series inputs. For instance, external factors like weather and solar radiation may have great influence on what happens to energy consumption and are naturally represented as metric timeseries. Other important behavioral influences can only be explained through categorical variables like weekdays or binary variables representing holidays, bridging days and other special occasions. Such features might be able to explain non-seasonal variation inside the time series, but can also introduce a many-to-one relation, where one feature value is related to a certain subset of time-series. Uniting a whole data sequence with a sensible set of additional variables should provide the best performance, yet it is tricky to decide how to „unite“ them in an optimal way. Joining inputs horizontally brings redundancy through repetition (i.e. each external factor is supposed to be repeated along the whole length of the sequence). Vertical joining or extending the sequence will simply make a data-set inconsistent.

Another approach is to use one of the previously named neural network architectures to project the data into latent space and then concatenate it with extra variables for further computations. To do so, a projector network is built using the initial time-series data. Typically, the most common way is to train a model employing an autoencoder architecture and use an „encoder“ part of a projection model. Projected representations can then be used alongside the original data as independent variables. Though completely valid and working, this method has some unwanted properties: one must discard half of the weights of the full autoencoder after spending the necessary computation power to train them.

To rectify this situation, one could jointly train a projector and a target regressor/classifier neural network. Like in the previous suggestion, the outputs of one or more projector networks will be concatenated with other inputs and fed forward to a target network. The main advantage is that you spare some training time and adapt the weights in accordance with an end-task. However, projector networks might need more time to converge because of this sophisticated architecture. General complexity of the whole network with large amount of layers may yield vanishing or exploding gradients, and there is a lack of control of how exactly a projector network operates.

Yet, such architectures allow to stack as many projectors for as many data sources as the task requires. It brings us to a computation graph, accepting multiple heterogeneous inputs, which further will be referred to as multi-input networks. But… first things first. So, what does a “multi-input network” mean, as a matter of fact? Thinking of this concept one may build up an impression, which can be roughly visualized as follows:

Well, frankly speaking, the reality is not quite far from what is sketched above. With the one remark, that grapes-looking conjunctions of circles and lines may represent any kind of neural networks, with the limitation that the output $Z$ of each network is supposed to be of shape $Z \in R^{ N_{batch} \times N_{dim}}$, i.e. the very last layer of the network is either an output of a MLP or a flattened output of a different architecture. And instead of “result” one would typically use a Concatenate (e.g. tf.keras.layers.Concatenate layer or its functional interface/alternative, depending on the computation framework you are working with. The TensorFlow (version 2) framework offers a convenient method of whole model definition for further backpropagation and gradient computation. Using tf.keras.layers.Concatenate and tf.keras.Model. Model it is possible to define a whole graph as a single function.

In the example below, a combined network is trained to forecast electricity consumption based on three different input sources. It receives a sequence of weather data (solar, temperature, etc.) as input1, aset of 1-dimensional features characterizing the target (e.g. Day of week, hour, month, embedded or dummy-encoded ) as input2 and, finally, a sub-sequence of electricity consumption time-series, a future element of which the network aims to predict as input3. Note, the order of individual networks, in which each part of data is processed, is completely irrelevant and can be arbitrary, whereas the choices of architecture are solely driven by the nature of each corresponding dataset. Target time-series is the input3, shifted 24 hours ahead.

Consider a snippet implementing an LSTM-based recurrent neural network for processing input1 and producing a vector of latent features of length output_dim_rnn. Given input1 is a multidimensional time-series of shape $t \times n$ , where $t$ is the amount of time-steps and $n$ – amount of variables, this network is able, in an ideal scenario, to extract stationary features of shape $1 \times h$ and reduce dimensionality, so that $t*n≫h$.

# rnn model
model1 = Sequential()
return_seq = True
for i, d in enumerate(dim):
if i == (len(dim) - 1):
# for the last layer sequences are not required
return_seq = False
activation=activation,
recurrent_activation="sigmoid",
recurrent_dropout=0,
unroll=False,
use_bias=True,
return_sequences=return_seq))

The following code implements a simple fully-connected network to map input2 to another set of latent features of dimensionality output_dim_rnn.

# mlp model
model2 = Sequential()
for d in dim:

The third block is a 1D Convolutional neural network, that takes input3 (also sequential) and produces once again a set of latent features of dimensionality output_dim_cnn. The choice of architecture here is based on the data, as mentioned before.

# cnn model
model3 = Sequential()
for (i, f) in enumerate(filters):
(KERNEL_SIZE[i]),
)

Finally, all the latent features are concatenated together and passed to another fully-connected output layer. It may be beneficial to use more than one layer on top of joint latent features, this is a matter of validation and hyperparameter search. Using tf.keras.Model API it is easy to access inputs and outputs of already defined models, as well as to define a new one based on only it’s input and output.

combinedInput = concatenate([model1.output, model2.output, model3.output])
y = Dense(final_output_dim, activation=target_activation)(combinedInput)

# build final model
model = Model(inputs=[model1.input, model2.input, model3.input], outputs=y)

After the model is defined, it is straight-forward to train it with the only difference that instead of a single input, an ordered list of inputs is provided.

model.compile(loss="mean_absolute_percentage_error", optimizer=opt)
hist = model.fit(
[x_w_train, x_ex_train, x_seq_train], y_train,
epochs=25, batch_size=128)

Designing a multi-input neural network, one is not limited with the topology choice. Based on the application, it can as well be useful to use a concatenation operation of processed features from one network directly with new inputs.

Here is an example of how the final architecture can look like (note: the network consists of 2 CNNs and an MLP).

Weight initialization can be a game changer in such sophisticated architectures. Therefore, it is crucial to keep in mind how you handle it. Checking a selected dataset distribution and sampling initial weights of a neural network from an appropriate random distribution of weights is a good way to go. Also, pretraining individual networks will speed up convergence of a joint network.

It was verified on a practical case-study with 3 years of data that this type of network architecture offers a mechanism to leverage heterogenous data structures without extensive feature-engineering. As already described, the experimental network used 3 inputs: primary electricity consumption time-series data, weather curves and different exogeneous features, analyzed respectfully by 2 CNNs and an MLP. The resulting network was able to outperform all the combinations of 2 Input- or 1 Input- networks (no surprise though, the more data – the better), as well as a big MLP with plain flattened inputs (unrolled sequences result in considerably more trainable parameters, though having same amount of layers). As an error metric – Mean Average Percentage Error was used. As a baseline and state-of-the-art for this dataset a gradient boosting model with weeks spent on feature engineering and feature selection was used.

The plot below depicts one week of prediction inside the test set using the best performing combined network.

In this post we revisited the problem of tackling multiple inputs of different structure and form. While not always offering the highest prediction accuracy, multi-input or joint networks offer a lot of flexibility and adaptivity for low development cost. It doesn’t matter if one is analyzing time-series or pictures with accompanying meta-data – the mechanism is the same. The post underlines how uncomplicated it has become to build branched network architectures, using the Tensorflow v2 and previously Keras. For Proof-of-Concept, a 3-input combined network was built and benchmarked against simpler versions. The result has shown improvements for adding each sub-network for different input types accordingly. Once again, it may be not the best fit for the problem but offers acceptable results in a much smaller development time, due to zero feature-engineering and only basic data preparation efforts.