text:
## Monday, 5 October 2009

### Early LHC Discoveries

It seems that the LHC restart will not be significantly delayed beyond this November. The moment when first protons collide at 7 TeV energy will send particle theorists into an excited state. From day one, we will start harassing our CMS and ATLAS colleagues, begging for a hint of an excess in the data, or offering sex for a glimpse on invariant mass distributions. That will be the case in spite of the very small odds for seeing any new physics during the first months. Indeed, the results acquired so far by the Tevatron make it very unlikely that spectacular phenomena could show up in the early LHC. Although the LHC in the first year will operate at a 3 times larger energy, the Tevatron will have the advantage of 100 times larger integrated luminosity, not to mention the better understanding of their detectors.

Nevertheless, it's fun to play the following game of imagination: what kind of new physics could show up in the early LHC without having been already discovered at the Tevatron? For that, two general conditions have to be satisfied:
1. There has to be a resonance coupled to the light quarks (so that it can be produced at the LHC with a large enough cross section) whose mass is just above the Tevatron reach, say 700-1000 GeV (so that the cross section at the Tevatron, but not at the LHC, is kinematically suppressed).
2. The resonance has to decay to electrons or muons with a sizable branching fraction (so that the decay products can be seen in relatively clean and background-free channels).
It turns out, however, that even these two favorable conditions may not guarantee an early discovery. The example of the Z' gauge boson is a good illustration here. In the particle slang, Z' refers to a new vector boson, a sort of a heavy photon, associated to a new broke U(1) gauge symmetry beyond the standard model. There is no particular motivation for such a creature to exist at the TeV scale, but the potentially large production cross section and clean experimental signatures (typical Z' couples to both the quarks and the leptons) make it the common case study for an early LHC discovery. Unfortunately, the existing bounds from LEP and the Tevatron forbid a large number of Z' events in the early LHC, as shown in this neat paper.

The possible couplings of Z' to quarks and leptons can be theoretically constrained: imposing anomaly cancellation, flavor independence, and the absence of exotic fermions at the TeV scale implies that the charges of the new U(1) acts on the standard model fermions as a linear combination of the familiar hypercharge and the B-L global symmetry. Thus, one can describe the parameter space of these Z' models by just three parameters: two couplings gY and gB-L and the Z' mass. This simple parametrization allows us to quickly scan through all possibilities. An example slice of the parameter space for the Z' mass 700 GeV is shown on the picture to the right. The region allowed by the Tevatron searches is painted blue, while the region allowed by electroweak precision tests is pink (the coupling of Z' to the electrons induces effective four-fermion operators that have been constrained by the LEP-II experiment). As you can see, these two constraints imply that both couplings have to be smallish, of order 0.2 at the most, which is even less than the hypercharge coupling g' in the standard model. That in turn implies that the production cross section at the LHC will be suppressed. Indeed, the region where the discovery at the LHC with 7 TeV and 100 inverse picobarns is impossible, marked as yellow, almost fully overlaps with the allowed parameter space. Only a tiny region (red arrow) is left for that particular mass, but even that pathetic scrap is likely to be wiped once the Tevatron updates their Z' analyses.

The above example illustrates how difficult is to cook up a model suitable for an early discovery at the LHC. A part of the reason why Z' is not a good candidate is that it is produced by quark-antiquark collisions. That is a frequent occurrence in the proton-antiproton collider like the Tevatron, whereas at the LHC, who is a proton-proton collider, one has to pay the PDF price of finding an antiquark in the proton. An interesting way out that goes under the name of diquark resonance was proposed in another recent paper. If the new resonance carries the quantum numbers of two quarks (rather than quark-antiquark pair) then the LHC would have a tremendous advantage over the Tevatron, as the resonance could be produced in quark-quark collisions that are more frequent at the LHC. Because of that, a large number of diquark events may be produced at the LHC in spite of the Tevatron constraints. The remaining piece of model building is to ensure that the diquark resonance decays to leptons often enough.

Diquarks are not present in the most popular extensions of the standard model and therefore they might appear to be artificial constructs. However, they can be found in somewhat more exotic models like for example the MSSM with a broken R-parity. That model allows for couplings like $u^c d^c \tilde b^c$, where $u^c,d^c$ are right-handed up and down quarks, while $\tilde b^c$ is the scalar partner of the right-handed bottom quark called the (right) sbottom. Obviously, this coupling violates R-symmetry because it contains only one superparticle (in the standard MSSM, supersymmetric particles couple always in pairs). The sbottom could then be produced by collisions of up and down quarks, both of which are easy to find in protons.

Decays of the sbottom are very model dependent: the parameter space of supersymmetric theories is as good as infinite and can accommodate numerous possibilities. Typically, the sbottom will undergo a complex cascade decay that may or may not involve leptons. For example, if the lightest supersymmetric particle is the scalar partner of the electron, then the sbottom can decay into a bottom quark + a neutralino who decays into an electron + a selectron who finally decays into an electron and 3 quarks:
$\tilde b^c -> b \chi^1 -> b e \tilde e -> b e e j j j$
As a result, the LHC would observe two hard electrons plus a number of jets in the final state, something that should not be missed.

To wrap up, the first year at the LHC will likely end up being an "engineering run", where the standard model will be "discovered" to the important end of calibrating the detectors. However, if the new physics is exotic enough, and the stars are lucky enough, then there might be some real excitement store.

Lumo said...

Hi Jester, do you really think that the energy enhancement is so irrelevant?

I actually bet that the LHC is more likely to find new physics during the first two months than during the two following years combined.

Jester said...

As I was trying to say in the post, in most cases Tevatron excludes early discoveries at LHC. Only exotic scenarios remain open.

Chris said...

Thanks for this nice post!

so the first LHC months will be interesting, because if something shows up, it is bound to be cool. probably not as cool as the first results the LHC has already delivered (arXiv:0910.0359 :-) ) but still..

a quantum diaries survivor said...

Lubos, I take your bet to mean "I think the LHC will discover something during the first two months", since you do believe it will discover something sometimes, right ?

In that case, I take your bet.

And a moment after, I am going to explain that the most likely energy for startup is 2.16 TeV. No kidding.

Cheers,
T.

joder said...

I find it quite strange that after booting up the lch still no real discoveries have been made...
Well atleast there is no black hole untill now... that's something :-)


text:
# Similar Artists

1. We don't have a wiki here yet...
2. We don't have a wiki here yet...
3. We don't have a wiki here yet...
4. We don't have a wiki here yet...
5. We don't have a wiki here yet...
6. We don't have a wiki here yet...
7. We don't have a wiki here yet...
8. We don't have a wiki here yet...
9. We don't have a wiki here yet...
10. We don't have a wiki here yet...
11. We don't have a wiki here yet...
12. We don't have a wiki here yet...
13. We don't have a wiki here yet...
14. We don't have a wiki here yet...
15. Śpiewa od najmłodszych lat. Wyrastał - jak całe jego pokolenie - zafascynowany rock'n'rollem i R&B, słuchał Beatlesów i Stonesów, ale ze…

16. We don't have a wiki here yet...
17. We don't have a wiki here yet...
18. We don't have a wiki here yet...
19. We don't have a wiki here yet...

format: plain


text:
# System response with initial condition

I have a small problem figuring out how to properly solve that. I could use help.

Say a system with a transfer function $H(s) = \frac{100}{0.4s + 1}$ is excited with an excitation $u(t) = 8V$ since very long (steady state). At time $t_1$, $u(t)$ is abruptly set to 0V. What is the value of y(t) at time $t_1$ + 0.1?

I calculate steady state value (before time $t_1$) using laplace final value theorem: $$U_0(s) = 8V \\ Y_0(s) = H(s) \cdot U_0(s) = \frac{800}{s(0.4s + 1)} \\ y_0 = \lim_{s \to 0} sY_0(s) = 800$$

I have a first order linear system, so the form is (including initial conditions): $$Y(s) = H(s)U(s) + C(s) = \frac{K}{\tau s + 1}U(s) + \frac{\tau y_0}{\tau s + 1}$$

Since at time $t_1$, u(t) goes from 8V to 0V abruptly, I conclude the excitation at this instant is a negative step of 8V, i.e. $U_1(s) = -\frac{8}{s}$. So I guess I have to calculate the response at time 0.1 of a negative step of -8V with initial condition $y_0 = 800V$ to obtain the correct answer.

So the general response $Y_1(s)$ at $t = t_1$ will be: $$Y_1(s) = H(s)U_1(s) + C(s) = \frac{-800}{s(0.4s + 1)} + \frac{320}{0.4s + 1}$$

Doing the inverse Laplace of this expression I get: $$y_1(t) = 1600 e^{- 2.5t} - 800$$

Knowing this, finding y(t) at $t = t_1 + 0.1$ would correspond to $y_1(0.1)$, which gives 446.08.

Well the answer should be 623.04. Could someone explain me what I'm doing wrong? I feel I did everything correctly.

The transfer function corresponds to a first order system, you can either assume that it's an RL or RC network with input voltage.

For unit step input of 8v,

Y(s) = 800/s.(0.4s+1) = 250 /s.(s+2.5).

By partial fractions and taking inverse laplace,

y(t) = 800 (1 - exp(-2.5.t) ).

At steady steady state y(t) =800 V.

Now, this can thought as an RC circuit with 800 volts input, so that at steady state the capacitor is charged to 800 volts.

Once at t = to, say you short the source ( Vin = 0 ),the capacitor discharges through the resistor R .

We already know from equation of y(t) that the time constant (RC) = 1/2.5 = 0.4.

So,the capacitor discharges as follows:

y(t) = 800 exp(-2.5t).

At t = 0.1 (after source is shorted);

y(0.1) = 800 x 0.7788 = 623.04 volts.


text:
#### Similar Solved Questions

##### Using the data shown in Table $5.3,$ calculate the pressure exerted by 2.50 moles of $\mathrm{CO}_{2}$ confined in a volume of $5.00 \mathrm{~L}$ at $450 \mathrm{~K}$. Compare the pressure with that calculated using the ideal gas equation.
Using the data shown in Table $5.3,$ calculate the pressure exerted by 2.50 moles of $\mathrm{CO}_{2}$ confined in a volume of $5.00 \mathrm{~L}$ at $450 \mathrm{~K}$. Compare the pressure with that calculated using the ideal gas equation....
##### Plz do number 4, number 2 answer is 4.18*10^-6 ev 2. What should be the energy...
Plz do number 4, number 2 answer is 4.18*10^-6 ev 2. What should be the energy of an electron so that the associated electron waves have a wavelength of 600 nm? 3. Since the visible region spans between approximately 400 nm and 700 nm why can the electron wave mentioned in Problem 2 not be seen b...
##### Greenfield Consultants conducts analyses of public policy issues. The company has two units: Government (with various...
Greenfield Consultants conducts analyses of public policy issues. The company has two units: Government (with various U.S. government agencies as the only clients) and Corporate (with several corporations as clients). Government business is charged based on the total costs (direct and indirect) plus...
##### Recommendations for Primary Billary Cirrhosis Explain what the patient or nurse should do to continue the...
Recommendations for Primary Billary Cirrhosis Explain what the patient or nurse should do to continue the recovery and improvement of the patient who has primary biliary cirrhosis....
##### Homework: 2.3. Arc length and curvature Score: 0 of 1 pt 4 of 11 (4 complete)11.5.4Find the radius of curvature of the curve rsr? -.Zj-tk at the point where t =1.The radius of curvature of the curver =t?1 -(?1-tk at the point where t = (Type an exact answer:)luvzEnter your answer in the answer box and then click Check Answer:All parts showingClear AlI
Homework: 2.3. Arc length and curvature Score: 0 of 1 pt 4 of 11 (4 complete) 11.5.4 Find the radius of curvature of the curve rsr? -.Zj-tk at the point where t =1. The radius of curvature of the curver =t?1 -(?1-tk at the point where t = (Type an exact answer:) luvz Enter your answer in the answer ...
##### Point) Use a least squares approximation to find the best linear fit (i.e., the best line)L(t) = C + Dtwhich is closest; in the sense of least squares, to passing through the through the following data points:(t1,b1)(-3,13) (0, -11)(t2, b2)(t3,b3 _ = (3,-23)What are the y-intercept C and the slope D of this line?CD =
point) Use a least squares approximation to find the best linear fit (i.e., the best line) L(t) = C + Dt which is closest; in the sense of least squares, to passing through the through the following data points: (t1,b1) (-3,13) (0, -11) (t2, b2) (t3,b3 _ = (3,-23) What are the y-intercept C and the ...
##### Challenge set 2 (20points) NAMECLASSQuestion 1 (5 points)Draw wedge and dash projections of the following structures Name compoundsHO-OHOH
Challenge set 2 (20points) NAME CLASS Question 1 (5 points) Draw wedge and dash projections of the following structures Name compounds HO- OH OH...
##### Problem The latent heat of fusion (solid become liquid) for ice is 79.8 cal/gram
ProblemThe latent heat of fusion (solid become liquid) for ice is 79.8 cal/gram. How much ice can we melt with 1000 calories of heat?ProblemWhich would require more heat, melting 500 g of 0 C ice or turning 500 g of 100 C water into steam?ProblemA 500 g sample of an unknown material requires 750 cal...
##### 1VH H W 1 the H from lowest highest Rf 1 standard1
1 VH H W 1 the H from lowest highest Rf 1 standard 1...
##### Ptc < Uras9 chop recied 31,030 Ivoice Shnc daled August 01 Kich 2/10, 1/15,n/60 torns 5266 parial pWmentWhal credit Juka Src TACeha (Round Ycui anbmolneahuei contCradilWhat Siaty& out-tanding bolarco? (Rquun YOH 9h8wo| the Wearust curt ) Outalotlea FmeAlgs
ptc < Uras9 chop recied 31,030 Ivoice Shnc daled August 01 Kich 2/10, 1/15,n/60 torns 5266 parial pWment Whal credit Juka Src TACeha (Round Ycui anbmol neahuei cont Cradil What Siaty& out-tanding bolarco? (Rquun YOH 9h8wo| the Wearust curt ) Outalotlea Fme Algs...
##### How do you evaluate sin^-1(sin((19pi)/10))?
How do you evaluate sin^-1(sin((19pi)/10))?...
##### How do you determine the concavity of a quadratic function?
How do you determine the concavity of a quadratic function?...
##### 3 Consider the random variable T which has the following distributionValueFrobability1505a) Graph the distribution of T. b) Compute P(T < 7). Compute P(3 < T <10). 3 Compute P(T Z 10|T _ 6): Compute P(T Z 6/T < 7). Compute E(T): g) Compute SD(T):
3 Consider the random variable T which has the following distribution Value Frobability 15 05 a) Graph the distribution of T. b) Compute P(T < 7). Compute P(3 < T <10). 3 Compute P(T Z 10|T _ 6): Compute P(T Z 6/T < 7). Compute E(T): g) Compute SD(T):...
##### 7.Fredit the product(s) of the follawvin Ttacool (Bpls0} andp lerandc AeRLCandinGlve the [UPAC nama for the following cotpound (3pts) CHsc-ch c(ch)} 44-dimethyd-2-hexymd Duoechnlctneehntnme 5Grohm cuhuezthaxmeDebermnelne productprtht (pllowing ! ELaenmm (Jpts)62 Ch
7.Fredit the product(s) of the follawvin Ttacool (Bpls 0} andp lerandc AeRLCandin Glve the [UPAC nama for the following cotpound (3pts) CHsc-ch c(ch)} 44-dimethyd-2-hexymd Duoechnlctneehntnme 5Grohm cuhuezthaxme Debermnelne productprtht (pllowing ! ELaenmm (Jpts) 62 Ch...
##### Recall that function f : A > R is differentiable at a â‚¬ A iff (a lim 4~0f(a)exists The limit_ if exists, is denoted by f' (a). Suppose that differentiable function on R. For c R show that f(a h) f'(a).(6) Let and 9 be functions defined 0n 2 andf(~ lim A_Of(x9(1)If f is differentiable at 2 = 4, then prove that f' (a) = g(a). Find function and point such that g(a) exists but differentiable atis not
Recall that function f : A > R is differentiable at a â‚¬ A if f (a lim 4~0 f(a) exists The limit_ if exists, is denoted by f' (a). Suppose that differentiable function on R. For c R show that f(a h) f'(a). (6) Let and 9 be functions defined 0n 2 and f(~ lim A_O f(x 9(1) If f is dif...
##### Mathematics Of Finance: Problem 3 Previous Problem Problem List Next Problempolnt) Ted and Christine want purchase. nouse Suppose they invest 4U0 dollars per month Into = murua fund How nkh Wl they have Ir @ payment aner vears M the Per annum Tate tetur 0t the mutual fund alaunetdio 9.5 peicent t compouded monthb?
Mathematics Of Finance: Problem 3 Previous Problem Problem List Next Problem polnt) Ted and Christine want purchase. nouse Suppose they invest 4U0 dollars per month Into = murua fund How nkh Wl they have Ir @ payment aner vears M the Per annum Tate tetur 0t the mutual fund alaunetdio 9.5 peicent t ...
##### (1 point) For the circuit below, V1 = 13 V, V2 = 8 V, V3 =...
(1 point) For the circuit below, V1 = 13 V, V2 = 8 V, V3 = -2 V. L1 = 22 mH, L2 = 18 mH, L3 = 46 mH. R1 = 22 12, R2 = 26 12, R3 = 25 12, R4 = 8 12, R5 = 47 12, R6 = 22 12, Find (a) i1, (b) i2, (C) v. 1+ RG V2 min to-rööviz w ell + V3 Zamo 2013 Paul Hummel BY NC SA (A) 11 = (B) 12 = < D ...
##### Question 7 (1 point) Which of the following statements is correct? A) One disadvantage of forming...
Question 7 (1 point) Which of the following statements is correct? A) One disadvantage of forming a corporation is that it makes it easier for the firm to raise capital. B) One advantage of forming a corporation is that it subjects the firm to fewer regulations. C) One disadvantage of forming a corp...
##### Give the IUPAC names for the following compounds: A) B) HO
Give the IUPAC names for the following compounds: A) B) HO...


text:
# Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$

Proposition 4.6.4.10. Let $\operatorname{\mathcal{C}}$ be an $\infty$-category containing an object $X$. Then the projection map $\{ X\} \operatorname{\vec{\times }}_{\operatorname{\mathcal{C}}} \operatorname{\mathcal{C}}\rightarrow \operatorname{\mathcal{C}}$ is a left fibration and the projection map $\operatorname{\mathcal{C}}\operatorname{\vec{\times }}_{\operatorname{\mathcal{C}}} \{ X\} \rightarrow \operatorname{\mathcal{C}}$ is a right fibration.

Proof. We will prove the second assertion; the first follows by a similar argument. Let $A \hookrightarrow B$ be a right anodyne morphism of simplicial sets; we wish to show that every lifting problem

$\xymatrix@R =50pt@C=50pt{ A \ar [r] \ar [d] & \operatorname{\mathcal{C}}\operatorname{\vec{\times }}_{\operatorname{\mathcal{C}}} \{ X\} \ar [d] \\ B \ar [r] \ar@ {-->}[ur] & \operatorname{\mathcal{C}}}$

admits a solution. Unwinding the definitions, we are reduced to showing that a map of simplicial sets

$\sigma _0: B \coprod _{A} (A \diamond \{ X\} ) \rightarrow \operatorname{\mathcal{C}}$

can be extended to a map $\sigma : B \diamond \{ X\} \rightarrow \operatorname{\mathcal{C}}$ (see Notation 4.5.8.3). By virtue of Lemma 4.5.5.2, it will suffice to show that the inclusion map

$\iota : B \coprod _{A} ( A \diamond \{ X\} ) \hookrightarrow B \diamond \{ X\}$

is a categorical equivalence of simplicial sets, which follows from Corollary 4.5.8.14. $\square$


text:
## 4.4 Deterministic Policy Gradient (DPG)

So far, the actor produces a stochastic policy $$\pi_\theta(s)$$ assigning probabilities to each discrete action or necessitating sampling in some distribution for continuous actions (see Section 4.2.4). The main advantage is that stochastic policies ensure exploration of the state-action space: as most actions have a non-zero probability of being selected, we should not miss any important reward which should be ignored if the greedy action is always selected (exploration/exploitation dilemma).

There are however two drawbacks:

1. The policy gradient theorem only works on-policy: the value of an action estimated by the critic must have been produced recently by the actor, otherwise the bias would increase dramatically (but see importance sampling, Section 4.3). This prevents the use of an experience replay memory as in DQN to stabilize learning. Importance sampling can help, but is unstable for long trajectories.
2. Because of the stochasticity of the policy, the returns may vary considerably between two episodes generated by the same optimal policy. This induces a lot of variance in the policy gradient, which explains why policy gradient methods have a worse sample complexity than value-based methods: they need more samples to get rid of this variance.

Successful value-based methods such as DQN produce a deterministic policy, where the action to be executed after learning is simply the greedy action $$a^*_t = \text{argmax}_a Q_\theta(s_t, a)$$. Exploration is enforced by forcing the behavior policy (the one used to generate the sample) to be stochastic ($$\epsilon$$-greedy), but the learned policy is itself deterministic. This is off-policy learning, allowing to use a different policy than the learned one to explore. When using an experience replay memory, the behavior policy is simply an older version of the learning policy (as samples stored in the ERM were generated by an older version of the actor).

In this section, we will see the now state-of-the-art method DDPG (Deep Deterministic Policy Gradient), which tries to combine the advantages of policy gradient methods (actor-critic, continuous or highly dimensional outputs, stability) with those of value-based methods (sample efficiency, off-policy).

### 4.4.1 Deterministic policy gradient theorem

We now assume that we want to learn a parameterized deterministic policy $$\mu_\theta(s)$$. As for the stochastic policy gradient theorem, the goal is to maximize the expectation over all states reachable by the policy of the reward to-go (return) after each action:

$J(\theta) = \mathbb{E}_{s \sim \rho_\mu}[R(s, \mu_\theta(s))]$

As in the stochastic case, the distribution of states reachable by the policy $$\rho_\mu$$ is impossible to estimate, so we will have to perform approximations. Building on Hafner and Riedmiller (2011), Silver et al. (2014) showed how to obtain a usable gradient for the objective function when the policy is deterministic.

Considering that the Q-value of an action is the expectation of the reward to-go after that action $$Q^\pi(s, a) = \mathbb{E}_\pi[R(s, a)]$$, maximizing the returns or maximizing the true Q-value of all actions leads to the same optimal policy. This is the basic idea behind dynamic programming (see Section 2.1.3). where policy evaluation first finds the true Q-value of all state-action pairs and policy improvement changes the policy by selecting the action with the maximal Q-value $$a^*_t = \text{argmax}_a Q_\theta(s_t, a)$$.

In the continuous case, we will simply state that the gradient of the objective function is the same as the gradient of the Q-value. Supposing we have an unbiased estimate $$Q^\mu(s, a)$$ of the value of any action in $$s$$, changing the policy $$\mu_\theta(s)$$ in the direction of $$\nabla_\theta Q^\mu(s, a)$$ leads to an action with a higher Q-value, therefore with a higher associated return:

$\nabla_\theta J(\theta) = \mathbb{E}_{s \sim \rho_\mu}[\nabla_\theta Q^\mu(s, a) |_{a = \mu_\theta(s)}]$

This notation means that the gradient w.r.t $$a$$ of the Q-value is taken at $$a = \mu_\theta(s)$$. We now use the chain rule to expand the gradient of the Q-value:

$\nabla_\theta J(\theta) = \mathbb{E}_{s \sim \rho_\mu}[\nabla_\theta \mu_\theta(s) \times \nabla_a Q^\mu(s, a) |_{a = \mu_\theta(s)}]$

It is perhaps clearer using partial derivatives and simplifying the notations:

$\frac{\partial Q(s,a)}{\partial \theta} = \frac{\partial Q(s,a)}{\partial a} \times \frac{\partial a}{\partial \theta}$

The first term defines of the Q-value of an action changes when one varies slightly the action (if I move my joint a bit more to the right, do I get a higher Q-value, hence more reward?), the second term defines how the action changes when the parameters $$\theta$$ of the actor change (which weights should be changed in order to produce that action with a slightly higher Q-value?).

We already see an actor-critic architecture emerging from this equation: $$\nabla_\theta \mu_\theta(s)$$ only depends on the parameterized actor, while $$\nabla_a Q^\mu(s, a)$$ is a sort of critic, telling the actor in which direction to change its policy: towards actions associated with more reward.

As in the stochastic policy gradient theorem, the question is now how to obtain an unbiased estimate of the Q-value of any action and compute its gradient. Silver et al. (2014) showed that it is possible to use a function approximator $$Q_\varphi(s, a)$$ as long as it is compatible and minimize the quadratic error with the true Q-values:

$\nabla_\theta J(\theta) = \mathbb{E}_{s \sim \rho_\mu}[\nabla_\theta \mu_\theta(s) \times \nabla_a Q_\varphi(s, a) |_{a = \mu_\theta(s)}]$ $J(\varphi) = \mathbb{E}_{s \sim \rho_\mu}[(Q^\mu(s, \mu_\theta(s)) - Q_\varphi(s, \mu_\theta(s)))^2]$

Fig. 25 outlines the actor-critic architecture of the DPG (deterministic policy gradient) method, to compare with the actor-critic architecture of the stochastic policy gradient (Fig. 21).

Silver et al. (2014) investigated the performance of DPG using linear function approximators and showed that it compared positively to stochastic algorithms in high-dimensional or continuous action spaces. However, non-linear function approximators such as deep NN would not work yet.

### 4.4.2 Deep Deterministic Policy Gradient (DDPG)

Lillicrap et al. (2015) extended the DPG approach to work with non-linear function approximators. In fact, they combined ideas from DQN and DPG to create a very successful algorithm able to solve continuous problems off-policy, the deep deterministic policy gradient (DDPG) algorithm..

The key ideas borrowed from DQN are:

• Using an experience replay memory to store past transitions and learn off-policy.
• Using target networks to stabilize learning.

They modified the update frequency of the target networks originally used in DQN. In DQN, the target networks are updated with the parameters of the trained networks every couple of thousands of steps. The target networks therefore change a lot between two updates, but not very often. Lillicrap et al. (2015) found that it is actually better to make the target networks slowly track the trained networks, by updating their parameters after each update of the trained network using a sliding average for both the actor and the critic:

$\theta' = \tau \, \theta + (1-\tau) \, \theta'$

with $$\tau <<1$$. Using this update rule, the target networks are always “late” with respect to the trained networks, providing more stability to the learning of Q-values.

The key idea borrowed from DPG is the policy gradient for the actor. The critic is learned using regular Q-learning and target networks:

$J(\varphi) = \mathbb{E}_{s \sim \rho_\mu}[(r(s, a, s') + \gamma \, Q_{\varphi'}(s', \mu_{\theta'}(s')) - Q_\varphi(s, a))^2]$

One remaining issue is exploration: as the policy is deterministic, it can very quickly produce always the same actions, missing perhaps more rewarding options. Some environments are naturally noisy, enforcing exploration by itself, but this cannot be assumed in the general case. The solution retained in DDPG is an additive noise added to the deterministic action to explore the environment:

$a_t = \mu_\theta(s_t) + \xi$

This additive noise could be anything, but the most practical choice is to use an Ornstein-Uhlenbeck process (Uhlenbeck and Ornstein, 1930) to generate temporally correlated noise with zero mean. Ornstein-Uhlenbeck processes are used in physics to model the velocity of Brownian particles with friction. It updates a variable $$x_t$$ using a stochastic differential equation (SDE):

$dx_t = \theta (\mu - x_t) dt + \sigma dW_t \qquad \text{with} \qquad dW_t = \mathcal{N}(0, dt)$

$$\mu$$ is the mean of the process (usually 0), $$\theta$$ is the friction (how fast it varies with noise) and $$\sigma$$ controls the amount of noise. Fig. 26 shows three independent runs of a Ornstein-Uhlenbeck process: successive values of the variable $$x_t$$ vary randomly but coherently over time.

The architecture of the DDPG algorithm is depicted on Fig. 27.

The pseudo-algorithm is as follows:

• Initialize actor network $$\mu_{\theta}$$ and critic $$Q_\varphi$$ with random weights.

• Create the target networks $$\mu_{\theta'}$$ and $$Q_{\varphi'}$$.

• Initialize experience replay memory $$\mathcal{D}$$ of maximal size $$N$$.

• for episode $$\in [1, M]$$:

• Initialize random process $$\xi$$.
• Observe the initial state $$s_0$$.
• for $$t \in [0, T_\text{max}]$$:
• Select the action $$a_t = \mu_\theta(s_t) + \xi$$ according to the current policy and the noise.

• Perform the action $$a_t$$ and observe the next state $$s_{t+1}$$ and the reward $$r_{t+1}$$.

• Store $$(s_t, a_t, r_{t+1}, s_{t+1})$$ in the experience replay memory.

• Sample a minibatch of $$N$$ transitions randomly from $$\mathcal{D}$$.

• For each transition $$(s_k, a_k, r_k, s'_k)$$ in the minibatch:

• Compute the target value using target networks $$y_k = r_k + \gamma \, Q_{\varphi'}(s'_k, \mu_{\theta'}(s'_k))$$.
• Update the critic by minimizing: $\mathcal{L}(\varphi) = \frac{1}{N} \sum_k (y_k - Q_\varphi(s_k, a_k))^2$

• Update the actor using the sampled policy gradient: $\nabla_\theta J(\theta) = \frac{1}{N} \sum_k \nabla_\theta \mu_\theta(s_k) \times \nabla_a Q_\varphi(s_k, a) |_{a = \mu_\theta(s_k)}$

• Update the target networks: $\theta' \leftarrow \tau \theta + (1-\tau) \, \theta'$ $\varphi' \leftarrow \tau \varphi + (1-\tau) \, \varphi'$

The question that arises is how to obtain the gradient of the Q-value w.r.t the action $$\nabla_a Q_\varphi(s, a)$$, when the critic only outputs the Q-value $$Q_\varphi(s, a)$$. Fortunately, deep neural networks are simulated using automatic differentiation libraries such as tensorflow, theano, pytorch and co, which can automatically output this gradient. If not available, one could simply use the finite difference method (Euler) to approximate this gradient. One has to evaluate the Q-value in $$a +da$$, where $$da$$ is a very small change of the executed action, and estimate the gradient using:

$\nabla_a Q_\varphi(s, a) \approx \frac{Q_\varphi(s, a + da) - Q_\varphi(s, a)}{da}$

Note that the DDPG algorithm is off-policy: the samples used to train the actor come from the replay buffer, i.e. were generated by an older version of the target policy. DDPG does not rely on importance sampling: as the policy is deterministic (we maximize $$\mathbb{E}_{s}[Q(s, \mu_\theta(s))]$$), there is no need to balance the probabilities of the behavior and target policies (with stochastic policies, one should maximize $$\mathbb{E}_{s}[\sum_{a\in\mathcal{A}} \pi(s, a) Q(s, a)]$$). In other words, the importance sampling weight can safely be set to 1 for deterministic policies.

DDPG has rapidly become the state-of-the-art model-free method for continuous action spaces (although now PPO is preferred). It is able to learn efficent policies on most contiuous problems, either pixel-based or using individual state variables. In the original DDPG paper, they showed that batch normalization (Ioffe and Szegedy, 2015) is crucial in stabilizing the training of deep networks on such problems. Its main limitation is its high sample complexity. Distributed versions of DDPG have been proposed to speed up learning, similarly to the parallel actor learners of A3C (Barth-Maron et al., 2018; Lötzsch et al., 2017; Popov et al., 2017).

3. Multiple Distributed Parallel Actors gather $$(s, a, r, s')$$ transitions in parallel and write them to the same replay buffer.


text:
Now showing items 11-19 of 19

• #### Observability of systems with delay convoluted observation

[OWP-2014-10] (Mathematisches Forschungsinstitut Oberwolfach, 2014-05-13)
This paper analyzes finite dimensional linear time-invariant systems with observation of a delay, where that delay satisfies a particular implicit relation with the state variables, rendering the entire problem nonlinear. ...
• #### On periodic solutions and global dynamics in a periodic differential delay equation

[OWP-2014-08] (Mathematisches Forschungsinstitut Oberwolfach, 2014-05-13)


text:
# E, maybe, may not be

Calculus Level pending

$\large \int_0^{1.5} \frac{\tan(x)}x \, dx$

Which of these answer choices is the best estimate for the value of the integral above?

×


text:
How long will it take cars to overtake?

Tags:
1. Sep 27, 2014

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

A car starts from rest and accelerates uniformly at 3.0 m/s2. A second car starts from rest 6.0 s later at the same
point and accelerates uniformly at 5.0 m/s2. How long does it take the second car to overtake the first car?

2. Relevant equations

3. The attempt at a solution
So let $t$ represent the time since the FIRST car, Car A has taken off.
Let $T$ represent the time since the SECOND car, Car B has taken off.

Note that $T = t - 6$.

$x_A(t) = (3/2)t^2$
$x_B(t) = (5/2)(t-6)^2$

Let x_A(t) = x_B(t) you find,

t = 26.618,

So I say that 26.618 seconds after the first car starts, the second car overtakes it.

The correct answer is 21 seconds.

26.618 - 6 = 20.618 =~ 21.

My point is, they dont explain from which "frame of reference" you should point out your time, then why isnt t = 26.618 correct?

2. Sep 27, 2014

Orodruin

Staff Emeritus
This is again a problem of the problem author making implicit assumptions. If someone asked me how long it would take to overtake A I would think it natural to use the time since the "chase" started, i.e., $T$. A complete answer would include the reference time and be of the form "it would take 21 seconds after car B has started to accelerate".

On a side note, answering with five significant digits is not reasonable as your input data only has two there is no way that you could have this amount of accuracy.

3. Sep 27, 2014

ehild

The question clearly refers to the second car.

ehild

4. Sep 27, 2014

@Orodruin, then how would you find the answer? 20.6 rounded up IS 21 seconds after all . what is the solution, I think this is this closest because it it matching up the position.

5. Sep 28, 2014

bump, the answer T = 20.608 is correct because I think the test-bank rounds it off.

6. Sep 28, 2014

Orodruin

Staff Emeritus
20.608 s is what you get when you simply inserts the numbers. However, it is not reasonable to respond with five significant digits when your input data has two. Most likely you cannot make the prediction to that level of accuracy or measure the time that accurately. Using the same number of significant digits (in this case rounding to two significant digits) gives a good first order approximation of how accurate you can be. You could also answer 20.608 s and give an estimate of the error, which will be significantly larger than 0.01 s, which means that the later digits do not contain any useful information. I would therefore answer along the lines "After the second car has started, it takes about 21 s for it to catch up."

7. Sep 28, 2014


text:
# Why is the local qasm_simulator significantly slower than the statevector_simulator?

I've been running VQE experiments locally using both the statevector_simulator and qasm_simulator, however I've noticed that the runtimes for the qasm_simulator are significantly longer than that of statevector_simulator. According to this answer the statevector_simulator produces ideal/deterministic results, whereas qasm_simulator produces non-ideal/probabilistic results. However I don't see why the simulation times should differ significantly($$>\times 100$$) if the number of shots=1 for the qasm_simulator even if a NoiseModel or measurement_error_mitigation_cls=CompleteMeasFitter is used.

Is this in fact expected and how is it explained?

## 1 Answer

Note that if you use qasm_simulator with shots=1, this doesn't tell you anything! Unless IBM automatically switch your simulator to statevector_simulator if you specify the shots =1 when calling qasm_simulator.

Now in term of add noise model and doing measurement_error_mitigation. To be able to do this, you need to generate $$2^n$$ basis states and measure each of them to create a calibration matrix. It is an expensive procedure since you have many more quantum circuits to execute. Each circuit requires a certain amount of shots, up to 8192 shots. In statevector_simulator, you don't need to do this as there is no noise.


text:
# The function is real, while its integral is complex [duplicate]

Suppose the function

SingleCrossSection[Ss_, s2_, m_, m2_, mp_] =
-(1/(288 π^3 s2^3 Ss^4 (mp^2 - Ss)^2))
((m^2 - s2) (1/((m + m2)^2 - (mp - Sqrt[
Ss])^2) (s2 - (mp - Sqrt[
Ss])^2) Sqrt[-2 mp^2 ((m + m2)^2 + Ss) + ((m + m2)^2 -
Ss)^2 +
mp^4] (m^4 (-6 mp^8 + 3 mp^6 (s2 + 24 Ss) +
mp^4 (3 s2^2 - 27 s2 Ss - 172 Ss^2) +
mp^2 Ss (-30 s2^2 - 19 s2 Ss + 152 Ss^2) +
Ss^2 (35 s2^2 + 35 s2 Ss - 46 Ss^2)) +
m^2 s2 (3 mp^8 - 6 mp^6 (s2 + 12 Ss) +
mp^4 (3 s2^2 + 18 s2 Ss + 110 Ss^2) -
2 mp^2 Ss (15 s2^2 + 17 s2 Ss + 8 Ss^2) +
Ss^2 (11 s2^2 + 38 s2 Ss - 25 Ss^2)) -
s2^2 (-3 mp^8 - 3 mp^6 (s2 - 24 Ss) +
mp^4 (6 s2^2 + 63 s2 Ss - 134 Ss^2) +
mp^2 Ss (-60 s2^2 + 19 s2 Ss + 64 Ss^2) +
Ss^2 (46 s2^2 - 71 s2 Ss + Ss^2))) +
12 Ss^2 (m^4 (2 mp^6 - 3 mp^4 (s2 + 2 Ss) + 6 mp^2 Ss^2 +
s2^3 + 3 s2 Ss^2 - 2 Ss^3) +
m^2 s2 (2 mp^6 + 3 mp^4 (s2 - 2 Ss) -
6 mp^2 (s2^2 + s2 Ss - Ss^2) + s2^3 + 3 s2 Ss^2 -
2 Ss^3) +
s2^2 (-mp^6 + 3 mp^4 (s2 + Ss) - 3 mp^2 Ss^2 - 2 s2^3 +
6 s2^2 Ss - 3 s2 Ss^2 + Ss^3)) Log[-(
s2/(-2 mp^2 + 4 mp Sqrt[Ss] + s2 - 2 Ss))]) -
12 Ss^2 Log[
m2^2/(-m^2 - 2 m m2 +
s2)] (-3 s2^3 (mp^2 - Ss)^2 (m^2 + mp^2 - Ss) Log[-(
s2/(-2 mp^2 + 4 mp Sqrt[Ss] + s2 - 2 Ss))] -
1/((m + m2)^2 - (mp - Sqrt[Ss])^2) (m^2 -
s2) (s2 - (mp - Sqrt[
Ss])^2) Sqrt[-2 mp^2 ((m + m2)^2 + Ss) + ((m + m2)^2 -
Ss)^2 +
mp^4] (m^4 (-2 mp^4 + mp^2 (s2 + 4 Ss) + s2^2 + s2 Ss -
2 Ss^2) +
m^2 s2 (-2 mp^4 + mp^2 (4 Ss - 5 s2) + s2^2 + s2 Ss -
2 Ss^2) +
s2^2 (mp^4 - 2 mp^2 (s2 + Ss) - 2 s2^2 + 4 s2 Ss +
Ss^2))));

defined on

{s2, (m+m2)^2, (Sqrt[Ss]-mp)^2}, Ss > (mp+m2+m)^2, m > 0, m2>0, mp>0

It is real function of its arguments on the domain of the definition.

I'm trying to evaluate its integral over s2:

CrossSectionIntegral[Ss_, s2_, m_, m2_, mp_] =
Simplify[Integrate[SingleCrossSection[Ss, s2, m, m2, mp],
s2, Assumptions -> Ss > 0 && Sqrt[Ss] > mp + m2 + m]];
CrossSection[Ss_, m_, m2_, mp_] =
Collect[CrossSectionIntegral[Ss, (Sqrt[Ss]-mp)^2, m, m2, mp] -
CrossSectionIntegral[Ss, (m+m2)^2, m, m2, mp], m] ;

The huge output for the integration contains, as far I can see, the combinations of polylogarithms with positive arguments larger than 1 and logarithms with negative arguments, and thus seems to be comples. However, because of an identity relating a polylogarithm with the argument larger than one with a polylogarithm with the argument less than one, all the imaginary terms becomes zero. Mathematica seems to know these identities, or at least evaluates the imaginary part to zero.

Now, I'm going to check this graphically for particular values of Ss, mp,m2. I write

Plot[{CrossSection[6.5, m, 0.1, 1]}, {m, 0, Sqrt[6.5] - 1}]

The output is not smooth, there are some discontinuites on the plot (the yellow curve, please ignore the blue curve here and below):

From the other side, if I plot the real part,

Plot[{Re[CrossSection[6.5, m, 0.1, 1]]}, {m, 0, Sqrt[6.5] - 1}]

the graphic is the same, but discontinuites are lost (the yellow curve):

Please ignore any errors during obtaining the output (such as "Infinite expression 1/0 encountered"), since the reason for them is just slightly incorrect upper limit for the plot (it must be smaller).

What can be the reason of such problem? I expect that the integral of the function over the domain where it is real and continuous will be real quantity, so it seems that the problem may be in misinterpretation of the output by Mathematica.

• Does it help if you increase the points used for plotting using PlotPoints ? Have I understood the question; are the discontinuities the problem of the appearance or another curve when you take the real part? – Hugh Aug 7 '17 at 17:13
• @Hugh : sorry, another curve is given from another plot. The only problem worrying me are discontinuities. As for PlotPoints, i'm not sure. Actually the function from my qiestion was obtained by the approximation of another function (whose integral corresponds to the blue curve), and its plot (obtained by numerical integration) is smooth. – John Taylor Aug 7 '17 at 17:16
• Try using PlotPoints-> 500. This will give 500 starting points and this may find all the intervals. – Hugh Aug 7 '17 at 17:19
• @Hugh : But why then the plot of real part is smooth? – John Taylor Aug 7 '17 at 17:24
• Try plotting the imaginary part. Are there small artifacts? This could spoil the algorithm for plotting points. Mathematica leaves a gap if the function is complex. – Hugh Aug 7 '17 at 17:27

If we just plot the function, the real part and the imaginary part around the discontinuity we find the following

  Plot[{CrossSection[6.5, m, 0.1, 1]}, {m, 0.7, 0.82}, PlotRange -> All]
Plot[{Re[CrossSection[6.5, m, 0.1, 1]]}, {m, 0.7, 0.82},
PlotRange -> All]
Plot[{Im[CrossSection[6.5, m, 0.1, 1]]}, {m, 0.7, 0.82},
PlotRange -> All]

So my guess is that the small imaginary part is too big for the plotting algorithm and it does not plot because it sees an imaginary part.

Note that you are hoping for imaginary parts to subtract to zero. This is not quite managed because of numerical precision. As Mr.Wizard mentions using Chop would be an option. It gets rid of small values.

This may be a duplicate but I can't find it. So the work around is to plot the real part or use Chop.

• You can also Chop away the imaginary noise: Plot[Chop @ CrossSection[6.5, m, 0.1, 1], {m, 0.7, 0.82}, PlotRange -> All] – Mr.Wizard Aug 7 '17 at 17:52
• @Mr.Wizard : is this imaginary noise just the artifact of Mathematica? – John Taylor Aug 7 '17 at 18:14
• See my additional comment in the answer you are hoping that imaginary parts will subtract to zero. – Hugh Aug 7 '17 at 18:23


text:
# Math Help - [probability] any help with this challenging problem?? explanations appreciated

2. ## Re: [probability] any help with this challenging problem?? explanations appreciated

In any two by two sub-grid, there are $4^4= 64$ equally likely "configuration". Only one such configuration gives a circle.

3. ## Re: [probability] any help with this challenging problem?? explanations appreciated

i got it, thanks for your help.


text:
## Einstein's reality criterion

Sorry for the delay, this week I want to have a short post continuing to showcase the results of late Asher Peres which unfortunately are not well known and this is a shame.

In the famous EPR paper, Einstein introduced a reality criterion:

"If, without in any way disturbing a system, we can predict with certainty ... the value of a physical quantity, then there exists an element of physical reality corresponding to this physical quantity"

Now it is generally accepted that the difference between classical and quantum mechanics is noncomutativity. While there are some subtle points to be made about this assertion (by the mathematical community), from the physics point of view the distinction is rock solid and we can build in confidence upon it.

Now consider again the  EPR-B experiment with its singlet state. Suppose the x and y components of the spin exists independent of measurement and let's call the measurement values: $$m_{1x}, m_{1y}, m_{2x}, m_{2y}$$. From experimental results we know:

$$m_{1x} = - m_{2x}$$
and
$$m_{1y} = - m_{2y}$$

And now for the singlet state $$\psi$$ let's compute:

$$(\sigma_{1x} \sigma_{2y} + \sigma_{1y} \sigma_{2x})\psi$$

which turns out to be zero. The beauty of this is that $$\sigma_{1x} \sigma_{2y}$$ commutes with $$\sigma_{1y} \sigma_{2x}$$ and by Einstein's reality criterion extended to commuting operators it implies that $$m_{1x} m_{2y} = - m_{1y} m_{2x}$$ which contradicts $$m_{1x} = - m_{2x}$$ and $$m_{1y} = - m_{2y}$$

This contradiction is in the same vein as the GHZ result, but it is not well known. The catch of this result is that measuring S1xS2y cannot be done at the same time with a measurement of  S1yS2x and so we are reasoning counterfactually. However, counterfactual reasoning is allowed in a noncontextual setting (in classical mechanics and in quantum mechanics for commuting operators) and the result is valid.

## von Neumann  and Gleason vs. Bell

Returning to physics topics today I want to talk about an important contention point between von Neuman and Gleason on one had, and Bell on the other. I had a series of posts about Bell in which I discussed his major achievement. However I do not subscribe to his ontic point of view and today I will attempt to explain why and perhaps persuade the reader with what what I consider to be a solid argument.

Before Bell wrote his famous paper he had another one in which he criticized von Neumann, Jauch and Piron, and Gleason. The key of the criticism was that additivity of orthogonal projection operators not necessarily implies the additivity of expectation values:

$$\langle P_u + P_v \rangle = \langle P_{u}\rangle + \langle P_{v}\rangle$$

The actual technical requirements in von Neumann and Gleason case were slightly different, but they can be reduced to the statement above and more importantly this requirement is the nontrivial one in a particular proof of Gleason's theorem

 Andrew Gleason

To Bell, additivity of expectation values is a non-natural requirement because he was able to construct hidden variable models violating this requirement. And this was the basis for his criticism of von Neumann and his theorem of the impossibility of hidden variables. But is this additivity requirement unnatural? What can happen when it is violated? I will show that violation on additivity of expectation values can allow instantaneous communication at a distance.

The experimental setting is simple and involves spin 1 particles. The example which I will present is given in late Asher Peres book: Quantum Theory: Concepts and Methods at page 191. (This book is one of my main sources of inspiration for how we should understand and interpret quantum mechanics. )

The mathematical identity we need is:

$$J_{z}^{2} = {(J_{x}^{2} - J_{y}^{2})}^2$$

and the experiment is as follows: a beam of spin 1 particles is sent through a beam splitter which sends to the left particles of eigenvalue zero for $$J_{z}^{2}$$ and to the right particles of eigenvalue one for $$J_{z}^{2}$$.

Now a lab on the right decides to measure either if $$J_z = 1$$ or if $$J_{x}^{2} - J_{y}^{2} = 1$$

For the laboratory on the right let's call the projectors in the first case $$P_u$$ and $$P_v$$ and in the second case $$P_x$$ and $$P_y$$

For the lab on the left let's call the projectors in the first case $$P_{w1}$$ and in the second case$$P_{w2}$$.

Because of the mathematical identity: $$P_u + P_v = P_x +P_y$$ the issues becomes: should the expectation value requirement hold as well?

$$\langle P_{u}\rangle + \langle P_{v}\rangle = \langle P_{x}\rangle + \langle P_{y}\rangle$$

For the punch line we have the following identities:

$$\langle P_{w1}\rangle = 1 - \langle P_{u}\rangle - \langle P_{v}\rangle$$
and
$$\langle P_{w2}\rangle = 1 - \langle P_{x}\rangle - \langle P_{y}\rangle$$

and as such if the additivity requirement is violated we have:

$$\langle P_{w1}\rangle \neq \langle P_{w2}\rangle$$

Therefore regardless of the actual spatial separation, the lab on the left can figure out which experiment the lab on the right decided to perform!!!

With this experimental setup, if additivity of expectation values is false, you can even violate causality!!!

Back to Bell: just because von Neumann and Gleason did not provide a justification for their requirements, this does not invalidate their arguments. The justification was found at a later time.

But what about the Bohmian interpretation of quantum mechanics? Although there are superluminal speeds in the theory, superluminal signaling is not possible in it. This is because Bohmian interpretation respects Born rule which is a consequence of Gleason't theorem and it respects the additivity of  expectation values as well. Bohmian interpretation suffers from other issues however.

## A US Presidential Election Analysis

Once in a while, important events deserve to be discussed and they dislodge physics topics. I wrote in the past about Donald Trump, and today I want to revisit the topic and present some analysis on what is currently going on in US election politics. By now the election outcome is all but certain: Trump will lose, and Clinton will win, but what is the basis for this prediction?

If you never heard of it, there is an amazing site by Nate Silverhttp://projects.fivethirtyeight.com/2016-election-forecast/

Nate Silver has a huge well deserved prediction credibility and he performs in-depth analysis of the elections way more than what you find on the usual media outlets like CNN.

In the image below you see the daily graph of the winning chances for Trump (the red line) and Clinton (the blue line).

Mid July Trump got a post Republican convention boost and he was on the rise until Clinton had the democratic convention.The sharp Trump decline after that convention was due to his attack on the Khan family, whose son died for America. When that scandal faded, mid August, Trump's odds began improving following Clinton's erosion of trust due to the email server scandal, and also due to concerns about her health. Then came the first debate in which Trump had a very good first half an hour but was ill prepared for the long haul of the debate. That started a turn-off reaction for the independent voters who only now got the first serious look at him.

Still the slide was temporary and the fluctuations were comparable with the prior two weeks and for two days he was climbing back in the polls. At this point the famous tape of him bragging about grabbing women by their genitals surfaced and this started a a chain reaction mostly inside the Republican party. The tape reversed the trend, but what killed his election chances was his performance in the second debate. Trump made two strategic mistakes:

• he attacked Hillary (and Bill Clinton) instead of sincerely apologizing
• he dismissed the tape as locker room talk and claimed he did not do anything physical
Let's see what those were fatal mistakes for him. By going on the offensive when people expected genuine contrition made Trump appear as a rabid dog and people were hugely disgusted by his behavior. The general consensus of the independent people who watched the second debate was that they themselves felt dirty and in need of a shower. The second debate reduced Trump's changes into low teen numbers. If you look at the two prior cycles: June-August and August-October you notice the bouncing back rate for Trump and that there is not enough time for him to close the gap before election day.

Now even if the election is postponed a few months, Trump will never recover due to his second strategic mistake. For all his playboy behavior, it is impossible that he never did anything real as he was bragging on the tape. But by claiming it was all "only talk" as opposed to Bill Clinton's actions encouraged women to come forward to tell their stories. Once this started it cannot be stopped. Just ask Bill Cosby on how it happened in his case: the same pattern will repeat here.

When the tape was released, republicans running for reelection started deserting Trump out of fear that he will negatively affect their changes of reelection due to the backlash in the women's vote. But by now is is clear Trump's chances of election are virtually zero and this has the potential to split the Republican party.

After the election loss, the finger-pointing will begin. Rience Priebus has no real vision or power and will most likely lose his job. The power vacuum will start a chaotic period for the Republican party which will end either by a victory of anti-Trump forces, or a party split. My bet is that the party will remain intact since politicians tend to act as a pack: there is strength in numbers and it is hard to survive alone.

## Local Causality in a Friedmann-Robertson-Walker Spacetime

A few days ago I learned about a controversy regarding Joy Christian's paper:
Local Causality in a Friedmann-Robertson-Walker Spacetime which got published in Annals of Physics and was recently withdrawn: http://retractionwatch.com/2016/09/30/physicist-threatens-legal-action-after-journal-mysteriously-removed-study/

The paper repeats the same mathematically incorrect arguments of Joy Christian against Bell's theorem and has nothing to do with Friedmann-Robertson-Walker spacetime. The FRW space was only used as a trick to get the wrong referees which are not experts on Bell theorem. In particular the argument is the same as in this incorrect Joy's one-pager preprint

The mistake happens in two steps:
• a unification of two algebras into the same equation
• a subtle transition from a variable to an index in a computation mixing apples with oranges
I will run the explanation in parallel between the one-pager and the withdrawn paper because it is easier to see the mistake in the one-pager.

Step 1: One-pager Eq. 3 is the same as FRW paper Eq. 49:

$$\beta_j \beta_k = -\delta_{jk} - \epsilon_{jkl} \beta_l$$
$$L(a, \lambda) L(b, \lambda) = - a\cdot b - L(a\times b, \lambda)$$

In the FRW paper $$L(a, \lambda) = \lambda I\cdot a$$ while in the 1-pager: $$\beta_j (\lambda) = \lambda \beta_j$$ where $$\lambda$$ is a choice of orientation. This make look as an innocuous unification but in fact it describes two distinct algebras with distinct representations.

This means that Eqs. 3/49 describe two multiplication rules (and let's call them A for apples and O for oranges). Unpacked, the multiplication rules are:

$$A_i A_j = -\delta_{jk} + \epsilon_{jkl} A_l$$
$$O_i O_j = -\delta_{jk} - \epsilon_{jkl} O_l$$

The matrix representations are:

$$A_1 = \left( \begin{array}{cc} i & 0 \\ 0 & -i \end{array}\right) = i\sigma_3$$
$$A_2 = \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array}\right) = -i \sigma_2$$
$$A_3 = \left( \begin{array}{cc} 0 & -i \\ -i & 0 \end{array}\right)= -i \sigma_1$$

and $$O_i = - A_i = {A_i}^{\dagger}$$

Try multiplying the above matrices to convince yourself that they are indeed a valid representation of the multiplication rule.

There is even a ket and bra or column and row vector representation of the two distinct algebras, but I won't go into details since it requires a math detour which will takes the focus away from Joy's mistake.

Step 2: summing apples with oranges (or column vectors with row vectors)

The summation is done in steps 5-7 and 67-75. The problem is that the sum from 1 to n contains two kinds of objects apples and oranges and should be in fact broken up in two sums. If this needs to be combined into a single sum then we need to convert apples and oranges to orientation independent objects. Since $$L(a, \lambda) = \lambda I\cdot a$$ and  $$\beta_j (\lambda) = \lambda \beta_j$$ with $$I \cdot a$$ and $$\beta_j$$ orientation independent objects, when we convert the two kinds of objects to a single unified kind there is an additional missing factor of lambda.

Since $$O_j=\beta_j (\lambda^k) = \lambda^k \beta_j$$ with $$\lambda^k = +1$$ and $$A_j=-\beta_j (\lambda^k) = \lambda^k \beta_j$$ with $$\lambda^k = -1$$ where $$\lambda^k$$ is the orientation of the k-th pair of particles, in the transition from 6 to 7 and 72 to 73  in an unified sum we are missing a $$\lambda^k$$  factor.

Again, either break up the sum into apples and oranges (where the index k tells you which kinds of objects you are dealing with) or unify the sum and adjust it by converting it into orientation-free objects and this is done by multiplication by $$\lambda^k$$. If we separate the sums, they will not cancel each other out because there is -1 a conversion factor from apples to oranges  $$O = - A$$, and if we unify the sum as Joy does in Eq. 74 the sum is not of $$\lambda^k$$ but of $${(\lambda^k)}^2$$ which does not vanish.

As it happens Joy's research program is plagued by this -1 (or missing lambda) mistake in his attempt to vanquish a cross product term. But even if his proposal were mathematically valid it would not represent a genuine challenge to Bell's theorem. Inspired by Joy's program, James Weatherall found a mathematically valid example very similar with Joy's proposal but one which does not use quaternions/Clifford algebras.

The lesson of Weatherall is that correlations must be computed using actual experimental results and the computation (like the one Joy is doing at steps 67-75) must not be made in a hypothetical space of "beables".

Now back to the paper withdrawal, the journal did not acted properly: it should have notified Joy before taking action. However Joy did not act in good faith by masquerading the title to sneak it past imperfect peer review and his attempt at victimization in the comments section has no merit. In the end the paper is mathematically incorrect, has nothing to do with FRW spacetime, and (as proven by Weatherall) Joy's program is fatally flawed and cannot get off the ground even if there were no mathematical mistakes in it.

## The whole is greater than the sum of its parts

The tile of today's post is a quote from Aristotle, but I want to illustrate this in the quantum formalism. Here I will refer to a famous Hardy paper: Quantum Theory From Five Reasonable Axioms. In there one finds the following definitions:

• The number of degrees of freedom, K, is defined as the minimum number of probability measurements needed to determine the state, or, more roughly, as the number of real parameters required to specify the state.
• The dimension, N, is defined as the maximum number of states that can be reliably distinguished from one another in a single shot measurement.
Quantum mechanics obeys $$K=N^2$$ while classical physics obeys $$K=N$$.

Now suppose nature is realistic and the electron spin does exist independent of measurement. From Stern-Gerlach experiments we know what happens when we pass a beam of electrons through two such devices rotates by an angle $$\alpha$$: suppose we pick only the spin up electrons, on the second device the electrons are still deflected up $$\cos^2 (\alpha /2)$$ percent of time and are deflected down $$\sin^2 (\alpha /2)$$ percent of time . This is an experimental fact.

Now suppose we have a source of electron pairs prepared in a singlet state. This means that the total spin of the system is zero. There is no reason to distinguish a particular direction in the universe and with the assumption of the existence of the spin independent of measurement we can very naturally assume that our singlet state electron source produces an isotropic distribution of particles with opposite spins. Now we ask: in an EPR-B experiment, what kind of correlation would Alice and Bob get under the above assumptions?

We can go about finding the answer to this in three ways. First we can cheat and look the answer up in a 1957 paper by Bohm and Aharonov who first made the computation, This paper (and the answer) is cited by Bell in his famous "On the Einstein-Podolsky-Rosen paradox". But we can do better than that. We can play with the simulation software from last time. Here is what you need to do:

-replace the generating functions with:

function GenerateAliceOutputFromSharedRandomness(direction, sharedRandomness3DVector) {
var cosAngle= Dot(direction, sharedRandomness3DVector);
var cosHalfAngleSquared = (1+cosAngle)/2;
if (Math.random() < cosHalfAngleSquared )
return +1;
else
return -1;
};

function GenerateBobOutputFromSharedRandomness(direction, sharedRandomness3DVector) {
var cosAngle= Dot(direction, sharedRandomness3DVector);
var cosHalfAngleSquared = (1+cosAngle)/2;
if (Math.random() < cosHalfAngleSquared )
return -1;
else
return +1;
};

-replace the -cosine curve drawing with  a -0.3333333 cosine curve:

boardCorrelations.create('functiongraph', [function(t){ return -0.3333333*Math.cos(t); }, -Math.PI*10, Math.PI*10],{strokeColor:  "#66ff66", strokeWidth:2,highlightStrokeColor: "#66ff66", highlightStrokeWidth:2});

replace the fit test for the cosine curve with one for with 0.3333333 cosine curve:

var diffCosine = epsilon + 0.3333333*Math.cos(angle);

and the result of the program (for 1000 directions and 1000 experiments) is:

So how does the program work? The sharedRandomness3DVector is the direction on which the spins are randomly generated. The dot product compute the cosine of the angle between the measurement direction and the spin, and from it we can compute the cosine of the half angle. The square of the cosine of the half angle is used to determine the random outcome. The resulting curve is 1/3 of the experimental correlation curve. Notice that the output generation for Alice and Bob are completely independent (locality).

But the actual analytical computation is not that hard to do either. We proceed in two steps.

Step 1: Let $$\beta$$ be the angle between one spin $$x$$ and a measurement device direction $$a$$. We have: $$\cos (\beta) = a\cdot x$$ and:

$${(\cos \frac{\beta}{2})}^2 = \frac{1+\cos\beta}{2} = \frac{1+a\cdot x}{2}$$

Keeping the direction $$x$$ constant, the measurement outcomes for Alice and Bob measuring on the directions $$a$$ and $$b$$ respectively are:

++ $$\frac{1+a\cdot x}{2} \frac{1+b\cdot (-x)}{2}$$ percent of the time
-- $$\frac{1-a\cdot x}{2} \frac{1-b\cdot (-x)}{2}$$ percent of the time
+-$$\frac{1+a\cdot x}{2} \frac{1-b\cdot (-x)}{2}$$ percent of the time
-+$$\frac{1-a\cdot x}{2} \frac{1+b\cdot (-x)}{2}$$ percent of the time

which yields the correlation: $$-(a\cdot x) (b \cdot x)$$

Step 2: integrate $$-(a\cdot x) (b \cdot x)$$ for all directions $$x$$. To this aim align $$a$$ on the z axis and have $$b$$ in the y-z plane:

$$a=(0,0,a)$$
$$b=(0, b_y , b_z)$$

then go to spherical coordinates integrating using:

$$\frac{1}{4\pi}\int_{0}^{2\pi} d\theta \int_{0}^{\pi} \sin\phi d\phi$$

$$a\cdot x = \cos\phi$$
$$b\cdot x = b(0, \sin\alpha, -\cos\alpha)\cdot(\sin\phi \cos\theta, \sin\phi\sin\theta, \cos\phi)$$

where $$\alpha$$ is the angle between $$a$$ and $$b$$.

Plugging all back in and doing the trivial integration yields: $$-\frac{\cos\alpha}{3}$$

So now for the moral of the story. the quantum mechanics prediction and the experimentally observed  correlation is  $$-\cos\alpha$$ and not $$-\frac{1}{3} \cos\alpha$$

The 1/3 incorrect correlation factor comes from demanding (1) the experimentally proven behavior from two consecutive S-G device measurements, (2) the hypothesis that the electron spins exist before measurement, and (3) and isotropic distribution of spins originating from a total spin zero state.

(1) and (3) cannot be discarded because (1) is an experimental behavior, and (3) is a very natural demand of isotropy. It is (2) which is the faulty assumption.

If (2) is true then circling back on Hardy's result, we are under the classical physics condition: $$K=N$$ which means that the whole is the sum of the parts.

Bell considered both the 1/3 result and the one from his inequality and decided to showcase his inequality for experimental purposes reasons: "It is probably less easy, experimentally, to distinguish (10) from (3), then (11) from (3).". Both hidden variable models:

if (Dot(direction, sharedRandomness3DVector) < 0)
return +1;
else
return -1;

and

var cosAngle= Dot(direction, sharedRandomness3DVector);
var cosHalfAngleSquared = (1+cosAngle)/2;
if (Math.random() < cosHalfAngleSquared )
return -1;
else
return +1;

are at odds with quantum mechanics and experimental results. The difference between them is on the correlation behavior for 0 and 180 degrees. If we allow information transfer between Alice generating function and Bob generating function (nonlocality) then it is easy to generate whatever correlation curve we want under both scenarios (play with the computer model to see how it can be done).

So from realism point of view, which hidden variable model is better? Should we insist on perfect anti-correlations at 0 degrees, or should we demand the two consecutive S-G results along with realism? It does not matter since both are wrong. In the end local realism is dead.


text:
# Mathematical Statistics and Data Analysis

It took me quite some time to decide on an introductory statistics book to read. Unlike calculus or linear algebra, it appears that there is not a general consensus on book(s) for an intermediate level introduction to the subject. Casella and Berger comes close but it is generally regarded as graduate level text. Based on an amazon review and a few Quora answers, I have decided to go with - Mathematical Statistics and Data Analysis by John A. Rice, third edition.

Recently, well not so recently, I completed watching lectures - Introduction to Probability by Prof. Blitzstein and also went through the corresponding book from the same author. Lectures and the problems were great and enriching . These are one of the best lectures that I have went through till now. And an accompanying book with the same flow of contents as in the lectures is as good as it can get. Thanks to Prof. Blitzstein and everyone involved in putting these lectures online. I will write a detailed review on it some time later.

I would suggest problems in the handouts are the minimum number of problems that one should do to convince oneself that he/she got a decent understanding of the content. The problems were carefully chosen and really help in deepening of the concepts. Though I have practiced with these problems in the handouts and they did helped a lot but still felt that I have not practiced enough.

One nice thing about Probability and Statistics, that Prof. Blitzstein also mentioned, is it builds up on the foundations laid out by the earlier topics and it is quite difficult to follow the advanced topics without having a decent hold of the basics.

Thus while going through Mathematical Statistics and Data Analysis, I am hoping to solve atleast 40-50% of the problems given in the book and put these solutions online. Well, the book contains 60 to 70 problems in each chapter, it would take too long to solve all of them :). I will try to solve all the problems whose answers are given in the book as it can help in ensuring some level of correctness.

As with every other post in the blog - there is no guarantee of the correctness - Please let me know if there are any mistakes - I will fix them as soon as I can.

Note: I will start from chapter 7 as I have already covered the earlier content in Probability lectures

$$\tag*{\blacksquare}$$


text:
# In Lambda calculus, Is there some alternative equivalence to $\eta$ conversion?

In Lambda calculus, is there some alternative equivalence to $$\eta$$ conversion?

I am reading Hendrik Pieter Barendregt's Introduction to Lambda Calculus. On Page 11, I saw $$\beta$$-reduction, $$\alpha$$-conversion, and $$ξ$$-rules (compatibility rules) which is:

Equality:

$$M = M;$$ $$M = N ⇒ N = M;$$ $$M = N, N = L ⇒ M = L.$$

Compatibility rules:

$$M = M' ⇒ MZ = M' Z;$$ $$M = M' ⇒ ZM = ZM' ;$$ $$M = M' ⇒ λx.M = λx.M' . (ξ)$$

But I do not find $$\eta$$-conversion in the book. Does the book mention $$\eta$$ conversion, possibly under a different name or indirectly via an alternative equivalence? Are $$ξ$$ rules by any chance an alternative equivalence to $$\eta$$ conversion?

No, those notes do not talk about $$\eta$$-conversion or $$\eta$$-reduction at all, not even under a different name.

$$\eta$$-conversion is the least equivalence relation on $$\lambda$$-terms that is closed under compatible rules and contains the following relation ($$\textrm{fv}(M)$$ stands for the set of the free variables of the $$\lambda$$-term $$M$$): \begin{align}\tag{1} \lambda x.M x &=_\eta M & \text{if } x \notin \textrm{fv}(M). \end{align}

$$\eta$$-conversion cannot be derived by the conversion rules presented in those notes. For instance, \begin{align} \lambda x. yx =_\eta y \end{align} but there is no hope to derive that using the conversion rules of those notes.

The main reason why $$\eta$$-conversion is important is that, when joined with $$\beta$$-conversion, it captures the notion of extensionality, which roughly means that $$\beta\eta$$-conversion equates all the $$\lambda$$-terms that ''represent'' the same funciton. Formally, it can be proved that $$M =_{\beta\eta} N$$ if and only if $$MP =_{\beta\eta} NP$$ for every $$\lambda$$-term $$P$$. Said differently (very roughly), up to $$\beta\eta$$-conversion, two $$\lambda$$-terms that always have the same output on the same inputs are equal (it does not matter how they compute that output).

Since the $$\lambda$$-calculus is interesting especially for studying intensional (as opposed to extensional) properties of computation, the lack of $$\eta$$-conversion in those notes is not so harmful.

A good reference for $$\eta$$-conversion (and many other topics about the $$\lambda$$-calculus) is Branedregt's book "The Lambda Calulus: Its Syntax and Semantics", North Holland, 1984.

From what I see, $$\eta$$-reduction is not introduced in the book at all.

The equality and compatibility rules you cited are merely natural consequences of the way $$\beta$$-reduction is defined; these axioms can all be justified on the base of the semantics of the $$\twoheadrightarrow_\beta$$ operation. $$\eta$$-conversion, on the other hand, is an operation on its own, which can not be derived from $$\alpha$$-conversion and $$\beta$$-conversion alone.

The operation of $$\eta$$-reduction is defined as follows:

$$P[\lambda x. M x] \to_\eta P[M]$$, $$\quad$$ if $$x \not \in \mathrm{FV}(M)$$.

Here, $$\to_\eta$$ is reduction in one step. In analogy to the relations $$\twoheadrightarrow_\beta$$ and $$=_\beta$$ defined on p. 23 in your book, the relation $$\twoheadrightarrow_{\beta \eta}$$ is then the transitive closure of the $$\to_\beta$$ and $$\to_\eta$$ operations, that is, $$M \twoheadrightarrow_{\beta \eta} N$$ iff there is a reduction series from $$M$$ to $$N$$ where each step is a $$\to_\alpha$$, $$\to_\beta$$ or $$\to_\eta$$ reduction; and $$=_{\beta \eta}$$, $$\beta\eta$$-convertibility, is the extension of the $$=_\beta$$ relation to include $$\to_\eta$$ and $$\leftarrow_\eta$$ reduction steps.

Intuitively, $$\beta \eta$$-convertibility expresses extensionality, that is, for two $$\lambda$$ terms to be the same, it suffices if they have the same behavior in application to other terms.

"Normal" $$\lambda$$ calculus is intensional, that is, two terms are not necessarily considered equal just because they have the same reduction behavior. The addition of $$\eta$$-conversion provides an extension to the calculus, that is, establishing further equivalences between $$\lambda$$ terms that can not be established on the basis of $$\beta$$-reduction alone, in a way that makes the theory of $$\lambda$$-calculus extensional.
Whether or not you want to include $$\eta$$-conversion in your system depends on which variant of equality you favor. Thinking in terms of ZF set theory and functions as a special kind of relation -- that is, a function seen as a set of tuples representing the course of values of the function, and two sets seen as equivalent if they have all the same elements -- the idea of extensionality (two functions are considered the same if they behave the same on any given input/if the input-output tuples in the set descibing the relation expressed by the function are all the same) might seem natural. However, from a computational/programming perspective, you might not want to consider any two programs the same just because they produce the same output, since they might implement two conceptually different algorithms. In pure $$\lambda$$-calculus without $$\eta$$, two programs which have the same behavior but a different "implementation" would not be considered equivalent.


text:
# Tag Info

2

As a disclaimer, I didn't read that page, but I can certainly explain where the derivatives come from. The backpropagation algorithm is actually a variant of the gradient descent algorithm. Think about a single function for the moment. Suppose you have a function which responds to a single input and a single weight: $f(w, x)$. We want to adjust $w$ so that ...

1

I have wondered something similar and failed to find much in the way of satisfying answers in the literature. Here is what I tentatively came up with. It seems perhaps what we need is some kind of regularization. If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the ...

0

I don't think that paper is suitable for what you want to do. That paper generates an embedding of nodes: given a graph $G$ and a node $v$ in $G$, it outputs an embedding of $v$ (a representation of some properties of $v$). You want an embedding of the entire graph: given a graph $G$, you want to compute an embedding of $G$ (a representation of the entire ...

0

This is called top-3 accuracy. See https://stats.stackexchange.com/q/95391/2921, https://stackoverflow.com/q/37668902/781723, https://stats.stackexchange.com/q/156471/2921. Sure, you can use it. Whether top-1 accuracy or top-3 accuracy is better correlated with user satisfaction will depend on your particular application and on your users.

2

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right). Machine learning ...

0

You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.

Top 50 recent answers are included


text:
track.split.3d {eRTG3D} R Documentation

## This function splits the by outliers in the time lag.

### Description

The length of timeLag must be the the track's length minus 1 and represents the time passed between the fix point acquisition

### Usage

track.split.3d(track, timeLag, lag = NULL, tolerance = NULL)

### Arguments

 track track data.frame with x, y and z coordinates timeLag a numeric vector with the time passed between the fix point acquisition lag NULL or a manually chosen lag tolerance NULL or a manually chosen tolerance

### Value

A list containing the splitted tracks.

### Examples

track.split.3d(
niclas,
timeLag = rep(1, nrow(niclas) - 1) + rnorm(nrow(niclas) - 1,
mean = 0,
sd = 0.25)
)

[Package eRTG3D version 0.7.0 Index]


text:
## Calculus 8th Edition

$\lim\limits_{x \to 5}\frac{x^2-5x+6}{x-5}=\frac{(5)^2-5(5)+6}{(5)-5}=\frac{0}{0}=$indet so we have to do algebra $\lim\limits_{x \to 5}\frac{x^2-5x+6}{x-5}=\lim\limits_{x \to 5}\frac{(x-3)(x-2)}{(x-5)}$ We can't simplify or do anything further so the limit does not exist.


text:
EDGEDIR - Editorial

#1

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

MEDIUM

PREREQUISITES:

Spanning trees, dp on trees

PROBLEM:

You have undirected connected graph with N vertices and M edges. You have to direct edges of the graph in such a way that indegree of each vertex is even. (1 \leq N, M \leq 10^5)

QUICK EXPLANATION:

Direct edges in arbitrary way. Now you may choose any path in initial graph and inverse all edges on this path. In such way you will change indegrees only of first and last vertices on the path, thus you may group vertices of odd indegrees in pairs and get rid of them.

EXPLANATION:

Assume that edges of the graph are already directed in some way. What will happen if we inverse edge u o v? Parities of indegrees of both u and v will inverse as well, because u will have one more edge among edges directed to it and v will lose one such edge. This is the simplest case of edge inversion and any other one may be simply reduced to it. Note that parity of vertices having odd indegree will never change when inverting one edge, this gives us simple criteria of when solution exists: Solution exists \iff amount of vertices having odd indegree is even.

Now what to do if solution exists? Consider path v_1 o v_2 o \dots o v_{k-1} o v_k. What will happen if we invert all edges in such path? Answer is that parity of indegrees of v_1 and v_k will be inversed and parity of v_2, \dots, v_{k-1} won’t change. Thus if amount of vertices having odd indegrees is even, you may make them in pairs in arbitrary way and one by one inverse all edges in pathes between vertices in each pair. And now you have pretty vast space on implementation of this.

First of all you should note that you may always choose path from some spanning tree (e.g. dfs tree). This would reduce problem to “invert edges on the path in tree several times, output final state of each edge”. And now you may either honestly group vertices in pairs and do such queries with some data structure or you may see that inverting path between u and v is the same as firstly inverting path from u to w and then from v to w where w is arbitrary vertex in the tree. This provides you with easiest solution if you simply choose w to be the root of the tree. Then no matter how you split vertices in pairs, you will simply need to invert all edges in set of pathes w o v_1, w o v_2, \dots, w o v_k where v_1, \dots, v_k is the set of vertices having odd indegree and w is the root of the tree. You may process such queries in offline with simple dp counting number of vertices with odd indegree in each’s vertex subtree.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.


text:
## Calculus (3rd Edition)

Since the slope of the tangent line of the curve $y=2x+8$ at an arbitrary point will be constant, that is $m=2$, then the tangent line will be the curve itself.


text:
You are currently browsing the tag archive for the ‘bayesian’ tag.

A Bayesian agent is observing a sequence of outcomes in ${\{S,F\}}$. The agent does not know the outcomes in advance, so he forms some belief ${\mu}$ over sequences of outcomes. Suppose that the agent believes that the number ${d}$ of successes in ${k}$ consecutive outcomes is distributed uniformly in ${\{0,1,\dots k\}}$ and that all configuration with ${d}$ successes are equally likely:

$\displaystyle \mu\left(a_0,a_1,\dots,a_{k-1} \right)=\frac{1}{(k+1)\cdot {\binom{k}{d}}}$

for every ${a_0,a_1,\dots,a_{k-1}\in \{S,F\}}$ where ${d=\#\{0\le i.

You have seen this belief ${\mu}$ already though maybe not in this form. It is a belief of an agent who tosses an i.i.d. coin and has some uncertainty over the parameter of the coin, given by a uniform distribution over ${[0,1]}$.

In this post I am gonna make a fuss about the fact that as time goes by the agent learns the parameter of the coin. The word learning’ has several legitimate formalizations and today I am talking about the oldest and probably the most important one — consistency of posterior beliefs. My focus is somewhat different from that of textbooks because 1) As in the first paragraph, my starting point is the belief ${\mu}$ about outcome sequences, before there are any parameters and 2) I emphasize some aspects of consistency which are unsatisfactory in the sense that they don’t really capture our intuition about learning. Of course this is all part of the grand marketing campaign for my paper with Nabil, which uses a different notion of learning, so this discussion of consistency is a bit of a sidetrack. But I have already came across some VIP who i suspect was unaware of the distinction between different formulations of learning, and it wasn’t easy to treat his cocky blabbering in a respectful way. So it’s better to start with the basics.

Let ${A}$ be a finite set of outcomes. Let ${\mu\in\Delta(A^\mathbb{N})}$ be a belief over the set ${A^\mathbb{N}}$ of infinite sequences of outcomes, also called realizations. A decomposition of ${\mu}$ is given by a set ${\Theta}$ of parameters, a belief ${\lambda}$ over ${\Theta}$, and, for every ${\theta\in\Theta}$ a belief ${\mu_\theta}$ over ${A^\mathbb{N}}$ such that ${\mu=\int \mu_\theta~\lambda(\mathrm{d}\theta)}$. The integral in the definition means that the agent can think about the process as a two stages randomization: First a parameter ${\theta}$ is drawn according to ${\lambda}$ and then a realization ${\omega}$ is drawn according to ${\mu_\theta}$. Thus, a decomposition captures a certain way in which a Bayesian agent arranges his belief. Of course every belief ${\mu}$ admits many decompositions. The extreme decompositions are:

• The Trivial Decomposition. Take ${\Theta=\{\bar\theta\}}$ and ${\mu_{\bar\theta}=\mu}$.
• Dirac’s Decomposition. Take ${\Theta=A^\mathbb{N}}$ and ${\lambda=\mu}$. A “parameter” in this case is a measure ${\delta_\omega}$ that assigns probability 1 to the realization ${\omega}$.

Not all decompositions are equally exciting. We are looking for decompositions in which the parameter ${\theta}$ captures some fundamental property’ of the process. The two extreme cases mentioned above are usually unsatisfactory in this sense. In Dirac’s decomposition, there are as many parameters as there are realizations; parameters simply copy realizations. In the trivial decomposition, there is a single parameter and thus cannot discriminate between different interesting properties. For stationary process, there is a natural decomposition in which the parameters distinguish between fundamental properties of the process. This is the ergodic decomposition, according to which the parameters are the ergodic beliefs. Recall that in this decomposition, a parameter captures the empirical distribution of blocks of outcomes in the infinite realization.

So what about learning ? While observing a process, a Bayesian agent will update his belief about the parameter. We denote by ${\lambda_n\left(a_0,\dots,a_{n-1}\right)\in\Delta(\Theta)}$ the posterior belief about the parameter ${\theta}$ at the beginning of period ${n}$ after observing the outcome sequence ${a_0,\dots,a_{n-1}}$. The notion of learning I want to talk about in this post is that this belief converges to a belief that is concentrated on the true parameter ${\theta}$. The example you should have in mind is the coin toss example I started with: while observing the outcomes of the coin the agent becomes more and more certain about the true parameter of the coin, which means his posterior belief becomes concentrated around a belief that gives probability ${1}$ to the true parameter.

Definition 1 A decomposition of ${\mu}$ is consistent if for ${\lambda}$-almost every ${\theta}$ it holds that

$\displaystyle \lambda_n\left(a_0,\dots,a_{n-1}\right)\xrightarrow[n\rightarrow\infty]{w}\delta_\theta$

for ${\mu_\theta}$-almost every realization ${\omega=(a_0,a_1,\dots)}$.

In this definition, ${\delta_\theta}$ is Dirac atomic measure on ${\theta}$ and the convergence is weak convergence of probability measures. No big deal if you don’t know what it means since it is exactly what you expect.

So, we have a notion of learning, and a seminal theorem of L.J. Doob (more on that below) implies that the ergodic decomposition of every stationary process is consistent. While this is not something that you will read in most textbooks (more on that below too), it is still well known. Why do Nabil and I dig further into the issue of learnability of the ergodic decomposition ? Two reasons. First, one has to write papers. Second, there is something unsatisfactory about the concept of consistency as a formalization of learning. To see why, consider the belief ${\mu}$ that outcomes are i.i.d. with probability ${1/2}$ for success. This belief is ergodic, so from the perspective of the ergodic decomposition the agent knows the process’ and there is nothing else to learn. But let’s look at Dirac’s decomposition instead of the ergodic decomposition. Then the parameter space equals the space of all realizations. Suppose the true parameter (=realization) is ${\omega^\ast=(a_0,a_1,\dots)}$, then after observing the first ${n}$ outcomes of the process the agent’s posterior belief about the parameter is concentrated on all ${\omega}$ that agrees with ${\omega^\ast}$ on the first ${n}$ coordinates. These posterior beliefs converge to ${\delta_{\omega^\ast}}$, so that Dirac decomposition is also consistent ! We may say that we learn the parameter, but “learning the parameter” in this environment is just recording the past. The agent does not gain any new insight about the future of the process from learning the parameter.

In my next post I will talk about other notions of learning, originating in a seminal paper of Blackwell and Dubins, which capture the idea that an agent who learns a parameter can make predictions as if he new the parameter. Let me also say here that this post and the following ones are much influenced by a paper of Jackson, Kalai, Smorodinsky. I will talk more on that paper in another post.

For the rest of this post I am going to make some comments about Bayesian consistency which, though again standard, I don’t usually see them in textbooks. Especially I don’t know of a reference for the version of Doob’s Theorem which I give below, so if any reader can give me such a reference it will be helpful.

First, you may wonder whether every decomposition is consistent. The answer is no. For a trivial example, take a situation where ${\mu_\theta}$ are the same for every ${\theta}$. More generally troubles arrise when the realization does not pin down the parameter. Formally, let us say that function ${f:\Omega\rightarrow \Theta}$ pins down or identifies the parameter if

$\displaystyle \mu_\theta\left(\{\omega: f(\omega)=\theta\}\right)=1$

for ${\lambda}$-almost every ${\theta}$. If such ${f}$ exists then the decomposition is identifiable.

We have the following

Theorem 2 (Doob’s Theorem) A decomposition is identifiable if and only if it is consistent.

The if’ part follows immediately from the definitions. The only if’ part is deep, but not difficult: it follows immediately from the martingale convergence theorem. Indeed, Doob’s Theorem is usually cited as the first application of martingales theory.

Statisticians rarely work with this abstract formulation of decomposition which I use. For this reason, the theorem is usually formulated only for the case that ${\Theta=\Delta(A)}$ and ${\mu_\theta}$ is i.i.d. ${\theta}$. In this case the fact that the decomposition is identifiable follows from the strong law of large numbers. Doob’s Theorem then implies the standard consistency of Bayesian estimator of the parameter ${\theta}$.

The abstract of a 2005 paper by Itti and Baldi begins with these words:

The concept of surprise is central to sensory processing, adaptation, learning, and attention. Yet, no widely-accepted mathematical theory currently exists to quantitatively characterize surprise elicited by a stimulus or event, for observers that range from single neurons to complex natural or engineered systems. We describe a formal Bayesian definition of surprise that is the only consistent formulation under minimal axiomatic assumptions.

They propose that surprise be measured by the Kullback-Liebler divergence between the prior and the posterior. As with many good ideas, Itti and Baldi are not the first to propose this. C. L. Martin and G. Meeden did so in 1984 in an unpublished paper entitled: The distance between the prior and the posterior distributions as a measure of surprise.’ Itti and Baldi go further and provide experimental support that this notion of surprise comports with human notions of surprise. Recently, Ely, Frankel and Kamenica in Economics, have also considered the issue of surprise, focusing instead on how best to release information so as to maximize interest.

Surprise now being defined, one might go on to define novelty, interestingness, beauty and humor. Indeed, Jurgen Schmidhuber has done just that (and more). A paper on the optimal design of jokes cannot be far behind. Odd as this may seem, it is a part of a venerable tradition. Kant defined humor as the sudden transformation of a strained expectation into nothing. Birkhoff himself wrote an entire treatise on Aesthetic Measure (see the review by Garabedian). But, I digress.

Returning to the subject of surprise, the Kulback-Liebler divergence is not the first measure of surprise or even the most wide spread. I think that prize goes to the venerable $p$-value. Orthodox Bayesians, those who tremble in the sight of measure zero events, look in horror upon the $p$-value because it does not require one to articulate a model of the alternative. Even they would own, I think, to the convenience of having to avoid listing all alternative models and carefully evaluating them. Indeed I. J. Good  writing in 1981 notes the following:

The evolutionary value of surprise is that it causes us to check our assumptions. Hence if an experiment gives rise to a surprising result given some null hypothesis $H$ it might cause us to wonder whether $H$ is true even in the absence of a vague alternative to $H$.

Good, by the way, described himself as a cross between Bayesian and Frequentist, called a Doogian. One can tell from this label that he had an irrepressible sense of humor. Born Isadore Guldak Joseph of a Polish family in London, he changed his name to Ian Jack Good, close enough one supposes. At Bletchley park he and Turing came up with the scheme that eventually broke the German Navy’s enigma code. This led to the Good-Turing estimator. Imagine a sequence so symbols chosen from a finite alphabet. How would one estimate the probability of observing a letter from the alphabet that has not yet appeared in the sequence thus far? But, I digress.

Warren Weaver was, I think, the first to propose a measure of surpirse. Weaver is most well known as a popularizer of Science. Some may recall him as the Weaver on the slim volume by Shannon and Weaver on the Mathematical Theory of Communication. Well before that, Weaver played an important role at the Rockefeller foundation, where he used their resources to provide fellowships to many promising scholars and jump start molecular biology. The following is from page 238 of my edition Jonas’ book `The Circuit Riders’:

Given the unreliability of such sources, the conscientious philanthropoid has no choice but to become a circuit rider. To do it right, a circuit rider must be more than a scientifically literate ‘tape recorder on legs.’ In order to win the confidence of their informants, circuit riders for Weaver’s Division of Natural Sciences were called upon the offer a high level of ‘intellectual companionship – without becoming ‘too chummy’ with people whose work they had, ultimately, to judge.

But, I digress.

To define Weaver’s notion, suppose a discrete random variable $X$ that takes values in the set $\{1, 2, \ldots, m\}$. Let $p_i$ be the probability that $X = i$. The surprise index of outcome $k$ is $\frac{\sum_i i p^2_i}{p_k}$. Good himself jumped into the fray with some generalizations of Weaver’s index. Here is one $\frac{[\sum_iip_i^t]^{1/t}}{p_k}$. Others involve the use of logs, leading to measures that are related to notions of entropy as well probability scoring rules. Good also proposed axioms that a good measure to satisfy, but I cannot recall if anyone followed up to derive axiomatic characterizations.

G. L. S. Shackle, who would count as one of the earliest decision theorists, also got into the act. Shackle departed from subjective probability and proposed to order degrees of beliefs by their potential degrees of surprise. Shackle also proposed, I think, that an action be judged interesting by its best possible payoff and its potential for surprise. Shackle, has already passed beyond the ken of men. One can get a sense of his style and vigor from the following response to an invitation to write a piece on Rational Expectations:

Rational expectations’ remains for me a sort of monster living in a cave. I have never ventured into the cave to see what he is like, but I am always uneasily aware that he may come out and eat me. If you will allow me to stir the cauldron of mixed metaphors with a real flourish, I shall suggest that ‘rational expectations’ is neo-classical theory clutching at the last straw. Observable circumstances offer us suggestions as to what may be the sequel of this act or that one. How can we know what invisible circumstances may take effect in time-to come, of which no hint can now be gained? I take it that ‘rational expectations’ assumes that we can work out what will happen as a consequence of this or that course of action. I should rather say that at most we can hope to set bounds to what can happen, at best and at worst, within a stated length of time from ‘the present’, and can invent an endless diversity of possibilities lying between them. I fear that for your purpose I am a broken reed.


text:
SG++
Modules

To insure extendability and maintainability, SG++ is divided into a number of modules that implement different functionality.

Different modules can be compiled independently from each other.

The modules can depend on each other. Especially all depend on the base module. Libraries are generated for all modules. The following modules are available:

The modules correspond to the C++ namespaces. Roughly speaking, all files from one namespace belong to the respective module. But a module can contain files belonging to some another namespace, i.e. static factory methods in the namespace sgpp::op_factory.

# Folder structure

Please note that the modularization results in a somewhat unconventional folder structure. Keeping

/path/to/SGpp/module/

as "modular" as possible requires to have everything belonging to a module below that directory. This especially applies to the src folder. Its subdirectories reflect the namespaces. Therefore, the module name reappears once again:

/path/to/SGpp/module/src/sgpp/module/...


text:
Report

Conversion of Zinc Oxide Nanobelts into Superlattice-Structured Nanohelices

+ See all authors and affiliations

Science  09 Sep 2005:
Vol. 309, Issue 5741, pp. 1700-1704
DOI: 10.1126/science.1116495

Abstract

A previously unknown rigid helical structure of zinc oxide consisting of a superlattice-structured nanobelt was formed spontaneously in a vapor-solid growth process. Starting from a single-crystal stiff nanoribbon dominated by the c-plane polar surfaces, an abrupt structural transformation into the superlattice-structured nanobelt led to the formation of a uniform nanohelix due to a rigid lattice rotation or twisting. The nanohelix was made of two types of alternating and periodically distributed long crystal stripes, which were oriented with their c axes perpendicular to each other. The nanohelix terminated by transforming into a single-crystal nanobelt dominated by nonpolar ($Math$) surfaces. The nanohelix could be manipulated, and its elastic properties were measured, which suggests possible uses in electromechanically coupled sensors, transducers, and resonators.

View Full Text