<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://en.formulasearchengine.com/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=128.179.159.66</id>
	<title>formulasearchengine - User contributions [en]</title>
	<link rel="self" type="application/atom+xml" href="https://en.formulasearchengine.com/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=128.179.159.66"/>
	<link rel="alternate" type="text/html" href="https://en.formulasearchengine.com/wiki/Special:Contributions/128.179.159.66"/>
	<updated>2026-08-07T20:49:15Z</updated>
	<subtitle>User contributions</subtitle>
	<generator>MediaWiki 1.47.0-wmf.7</generator>
	<entry>
		<id>https://en.formulasearchengine.com/w/index.php?title=Pairing_heap&amp;diff=12102</id>
		<title>Pairing heap</title>
		<link rel="alternate" type="text/html" href="https://en.formulasearchengine.com/w/index.php?title=Pairing_heap&amp;diff=12102"/>
		<updated>2014-01-14T15:50:36Z</updated>

		<summary type="html">&lt;p&gt;128.179.159.66: &lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;&#039;&#039;&#039;Difference in differences&#039;&#039;&#039; (sometimes &#039;Difference-in-Differences&#039;,&amp;lt;ref&amp;gt;{{cite book |last=Angrist |first=J. D. |last2=Pischke |first2=J. S. |year=2008 |title=Mostly harmless econometrics: An empiricist&#039;s companion |publisher=Princeton University Press |location= |isbn=9780691120348 }}&amp;lt;/ref&amp;gt; &#039;DID&#039;,&amp;lt;ref&amp;gt;{{cite journal |last=Abadie |first=A. |year=2005 |title=Semiparametric difference-in-differences estimators |journal=[[Review of Economic Studies]] |volume=72 |issue=1 |pages=1–19 |doi=10.1111/0034-6527.00321 }}&amp;lt;/ref&amp;gt; or &#039;DD&#039;&amp;lt;ref name=Bertrand /&amp;gt;) is a technique used in [[econometrics]] that measures the effect of a treatment at a given period in time. It is often used to measure the change induced by a particular treatment or event, though it may be subject to certain biases ([[Regression toward the mean|mean reversion]] bias, etc.). In contrast to a [[Fixed effects model|within-subjects estimate]] of the treatment effect (that measures the difference in an outcome after and before treatment) or a between-subjects estimate of the treatment effect (that measures the difference in an outcome between the treatment and control groups), the DID estimator represents the difference between the pre-post, within-subjects differences of the treatment and control groups.&lt;br /&gt;
&lt;br /&gt;
==Formal Definition==&lt;br /&gt;
&lt;br /&gt;
Consider the model&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;y_{ist} ~=~ \gamma_s + \lambda_t + \delta D_{st} + \epsilon_{ist}&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
where &amp;lt;math&amp;gt;y_{ist}&amp;lt;/math&amp;gt; is the dependent variable for [[Sampling (statistics)|individual]] &amp;lt;math&amp;gt;i&amp;lt;/math&amp;gt;, given &amp;lt;math&amp;gt;s&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;t&amp;lt;/math&amp;gt;. The dimensions &amp;lt;math&amp;gt;s&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;t&amp;lt;/math&amp;gt; may for example be [[State (polity)|state]] and time. &amp;lt;math&amp;gt;\gamma_s&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;\lambda_t&amp;lt;/math&amp;gt; is then the vertical intercept for &amp;lt;math&amp;gt;s&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;t&amp;lt;/math&amp;gt; respectively. &amp;lt;math&amp;gt;D_{st}&amp;lt;/math&amp;gt; is a [[Dummy variable (statistics)|dummy variable]] indicating [[Treatment and control groups|treatment]] status, &amp;lt;math&amp;gt;\delta&amp;lt;/math&amp;gt; is the treatment effect, and &amp;lt;math&amp;gt;\epsilon_{ist}&amp;lt;/math&amp;gt; is an [[Errors and residuals in statistics|error term]].&lt;br /&gt;
&lt;br /&gt;
Let&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\overline{y}_{st} ~=~ \frac{1}{n} \sum_{i=1}^{n} y_{ist}&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\overline{\gamma}_s ~=~ \frac{1}{n}\sum_{i=1}^{n}\gamma_s ~=~ \gamma_s&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\overline{\lambda}_t ~=~ \frac{1}{n}\sum_{i=1}^{n}\lambda_t ~=~ \lambda_t&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\overline{D}_{st} ~=~ \frac{1}{n}\sum_{i=1}^{n} D_{st} ~=~ D_{st}&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\overline{\epsilon}_{st} ~=~ \frac{1}{n}\sum_{i=1}^{n}\epsilon_{ist}&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
and suppose for simplicity that &amp;lt;math&amp;gt;s=1,2&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;t=1,2&amp;lt;/math&amp;gt;. Then&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;(\overline{y}_{11} - \overline{y}_{12}) - (\overline{y}_{21} - \overline{y}_{22}) &amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;= \left [ (\gamma_1 + \lambda_1 + \delta D_{11} + \overline{\epsilon}_{11}) - (\gamma_1 + \lambda_2 + \delta D_{12} + \overline{\epsilon}_{12}) \right ] - \left [ (\gamma_2 + \lambda_1 + \delta D_{21} + \overline{\epsilon}_{21}) - (\gamma_2 - \lambda_2 + \delta D_{22} + \overline{\epsilon}_{22}) \right ] &amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;= \delta (D_{11} - D_{12}) + \delta(D_{22} - D_{21}) + \overline{\epsilon}_{11} - \overline{\epsilon}_{12} + \overline{\epsilon}_{22} - \overline{\epsilon}_{21}&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
The [[Ordinary least squares#Assumptions|strict exogeneity assumption]] then implies that&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;E \left [ (\overline{y}_{11} - \overline{y}_{12}) - (\overline{y}_{21} - \overline{y}_{22}) \right ] ~=~ \delta (D_{11} - D_{12}) + \delta(D_{22} - D_{21})&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Without loss of generality, assume that &amp;lt;math&amp;gt;D_{22}=1&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;D_{11}=D_{12}=D_{21}=0&amp;lt;/math&amp;gt;, giving the DID estimator&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\delta} ~=~ (\overline{y}_{11} - \overline{y}_{12}) - (\overline{y}_{21} - \overline{y}_{22})&amp;lt;/math&amp;gt;,&lt;br /&gt;
&lt;br /&gt;
which can be interpreted as the treatment effect of the treatment indicated by &amp;lt;math&amp;gt;D_{st}&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
==Assumptions==&lt;br /&gt;
&lt;br /&gt;
[[File:Parallel Trend Assumption.png|right|thumb|320px| Illustration of the parallel trend assumption]]&lt;br /&gt;
&lt;br /&gt;
All the assumptions of the [[Ordinary least squares#Assumptions|OLS model]] apply equally to DID. In addition, DID requires a &#039;&#039;&#039;parallel trend assumption&#039;&#039;&#039;. The parallel trend assumption says that &amp;lt;math&amp;gt;\lambda_2 - \lambda_1&amp;lt;/math&amp;gt; are the same in both &amp;lt;math&amp;gt;s=1&amp;lt;/math&amp;gt; and &amp;lt;math&amp;gt;s=2&amp;lt;/math&amp;gt;. Given that the [[Difference in differences#Formal Definition|formal definition]] above accurately represents reality, this assumption automatically holds. However, a model with &amp;lt;math&amp;gt;\lambda_{st} ~:~ \lambda_{22} - \lambda_{21} \neq \lambda_{12} - \lambda_{11}&amp;lt;/math&amp;gt; may well be more realistic.&lt;br /&gt;
&lt;br /&gt;
As illustrated to the right, the treatment effect is the difference between the observed value of &#039;&#039;y&#039;&#039; and what the value of &#039;&#039;y&#039;&#039; would have been with parallel trends, had there been no treatment. The [[Achilles&#039; heel]] of DID is when something other than the treatment changes in one group but not the other at the same time as the treatment, implying a violation of the parallel trend assumption.&lt;br /&gt;
&lt;br /&gt;
To guarantee the accuracy of the DID estimate, the composition of individuals of the two groups is assumed to remain unchanged over time. When using a DID model, various issues that may compromise the results, such as [[autocorrelation]] and [[Ashenfelter dip]]s, must be considered and dealt with.&lt;br /&gt;
&lt;br /&gt;
==Implementation==&lt;br /&gt;
&lt;br /&gt;
The DID method can be implemented according to the table below, where the lower right cell is the DID estimator.&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|-&lt;br /&gt;
! &amp;lt;math&amp;gt;y_{st}&amp;lt;/math&amp;gt; !! &amp;lt;math&amp;gt;s=2&amp;lt;/math&amp;gt; !! &amp;lt;math&amp;gt;s=1&amp;lt;/math&amp;gt; !! Difference&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;&amp;lt;math&amp;gt;t=2&amp;lt;/math&amp;gt;&#039;&#039;&#039; || &amp;lt;math&amp;gt;y_{22}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;y_{12}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;y_{12}-y_{22}&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;&amp;lt;math&amp;gt;t=1&amp;lt;/math&amp;gt;&#039;&#039;&#039; || &amp;lt;math&amp;gt;y_{21}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;y_{11}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;y_{11}-y_{21}&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;Change&#039;&#039;&#039; || &amp;lt;math&amp;gt;y_{21}-y_{22}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;y_{11}-y_{12}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;(y_{11}-y_{21})-(y_{12}-y_{22})&amp;lt;/math&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
Running a regression analysis gives the same result. Consider the OLS model&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;y ~=~ \beta_0 + \beta_1 T + \beta_2 S + \beta_3 (T \cdot S) + \varepsilon&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
where &amp;lt;math&amp;gt;T&amp;lt;/math&amp;gt; is a dummy variable for &amp;lt;math&amp;gt;t=2&amp;lt;/math&amp;gt;, and &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; is a dummy variable for &amp;lt;math&amp;gt;s=2&amp;lt;/math&amp;gt;. The composite variable &amp;lt;math&amp;gt;(T \cdot S)&amp;lt;/math&amp;gt; is then a dummy variable indicating when &amp;lt;math&amp;gt;S=T=1&amp;lt;/math&amp;gt;. Although it is not shown rigorously here, it turns out that the estimates in this model are&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\beta}_0 ~=~ (y ~|~ T=0,~ S=0)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\beta}_1 ~=~ (y ~|~ T=1,~ S=0) - (y ~|~ T=0,~ S=0)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\beta}_2 ~=~ (y ~|~ T=0,~ S=1) - (y ~|~ T=0,~ S=0)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\beta}_3 ~=~ [(y ~|~ T=1,~ S=1) - (y ~|~ T=0,~ S=1)] - [(y ~|~ T=1,~ S=0) - (y ~|~ T=0,~ S=0)]&amp;lt;/math&amp;gt;, &lt;br /&gt;
&lt;br /&gt;
which is equivalent to&lt;br /&gt;
&lt;br /&gt;
&amp;lt;math&amp;gt;\hat{\beta}_3 ~=~ (y_{11} - y_{21}) - (y_{12} - y_{22})&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
But this is the expression for the treatment effect that was given in the [[Difference in differences#Formal Definition|formal definition]] and in the above table.&lt;br /&gt;
&lt;br /&gt;
==Card &amp;amp; Krueger (1994) example==&lt;br /&gt;
&lt;br /&gt;
Consider one of the most famous DID studies, the [[David Card|Card]] and [[Alan Krueger|Krueger]] article on [[minimum wage]] in [[New Jersey]], published in 1994.&amp;lt;ref&amp;gt;{{cite journal |first=David |last=Card |first2=Alan B. |last2=Krueger |year=1994 |title=Minimum Wages and Employment: A Case Study of the Fast-Food Industry in New Jersey and Pennsylvania |journal=[[American Economic Review]] |volume=84 |issue=4 |pages=772–793 |doi= |jstor=2118030 }}&amp;lt;/ref&amp;gt; Card and Krueger compared [[Unemployment|employment]] in the [[fast food]] sector in New Jersey and in [[Pennsylvania]], in February 1992 and in November 1992, after New Jersey&#039;s minimum wage rose from $4.25 to $5.05 in April 1992. Observing a change in employment in New Jersey only, before and after the treatment, would fail to control for [[Omitted-variable bias|omitted variables]] such as weather and macroeconomic conditions of the region. By including Pennsylvania as a control in a difference-in-differences model, any bias caused by variables common to New Jersey and Pennsylvania are implicitly controlled for, even when these variables are unobserved. Assuming that New Jersey and Pennsylvania have parallel trends over time, Pennsylvania&#039;s change in employment can be interpreted as the change New Jersey would have experienced, had they not increased the minimum wage, and vice versa. The evidence suggested that the increased minimum wage did not induce an increase in unemployment in New Jersey, as standard economic theory would suggest. The table below shows Card &amp;amp; Krueger&#039;s estimates of the treatment effect on employment, measured as [[Full-time equivalent|FTEs (or Full-time equivalents)]]. Keeping in mind that the finding is [[Minimum wage#Card and Krueger|controversial]], Card and Krueger estimate that the $0.80 minimum wage increase in New Jersey lead to a 2.76 FTE increase in employment.&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|-&lt;br /&gt;
!  !! New Jersey !! Pennsylvania !! Difference&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;February&#039;&#039;&#039; || 20.44 || 23.33 || -2.89&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;November&#039;&#039;&#039; || 21.03 || 21.17 || -0.14&lt;br /&gt;
|-&lt;br /&gt;
| &#039;&#039;&#039;Change&#039;&#039;&#039; || 0.59 || -2.16 || 2.76&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
==Critics==&lt;br /&gt;
&lt;br /&gt;
In 2004, the question &amp;quot;How Much Should We Trust Differences-in-Differences Estimates?&amp;quot; was asked in an article with the same name,&amp;lt;ref name=Bertrand/&amp;gt; and apparently the answer is &amp;quot;not all that much.&amp;quot; It is worth noting however that this is only the case if DiD is employed without considering the auto-correlation in calculating the standard errors. Most papers that employ Difference-in-Differences estimation use many years of data and focus on [[Autocorrelation#Regression analysis|serially correlated]] outcomes but ignore that the resulting [[Standard error (statistics)|standard errors]] are inconsistent, leading to serious over-estimation of t-statistics and [[Statistical significance|significance levels]].&amp;lt;ref name=Bertrand&amp;gt;{{cite journal |last=Bertrand |first=M. |last2=Duflo |first2=E. |authorlink2=Esther Duflo |last3=Mullainathan |first3=S. |year=2004 |title=How Much Should We Trust Differences-in-Differences Estimates? |journal=[[Quarterly Journal of Economics]] |volume=119 |issue=1 |pages=249–275 |doi=10.1162/003355304772839588 |jstor= }}&amp;lt;/ref&amp;gt; &#039;&#039;These conventional DID standard errors severely understate the standard deviation of the estimators: we find an &amp;quot;effect&amp;quot; significant at the 5 percent level for up to 45 percent of the placebo interventions.&#039;&#039;&amp;lt;ref name=Bertrand/&amp;gt; To alleviate this problem &#039;&#039;two corrections based on asymptotic approximation of the variance-covariance matrix work well for moderate numbers of states and one correction that collapses the time series information into a &amp;quot;pre&amp;quot; and &amp;quot;post&amp;quot; period and explicitly takes into account the effective sample size works well even for small numbers of states.&#039;&#039;&amp;lt;ref name=Bertrand/&amp;gt;&lt;br /&gt;
&lt;br /&gt;
==See also==&lt;br /&gt;
* [[Design of experiments]]&lt;br /&gt;
* [[Average treatment effect]]&lt;br /&gt;
&lt;br /&gt;
==References==&lt;br /&gt;
{{reflist}}&lt;br /&gt;
&lt;br /&gt;
==Further reading==&lt;br /&gt;
*{{cite journal |last=Imbens |first=Guido W. |first2=Jeffrey M. |last2=Wooldridge |year=2009 |title=Recent Developments in the Econometrics of Program Evaluation |journal=[[Journal of Economic Literature]] |volume=47 |issue=1 |pages=5–86 |doi=10.1257/jel.47.1.5 }}&lt;br /&gt;
&lt;br /&gt;
==External links==&lt;br /&gt;
* [http://www.nber.org/papers/w14237 How Does Charitable Giving Respond to Incentives and Income? Dynamic Panel Estimates Accounting for Predictable Changes in Taxation, [[National Bureau of Economic Research]], July 2005]&lt;br /&gt;
* [http://www.nber.org/papers/t0312 T. Conley and C. Taber, &amp;quot;Inference with &amp;quot;Difference in Differences&amp;quot; with a Small Number of Policy Changes&amp;quot;, National Bureau of Economic Research, July 2005]&lt;br /&gt;
* [http://healthcare-economist.com/2006/02/11/difference-in-difference-estimation/ Difference in Difference Estimation], Healthcare Economist website&lt;br /&gt;
&lt;br /&gt;
{{DEFAULTSORT:Difference In Differences}}&lt;br /&gt;
[[Category:Econometrics]]&lt;br /&gt;
[[Category:Regression analysis]]&lt;br /&gt;
[[Category:Design of experiments]]&lt;br /&gt;
[[Category:Observational study]]&lt;br /&gt;
[[Category:Causal inference]]&lt;/div&gt;</summary>
		<author><name>128.179.159.66</name></author>
	</entry>
</feed>