MD MPH Kim Bouillon
email: kim.bouillon.09@ucl.ac.uk

PhD Archana Singh-Manoux

PhD Markus Jokela

Martin J Shipley

David G Batty

PhD Eric J Brunner

PhD Séverine Sabia

MD Adam G Tabák

PhD Tasnime N Akbaraly

PhD Jane E Ferrie

PhD G David Batty

PhD Mika Kivimäki

Decline in low-density lipoprotein cholesterol concentration: lipid-lowering drugs, diet, or physical activity? Evidence from

Keywords: cohort study, LDL-cholesterol, lipid lowering drug, diet, physical activity

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Blood cholesterol, low density lipoprotein (LDL) cholesterol in particular, is a major risk factor for coronary heart disease (CHD) [START_REF]Executive Summary of The Third Report of The National Cholesterol Education Program (NCEP) Expert Panel on Detection, Evaluation, And Treatment of High Blood Cholesterol In Adults (Adult Treatment Panel III)[END_REF]. Large randomized controlled trials and meta-analyses [START_REF] Hebert | Cholesterol lowering with statin drugs, risk of stroke, and total mortality. An overview of randomized trials[END_REF][START_REF]MRC/BHF Heart Protection Study of cholesterol lowering with simvastatin in 20,536 highrisk individuals: a randomised placebo-controlled trial[END_REF][START_REF] Baigent | Efficacy and safety of cholesterol-lowering treatment: prospective meta-analysis of data from 90,056 participants in 14 randomised trials of statins[END_REF] have established the clinical benefits of lowering LDL-cholesterol. A decrease of one millimole per litre (mmol/L) in LDL-cholesterol concentrations has been shown to be associated with 23% lower risk of myocardial infarction or coronary death [START_REF] Baigent | Efficacy and safety of cholesterol-lowering treatment: prospective meta-analysis of data from 90,056 participants in 14 randomised trials of statins[END_REF]. Similarly, a 1% reduction in total cholesterol was associated with 2% reduction in risk of CHD [START_REF] Probstfield | The Lipid Research Clinics Coronary Primary Prevention Trial: design, results, and implications[END_REF].

There is now consistent evidence for a secular decline in total cholesterol and LDLcholesterol levels among adults in industrialized countries [START_REF] Kuulasmaa | Estimation of contribution of changes in classic risk factors to trends in coronary-event rates across the WHO MONICA Project populations[END_REF][START_REF] Kotseva | Cardiovascular prevention guidelines in daily practice: a comparison of EUROASPIRE I, II, and III surveys in eight European countries[END_REF][START_REF] Unal | Modelling the decline in coronary heart disease deaths in England and Wales, 1981-2000: comparing contributions from primary prevention and secondary prevention[END_REF][START_REF] Berg | Trends in blood lipid levels, blood pressure, alcohol and smoking habits from 1985 to 2002: results from INTERGENE and GOT-MONICA[END_REF][START_REF] Ferrieres | Trends in plasma lipids, lipoproteins and dyslipidaemias in French adults, 1996-2007[END_REF][START_REF] Serra-Majem | Trends in blood lipids and fat soluble vitamins in Catalonia, Spain (1992-2003)[END_REF][START_REF] Grau | Trends in cardiovascular risk factor prevalence (1995-2000-2005) in northeastern Spain[END_REF][START_REF] Li | Utilization of lipid lowering medications among adults in the United States 1999-2006[END_REF][START_REF] Carroll | Trends in serum lipids and lipoproteins of adults, 1960-2002[END_REF][START_REF] Arnett | Twentyyear trends in serum cholesterol, hypercholesterolemia, and cholesterol medication use: the Minnesota Heart Survey, 1980-1982 to 2000-2002[END_REF][START_REF] Kuklina | Trends in high levels of low-density lipoprotein cholesterol in the United States, 1999-2006[END_REF][START_REF] Neutel | Statin use in Canadians: trends, determinants and persistence[END_REF][START_REF] Hobbs | Plasma cholesterol levels continue to decline despite the rising prevalence of obesity: population trends in Perth, Western Australia, 1980-1999[END_REF][START_REF] Metcalf | Factors associated with changes in serum total cholesterol levels over 7 years in middle-aged New Zealand men and women: a prospective study[END_REF]. For example, the MONICA study showed total cholesterol in adults aged 35 to 64 years to have declined between the mid-1980s and mid-1990s in approximately half of the European populations included in the study [START_REF] Kuulasmaa | Estimation of contribution of changes in classic risk factors to trends in coronary-event rates across the WHO MONICA Project populations[END_REF]. Similar findings have been reported in other European populations [START_REF] Unal | Modelling the decline in coronary heart disease deaths in England and Wales, 1981-2000: comparing contributions from primary prevention and secondary prevention[END_REF][START_REF] Berg | Trends in blood lipid levels, blood pressure, alcohol and smoking habits from 1985 to 2002: results from INTERGENE and GOT-MONICA[END_REF][START_REF] Ferrieres | Trends in plasma lipids, lipoproteins and dyslipidaemias in French adults, 1996-2007[END_REF][START_REF] Serra-Majem | Trends in blood lipids and fat soluble vitamins in Catalonia, Spain (1992-2003)[END_REF][START_REF] Grau | Trends in cardiovascular risk factor prevalence (1995-2000-2005) in northeastern Spain[END_REF], the United States [START_REF] Li | Utilization of lipid lowering medications among adults in the United States 1999-2006[END_REF][START_REF] Carroll | Trends in serum lipids and lipoproteins of adults, 1960-2002[END_REF][START_REF] Arnett | Twentyyear trends in serum cholesterol, hypercholesterolemia, and cholesterol medication use: the Minnesota Heart Survey, 1980-1982 to 2000-2002[END_REF][START_REF] Kuklina | Trends in high levels of low-density lipoprotein cholesterol in the United States, 1999-2006[END_REF], Canada [START_REF] Neutel | Statin use in Canadians: trends, determinants and persistence[END_REF], Australia [START_REF] Hobbs | Plasma cholesterol levels continue to decline despite the rising prevalence of obesity: population trends in Perth, Western Australia, 1980-1999[END_REF], and New Zealand [START_REF] Metcalf | Factors associated with changes in serum total cholesterol levels over 7 years in middle-aged New Zealand men and women: a prospective study[END_REF].

Clinical guidelines recommend a multifaceted approach to lowering LDL-cholesterol [START_REF]Executive Summary of The Third Report of The National Cholesterol Education Program (NCEP) Expert Panel on Detection, Evaluation, And Treatment of High Blood Cholesterol In Adults (Adult Treatment Panel III)[END_REF][START_REF] Graham | European guidelines on cardiovascular disease prevention in clinical practice: full text. Fourth Joint Task Force of the European Society of Cardiology and other societies on cardiovascular disease prevention in clinical practice (constituted by representatives of nine societies and by invited experts)[END_REF]. Besides medication, this consists of reducing the intake of saturated fats and cholesterol, reducing weight, and increasing physical activity in order to reach optimal levels of LDLcholesterol. However, the extent to which a healthy diet, physical activity and lipid lowering drugs independently explain the decline in LDL-cholesterol levels currently being observed at the population level is unknown. We therefore examined associations of lipid-lowering drug use and 11-year change in diet and physical activity with declining LDL-cholesterol trends in an occupational cohort of middle-aged British civil servants participating in the Whitehall II study.

inserm-00588857, version 1 -26 Apr 2011

SUBJECTS AND METHODS

Study sample

The Whitehall II study is a prospective cohort study of 10,308 (67% men) London-based British civil servants aged 35-55 years in 1985 [START_REF] Marmot | Cohort Profile: the Whitehall II study[END_REF]. The baseline examination (phase 1) took place during 1985-1988 and involved a clinical examination and self-administered questionnaire.

Subsequent phases of data collection have alternated between postal questionnaire alone (phases 2 (1988-1990), 4 (1995-1996), 6 (2001), and 8 (2006)), and postal questionnaire accompanied by a medical screening (phases 3 (1991-1993), 5 (1997-1999), and 7 (2002-2004)). Detailed lipid data were not available at phase 1 so the data used in the current analysis were drawn from phases 3 to 7, making phase 3 the baseline for the present study. Mean followup between phases 3 and 7 was 11.3 years (standard deviation, SD=0.5). Participants not included in the analysis were those who did not undertake the medical screening at phases 3 or 7, and those with missing data on any of the predictors (lipid lowering drugs, diet, and physical activity) or potential confounders (ethnicity, body mass index, level of education, smoking status, and presence of longstanding illness) either at phase 3 or phase 7 (Figure 1). A total of 4,469 participants were eligible and constituted the study sample. Ethical approval for the Whitehall II study was obtained from the University College London Medical School Committee on the ethics of human research (London, UK).

Biochemical analyses inserm-00588857, version 1 -26 Apr 2011

Blood samples were collected at phases 3 and 7, following either an 8-hour overnight fast (participants presenting to the clinic in the morning) or at least a 4-hour fast after a light fat-free breakfast (participants presenting in the afternoon). Venepuncture of the left antecubital vein was performed with tourniquet. Blood was collected into plain and fluoride Sarstedt (Neumbrecht, Germany) monovettes. Serum for lipid analyses was refrigerated at -4°C and assayed within 72 hours [START_REF] Brunner | Social inequality in coronary risk: central obesity and the metabolic syndrome. Evidence from the Whitehall II study[END_REF]. Total cholesterol was determined by an enzymatic procedure using the CHOD-PAP method at phases 3 and 7. Serum HDL-cholesterol concentrations were measured from the supernatant after precipitation of non-HDL-cholesterol with dextran sulphate-magnesium at phase 3 and with a direct homogeneous assay at phase 7 ( 23), using at both phases the CHOD-PAP method. Serum triglyceride was determined by enzymatic colorimetric method (GPO-PAP) at both phases. The concentration of LDL-cholesterol was calculated using the Friedewald formula when serum triglycerides were lower than 4.5 mmol/L [START_REF] Friedewald | Estimation of the concentration of low-density lipoprotein cholesterol in plasma, without use of the preparative ultracentrifuge[END_REF]. Technical error was estimated by assaying blinded duplicate samples for 5% of subjects. Coefficients of variation were 2.0% to 6.6%. After both screenings, participants were sent a letter which informed them of their results and summarised whether or not they were "at increased risk of heart disease or angina". For example, when a total cholesterol level of 8.5 mmol/L or higher was recorded at baseline (n=185), the letter suggested the participant see his or her GP for a repeat test. The same envelope contained a similar unsealed letter addressed to the participant's GP.

Potential predictors

Lipid lowering drugs

At phases 3 and 7, participants were asked whether they had taken any medication in the last 14 days and, if so, to provide the name of the medication. Medications were coded using British National Formulary codes which do not distinguish statins from other lipid lowering drugs, such inserm-00588857, version 1 -26 Apr 2011 as fibrates, nicotinic acid and its derivatives, cholesterol absorption inhibitors, or omega-3 fatty acid compounds. Thus, our measure included all lipid lowering drugs combined together.

Diet quality using the Alternate Healthy Eating Index (AHEI)

Diet quality was measured using the AHEI. [START_REF] Mccullough | Diet quality and major chronic disease risk in men and women: moving toward improved dietary guidance[END_REF]. Based on the 127 item anglicized version of Willett's Food Frequency Questionnaire (FFQ) [START_REF] Willett | Reproducibility and validity of a semiquantitative food frequency questionnaire[END_REF][START_REF] Brunner | Dietary assessment in Whitehall II: comparison of 7 d diet diary and food-frequency questionnaire and validity against biomarkers[END_REF], it has been found to yield a satisfactory estimate of food intake among Whitehall II participants compared to biomarkers and 7-day diet diaries [START_REF] Brunner | Dietary assessment in Whitehall II: comparison of 7 d diet diary and food-frequency questionnaire and validity against biomarkers[END_REF]. The AHEI includes nine food components; food items listed on the FFQ were assigned to their appropriate food groups, using the FFQ serving sizes identified. Eight of the nine components (vegetables, fruit, nuts and soy protein, ratio of white to red meat, dietary fibre, trans fat, ratio of polyunsaturated to saturated fatty acids, and alcohol) contributed 0-10 points to the total AHEI score. A score of 10 indicates that recommendations were fully met, whereas a score of 0 represents the least healthy dietary behaviour. Intermediate intakes were scored proportionally between 0 and 10. The final component, long-term multivitamin use, was dichotomized, contributing either 2.5 points (for non-use) or 7.5 points (for use) to the total score. All component scores were summed to obtain a total AHEI score ranging from 2.5 (worst) to 87.5 (best) [START_REF] Mccullough | Diet quality and major chronic disease risk in men and women: moving toward improved dietary guidance[END_REF]. Nutrient intake estimates were calculated using a computerized system developed for the Whitehall II dietary data [START_REF] Brunner | Dietary assessment in Whitehall II: comparison of 7 d diet diary and food-frequency questionnaire and validity against biomarkers[END_REF].

Physical activity

At baseline (phase 3), participants were asked the duration (number of hours per week) of their participation in moderately energetic (e.g., dancing, cycling, leisurely swimming, lawn mowing), and vigorous (e.g., running, hard swimming, playing squash) physical activity. At phase 7, the questionnaire was modified to include 20 items on duration of participation in different physical inserm-00588857, version 1 -26 Apr 2011 activities (e.g., running, cycling, other sports, housework, and gardening activities) that were used to compute hours per week at each intensity level. At both phases, physical activity was defined as the total number of hours per week spent in moderate and vigorous activity.

Covariates

Other variables included in the analysis were: sex; age at baseline (<45, 45-54, ≥55 years); selfreported ethnicity (White, non-White); education (none, lower secondary, A-levels, university or higher); current smoking (categorized as yes, no); and longstanding illness (categorized as yes, no). Prevalent CHD was defined using the MONICA criteria [START_REF] Tunstall-Pedoe | Myocardial infarction and coronary deaths in the World Health Organization MONICA inserm-00588857, version 1 -26 Apr 2011 Project. Registration procedures, event rates, and case-fatality rates in 38 populations from 21 countries in four continents[END_REF], positive responses to questions about chest pain [START_REF] Rose | Cardiovascular Survey Methods[END_REF] and physician diagnoses, evidence from medical records, or ECG findings.

Prevalent diabetes mellitus was defined as reported doctor-diagnosed diabetes mellitus or use of diabetes medication [START_REF]World Health Organization. Definition, Diagnosis and Classification of Diabetes Mellitus and Its Complications[END_REF]. Body mass index (BMI) was calculated as weight in kilograms divided by height in meters squared and categorized as normal (BMI<25), overweight (25≤BMI <30), or obese (≥30) [START_REF]Physical status: the use and interpretation of anthropometry: report of a WHO expert committee[END_REF].

Statistical analyses

Eleven-year change in LDL-cholesterol was calculated as phase 7 minus phase 3 values. In the analysis we wanted to determine the impact of the predictors assessed at baseline (phase 3) and their values over the 11-year follow-up. In order to simplify the interpretation of the coefficients, we categorized the predictors in the following way: lipid lowering drug use was categorized as no use, treated at baseline, or treatment started during the follow-up. Change in diet was estimated by subtracting AHEI score at baseline from that at phase 7, standardized to a z-score (mean=0, standard deviation (SD)=1) and categorized as "increase" (z-score>1), "stable" (-1≤z-score<1), and "decrease" (z-score≤-1). This procedure was first applied to the total AHEI score and then to inserm-00588857, version 1 -26 Apr 2011 the 9 components of the score. Change in physical activity was calculated by subtracting the number of hours per week of physical activity at baseline from that at phase 7. The difference in duration was standardized and categorized as an "increase" (z-score>1), "stable" (-1≤z-score<1), "decrease" (z-score≤-1) level of physical activity.

As 11-year changes in LDL-cholesterol, diet score, and physical activity were all normally distributed, parametric statistical tests were used in the analysis. To examine the unadjusted impact of the predictors (lipid lowering drug, diet, and physical activity) and the covariates we first conducted univariate analysis using linear regression with change in LDLcholesterol as the dependent variable. The interaction terms between the predictors and sex and age had p values p>0.05 negating any necessity to stratify the analyses by age or sex. For the quantitative predictors (diet and physical activity) and for change in BMI, we tested the interaction between continuous values at baseline and the change measures expressed as "increase", "stable", or "decrease". Only the interaction term between BMI at baseline and change in BMI was significant (p<0.05) and consequently was included in further analyses as a covariate.

We constructed 3 models to examine associations between the predictors and concomitant change in LDL-cholesterol. Model 1 included only non-modifiable covariates (sex, age at baseline, ethnicity) and the duration of follow-up. Model 2 further included education, BMI, and longstanding illness at baseline. Model 3 included all three predictors together with the covariates already in model 2. To examine the role of regression to the mean in declining LDLcholesterol trends, we repeated Model 3 among participants in the highest quintile of LDLcholesterol at baseline (in this subgroup regression to the mean is particularly likely) [START_REF] Morton | Effect of regression to the mean on decision making in health care[END_REF], and compared the results to those from the main analysis. In addition, for lipid lowering medication we removed any potential regression to the mean effect by comparing those with lipid-lowering inserm-00588857, version 1 -26 Apr 2011 medication during follow-up with a group without medication selected such that their mean LDLcholesterol values at baseline were identical.

Using the covariates and predictors in model 3, we conducted several supplementary analyses to determine: 1) whether specific components of the 9 item AHEI scale were associated with the reduction in LDL-cholesterol; 2) the effect of moderate and vigorous physical activity separately on change in LDL-cholesterol; 3) the impact of further adjusting model 3 for change in BMI and the interaction term between change in BMI and BMI at baseline; and 4) whether replacing the variable "presence of a long standing illness at baseline" by the variables "presence of at least one non-fatal CHD event at baseline" and "presence of diabetes mellitus at baseline" changed estimates.

The squared multiple correlation, also called coefficient of determination (R 2 ), was used to estimate the proportion of variation in LDL-cholesterol change explained by the predictors. We assessed change in R 2 when each predictor was entered individually into: 1) the initial model adjusted for sex, age at baseline, ethnicity, duration of follow-up, education level, BMI at baseline, and longstanding illness at baseline; 2) the model above plus mutual adjustment for the predictors [START_REF] Chao | Quantifying the relative importance of predictors in multiple linear regression analyses for public health studies[END_REF].

To examine potential beneficial effects related to lipid lowering drug treatment and favourable changes in diet and physical activity, we estimated the reduction in LDL-cholesterol that would be observed if 1) all participants in need of lipid-lowering drugs at baseline (n=858) were treated, 2) all individuals with a non-optimal diet (AHEI score <60, n=3457) improved their diet, defined as an increased AHEI score of at least 1 SD (0.6 point), and 3) those who undertake less than the recommended level of physical activity (<2.5 hours per week, n=2190) increased their physical activity, defined as a minimum increase of 17 minutes (1 SD) physical activity per week. Following European guidelines [START_REF] Graham | European guidelines on cardiovascular disease prevention in clinical practice: full text. Fourth Joint Task Force of the European Society of Cardiology and other societies on cardiovascular disease prevention in clinical practice (constituted by representatives of nine societies and by invited experts)[END_REF], participants with prevalent CHD or diabetes and inserm-00588857, version 1 -26 Apr 2011 those with a "high risk" of cardiovascular disease (CVD) defined as having 10-year risk of CVD death of 5% or more based on the SCORE (Systematic COronary Risk Evaluation) charts [START_REF] Conroy | Estimation of ten-year risk of fatal cardiovascular disease in Europe: the SCORE project[END_REF], were deemed to be in need of lipid lowering therapy. The benefits of lipid-lowering treatment, improved diet (> 1 SD) and increased physical activity levels (> 1 SD) for the total population were estimated based on Model 3 estimates using the following equation:

RESULTS

Description of the study participants

Of the 10,308 participants at recruitment to the study, 7,583 had complete data at phase 3 and 4,469 were included in the analysis reported here (Figure 1, comparison of the participants included in the analyses to those excluded is provided in Appendix, eTable 1). Table 1 describes the characteristics of those included at baseline and follow-up. The mean age at baseline was 49.3 years and 72.0% were men. From baseline to follow-up, the mean LDL-cholesterol concentration dropped from 4.38 to 3.52 mmol/L. At the same time the use of lipid lowering drugs increased from 0.8% to 10.8%. There was a small increase in the mean total AHEI score (from 50.7 to 51.2) and the mean number of hours/week spent in moderate or vigorous physical activity (from 3.4 to 3.7 hours/week).

inserm-00588857, version 1 -26 Apr 2011

At baseline, 858 participants had a high risk of CVD according to the European guidelines [START_REF] Graham | European guidelines on cardiovascular disease prevention in clinical practice: full text. Fourth Joint Task Force of the European Society of Cardiology and other societies on cardiovascular disease prevention in clinical practice (constituted by representatives of nine societies and by invited experts)[END_REF], had diabetes or had experienced a validated non-fatal CHD event at baseline, or took lipid lowering medication at baseline or follow-up. Only 60.0% (n=515) of them were taking lipid lowering medication at follow-up.

Multivariate analysis of change in lipid levels during the follow-up

Univariate analyses provided strong evidence of associations between changes in LDLcholesterol and all the covariates, with the exception of smoking (Appendix eTable 2). Table 2 presents multivariable-adjusted absolute changes in LDL-cholesterol as a function of lipid lowering medication and changes in diet and physical activity. These results show that LDLcholesterol declined in all groups. Table 3 shows the corresponding changes in relative terms.

Compared to those not on lipid lowering drugs, decline in LDL-cholesterol was greater among those who were on treatment at baseline or during the follow-up. Compared to those with a stable diet, individuals who improved their diet showed greater decline in LDL-cholesterol while those whose diet worsened showed a smaller decline. Similar results were observed for physical activity. All relative differences persisted after serial adjustments for multiple covariates (Table 3). The results were largely similar in a sub-group of participants in the top quintile of LDLcholesterol at baseline and when, for lipid lowering medication, potential regression to the mean effects were totally removed (Appendix eTable 3).

More detailed analyses of the 9 components of the AHEI diet score and intensity of physical activity are shown in Appendix eTables 4 and 5. Briefly, the decline of LDLcholesterol change was significantly associated with an increase of the ratio of white to red meat consumption (p<0.001), the ratio of polyunsaturated to saturated fatty acids (p<0.001), increase in inserm-00588857, version 1 -26 Apr 2011 the fruit consumption (p=0.04) and decrease in trans fats (p=0.04). Decreases in both moderate and vigorous physical activity were associated with a smaller decrease in LDL-cholesterol.

In sensitivity analyses, we examined the role of BMI by adding the following covariates to model 3: change in BMI and the interaction term between change in BMI and BMI at baseline. The results remained largely unchanged. Similarly, when the variable "presence of a long standing illness at baseline" was replaced by the variables "presence of at least one non-fatal CHD event at baseline" and "presence of diabetes mellitus at baseline" respectively in Model 3, the results were much the same (data not shown).

Multivariate analyses of changes in other lipid fractions are provided in Appendix, eTable 6. An increase in physical activity was associated with a 0.05 mmol/L greater increase in HDL-cholesterol compared with those who had a stable level of physical activity. Participants whose BMI increased over the follow-up showed a 0.01 mmol/L decrease in HDL-cholesterol and 0.27 mmol/L increase in triglycerides; among those with stable BMI, HDL-cholesterol increased by 0.11 mmol/L and triglycerides decreased by 0.07 mmol/L. Participants whose alcohol consumption increased had a 0.08 mmol/L greater increase in HDL-cholesterol than those whose alcohol consumption was stable. Among participants who stopped smoking during followup, there was a 0.04 mmol/L greater increase in HDL-cholesterol compared with never smokers.

Relative importance of medications, diet and physical activity in explaining LDLcholesterol trends

The baseline model for this analysis, including sex, ethnicity, duration of follow-up and baseline 4). If all 3457 participants who did not have an optimal diet (AHEI score <60) had improved their diet, the corresponding additional decline in LDL-cholesterol would have been 0.08 mmol/L. Adoption of a more physically active lifestyle by the 2190 participants who undertook less than 2.5 hours of moderate or vigorous activities per week would have produced an additional decline in LDL-cholesterol of 0.11 mmol/L. These estimations applied to the total cohort (n=4469) suggest that successful implementation of lipid-lowering therapy and change in lifestyle would each reduce LDL-cholesterol levels by 0.90 to 1.07 mmol/L (Table 4).

DISCUSSION

We found an overall decrease in LDL-cholesterol concentration in the Whitehall II cohort of civil servants over 11 years of follow-up. The degree of decline was associated with an increased use of lipid lowering drugs, improvements in dietespecially the ratio of white to red meat consumption and the ratio of polyunsaturated to saturated fatty acids intakeand increase in physical activity. In this population, the contribution of changes in diet and physical activity were inserm-00588857, version 1 -26 Apr 2011 modest compared to pharmacological treatment among individuals at high risk of CVD.

However, a successful implementation of lipid-lowering drug treatment for the relatively small group of high-risk individuals and a favourable change in diet and physical activity in the large group of people with a non-optimal lifestyle were estimated to result in largely similar declines in LDL-cholesterol in the total cohort. These findings support the use of multifaceted intervention strategies for prevention.

In many previous studies, decrease in LDL-cholesterol concentration has been assessed by comparing cross-sectional surveys repeated over time: in the INTERGENE and GOT-MONICA study (1985, 1990, 1995, and 2002) [START_REF] Berg | Trends in blood lipid levels, blood pressure, alcohol and smoking habits from 1985 to 2002: results from INTERGENE and GOT-MONICA[END_REF], in the French MONICA study (1996 and 2007) [START_REF] Ferrieres | Trends in plasma lipids, lipoproteins and dyslipidaemias in French adults, 1996-2007[END_REF], in the studies conducted in Catalonia, Spain (1992 and 2003) [START_REF] Serra-Majem | Trends in blood lipids and fat soluble vitamins in Catalonia, Spain (1992-2003)[END_REF] and in Gerona, Spain (1995, 2000, and 2005) [START_REF] Grau | Trends in cardiovascular risk factor prevalence (1995-2000-2005) in northeastern Spain[END_REF]. This design captures time trends but, unlike the prospective cohort design employed in the present study, does not allow estimation of within-subject changes in LDLcholesterol, or in their predictors.

Our study confirms the findings of the few prior cohort studies on changes in total or LDL-cholesterol among middle-aged individuals. In an Australian population-based cohort study, Buyken et al [START_REF] Buyken | Modifications in dietary fat quality are associated with changes in serum lipids of older adults independently of lipid medication[END_REF] reported a decrease of 0.7 mmol/L in LDL-cholesterol between 1992 and 2004, comparable to the 0.9 mmol/L decrease in our study. Two other cohort studies, the New Zealand Workforce Diabetes Survey [START_REF] Metcalf | Factors associated with changes in serum total cholesterol levels over 7 years in middle-aged New Zealand men and women: a prospective study[END_REF] and the American Physicians' Health Study [START_REF] Scranton | Predictors of 14-year changes in the total cholesterol to high-density lipoprotein cholesterol ratio in men[END_REF], also reported a decline in LDL-cholesterol from 1988 to 1997 and from 1982 to 1997, respectively. In the Framingham Heart Study [START_REF] Ingelsson | Contemporary trends in dyslipidemia in the Framingham Heart Study[END_REF], there was a slight increase in LDL-cholesterol over time, but these analyses did not include individuals on lipid lowering or hormone replacement therapies, or those with prevalent cardiovascular disease. Randomized trials have shown lipid lowering drugs [START_REF] Cui | Effects of increasing high-density lipoprotein cholesterol and decreasing low-density lipoprotein cholesterol on the incidence of first acute coronary events (from the Air Force/Texas Coronary Atherosclerosis Prevention Study)[END_REF][START_REF] Nakamura | Primary prevention of cardiovascular disease with pravastatin in Japan (MEGA Study): a prospective randomised controlled trial[END_REF], diet modification [START_REF] Nakamura | Primary prevention of cardiovascular disease with pravastatin in Japan (MEGA Study): a prospective randomised controlled trial[END_REF][START_REF] Brunner | Dietary advice for reducing cardiovascular risk[END_REF][START_REF] Howard | Low-fat dietary pattern and risk of cardiovascular disease: the Women's Health Initiative Randomized Controlled Dietary Modification Trial[END_REF][START_REF] Varady | Combination diet and exercise interventions for the treatment of dyslipidemia: an effective preliminary strategy to lower cholesterol levels?[END_REF] and endurance exercise training [START_REF] Varady | Combination diet and exercise interventions for the treatment of dyslipidemia: an effective preliminary strategy to lower cholesterol levels?[END_REF][START_REF] Halverstadt | Endurance exercise training raises high-density lipoprotein cholesterol and lowers small low-density lipoprotein and very low-density lipoprotein independent of body fat phenotypes in older men and women[END_REF][START_REF] Wilund | Effects of endurance exercise training on markers of cholesterol absorption and synthesis[END_REF] There are a few caveats to the results reported here. First, total cholesterol and triglyceride were not measured using the same enzymatic methods at both study phases; but HDL-cholesterol was assessed using the dextran sulphate-magnesium precipitation method at baseline and the direct homogeneous method at follow-up [START_REF] Warnick | Evolution of methods for measurement of HDLcholesterol: from ultracentrifugation to homogeneous assays[END_REF]. These protocol changes might have affected the estimation of absolute LDL levels. However, this is an unlikely source of major bias because both methods have been validated and certified by the Cholesterol Reference Method Laboratory Network at the Centers for Disease Control and Prevention [START_REF] Kimberly | Selection, validation, standardization, and performance of a designated comparison method for HDL-cholesterol for use in the cholesterol reference method laboratory network[END_REF][START_REF]Programs: Cholesterol Reference Method Laboratory Network[END_REF], and the agreement between the methods is high with a correlation coefficient of 0.98, slope 0.98 and mean bias 0.05 mmol/L [START_REF] Bairaktari | Homogeneous HDL-cholesterol assay versus ultracentrifugation/dextran sulfate-Mg2+ precipitation and dextran sulfate-Mg2+ precipitation in healthy population and in hemodialysis patients[END_REF]. If the level of HDL-cholesterol was "overestimated" by 0.05 mmol/L at follow-up in the present study, the method-related decrease in LDL-cholesterol between baseline and follow-up would have been approximately 0.06 mmol/L, which is small compared to the mean observed decrease of 0.86 mmol/L. Furthermore, bias resulting from the change in the method of assessing HDL-cholesterol is likely to be independent of the measurement of the predictors and thus should not unduly bias our findings on relative differences in changes in LDL-cholesterol between subgroups.

Second, physical activity and, to a greater extent, dietary intake, are difficult to measure accurately; while it is likely that use of lipid-lowering drugs is recalled with greater precision. We may have therefore underestimated the effects of diet and physical activity on LDL-cholesterol decline. Furthermore, it is possible that we underestimated the contribution of diet because our analysis did not fully capture effects arising from externally driven secular changes in dietary patterns. For example, recommendations from the National Institute for health and Clinical Excellence (NICE) encourage manufacturers, caterers and producers to reduce the amount of inserm-00588857, version 1 -26 Apr 2011 saturated and trans fatty acids in all food products and replace them, if needed, by polyunsaturated and monounsaturated fatty acids [START_REF]Prevention of cardiovascular disease at population level[END_REF]. Such guidance, if successful in reducing "bad" cholesterol in marketed foods, could, potentially, have a notable impact on the number of cardiovascular events at the population level, as is clear from results from the recent metaanalysis of randomised controlled trials [START_REF] Mozaffarian | Effects on coronary heart disease of increasing polyunsaturated fat in place of saturated fat: a systematic review and meta-analysis of randomized controlled trials[END_REF].

Third, regression toward the mean is a potential source of bias in observational studies with repeat outcome measures [START_REF] Morton | Effect of regression to the mean on decision making in health care[END_REF]. Regression to the mean arises from random errors in measurement and should be relatively independent of the use of lipid-lowering drugs or lifestyle.

In the present study, these factors remained important predictors of reduced LDL levels in a subgroup of participants with particularly high LDL-cholesterol at baseline, a group whose measures are likely to contain more measurement error, suggesting that regression to the mean had, if anything, little impact on our findings. Fourth, by definition, occupational cohorts such as Whitehall II are fitter than the general population due to the healthy worker effect. The feedback provided to participants after medical screening Phases of the study about their coronary risk factors may also have promoted healthier lifestyles, as discussed in relation to the Framingham study [START_REF] Ingelsson | Contemporary trends in dyslipidemia in the Framingham Heart Study[END_REF]. Thus, further research is needed to examine the generalisability of our findings.

With the limitations of our study in mind, we conclude that declining trends in LDLcholesterol seems to be independently associated with the use of lipid lowering therapy and favourable lifestyle changes. Our findings suggest that more should be done to reduce undertreatment of dyslipidaemia and promote lifestyle modifications in order to further accelerate the favourable population trends in LDL-cholesterol.

inserm-00588857, version 1 -26 Apr 2011

government employees) on a worldwide basis to the BMJ Publishing Group Ltd and its Licensees to permit this article (if accepted) to be published in HEART editions and any other BMJPGL products to exploit all subsidiary rights" having a longstanding illness at baseline. ΔR 2 = R 2 from the current model -R 2 from the reference model.

y

  = Intercept + β1 I treatment at baseline + β2 I treatment during the follow-up + β3 I one or more SD decrease in AHEI score + β4 I one or more SD increase in AHEI score + β5 I one or more SD decrease in hours of physical activity + β6 I one or more SD increase in hours of physical activity + β7 Men + β8 Age at baseline + β9 Ethnicity + β7 I intermediate education + β8 I high education + β9 BMI at baseline + β10 Longstanding illness + β11 Duration of follow-up, where  y is change in LDL cholesterol and I an indicator variable (1 vs 0). All analyses were performed with SAS software, version 9 (SAS Institute Inc, USA).

  measures of age, education, BMI and longstanding illness as covariates, explained 11.6% of the variability in the change in LDL-cholesterol. Adding lipid lowering drugs to this model increased the coefficient of determination (R 2 ) by 29.4%. AHEI diet score and physical activity, when inserm-00588857, version 1 -26 Apr 2011 added into the baseline model, explained only 0.5% and 0.3% of the variability in the change in LDL-cholesterol concentrations, respectively. Each predictor had an independent effect in the mutually adjusted model. (Appendix eTable 7) Estimated population-level benefits of lipid-lowering drugs and improved lifestyle Based on Model 3 estimates, if all 858 participants with prevalent CHD or diabetes or a high risk of CVD death at baseline had been on lipid-lowering medication, as suggested in European guidelines, then the decline in LDL-cholesterol would have been 2.77 mmol/L greater than the observed value (Table

  to be effective in lowering LDL-cholesterol concentrations. The present results, obtained from an observational study, add to inserm-00588857, version 1 -26 Apr 2011 knowledge from randomized controlled trials where the effect size is dependent on specific interventions.

Table 1 .

 1 Baseline (phase 3) and follow-up (phase 7) characteristics of the 4,469 study participants.

	Baseline (1991-93)	Phase 7 (2003-04)
	N	% / Mean (SD)	N	% / Mean (SD)

SD = standard deviation; LDL = low-density lipoprotein; BMI = body mass index; AHEI = alternate healthy eating index.

Table 2 .

 2 Absolute change in serum LDL-cholesterol between the baseline (1991-1993) and follow-up (2003-2004) screening as function of use of lipid-lowering drugs, healthy diet, and physical activity, (N=4,469). Model 1: Adjusted for sex, age at baseline, ethnicity, and duration of follow-up. † Model 2: As model 1 and additionally adjusted for education level, BMI at baseline, and longstanding illness at baseline. ‡ Model 3: As model 2 with predictors mutually adjusted.

				Mean absolute change in LDL-cholesterol (95% CI), mmol/L
			n	Model 1*	Model 2 †	Model 3 ‡
		Start of lipid lowering drug
		None	3954 -0.61 (-0.66 to -0.56)	-0.60 (-0.65 to -0.56)	-0.59 (-0.65 to -0.53)
	inserm-00588857, version 1 -26 Apr 2011	Baseline During follow-up Change in AHEI score Increase (≥1 SD) Stable (-1≤SD<1) Decrease (<-1 SD) Change in physical activity Increase (≥1 SD) Stable (-1≤SD<1) Decrease (<-1 SD)	34 481 717 3071 -0.85 (-0.92 to -0.79) -1.70 (-1.96 to -1.43) -2.42 (-2.50 to -2.34) -0.99 (-1.08 to -0.91) 681 -0.76 (-0.85 to -0.67) 601 -0.98 (-1.07 to -0.88) 3312 -0.86 (-0.92 to -0.80) 556 -0.77 (-0.87 to -0.68)	-1.70 (-1.96 to -1.43) -2.38 (-2.46 to -2.30) -0.99 (-1.07 to -0.90) -0.84 (-0.90 to -0.78) -0.75 (-0.83 to -0.66) -0.95 (-1.05 to -0.86) -0.85 (-0.91 to -0.79) -0.76 (-0.85 to -0.66)	-1.73 (-1.99 to -1.46) -2.36 (-2.45 to -2.28) -1.65 (-1.76 to -1.53) -1.58 (-1.68 to -1.47) -1.46 (-1.57 to -1.35) -1.66 (-1.78 to -1.54) -1.56 (-1.66 to -1.46) -1.46 (-1.58 to -1.34)

CI = confidence interval; other abbreviations as in Table

1

. *

Table 3 .

 3 Relative change in serum LDL-cholesterol (mmol/L) between the baseline (1991-1993) and follow-up(2003)(2004) screening as a function of use of lipid-lowering drugs, healthy diet, and physical activity, (N=4,469). Adjusted for sex, age at baseline, ethnicity, and duration of follow-up. † Model 2: As model 1 and additionally adjusted for education level, BMI at baseline, and longstanding illness at baseline. ‡ Model 3: As model 2 with predictors mutually adjusted.

			Mean relative change in LDL-cholesterol (mmol/L) and P-value for difference
		n		Model 1*		Model 2 †		Model 3 ‡
	Start of lipid lowering drug
	None	3954	0	Reference	0	Reference	0	Reference
	Baseline	34	-1.09	<0.001	-1.09	<0.001	-1.14	<0.001
	During follow-up	481	-1.81	<0.001	-1.77	<0.001	-1.77	<0.001
	Change in AHEI score
	Increase (≥1 SD)	717	-0.14	<0.001	-0.14	<0.001	-0.07	0.03
	Stable (-1≤SD<1)	3071	0	Reference	0	Reference	0	Reference
	Decrease (<-1 SD)	681	0.10	0.02	0.10	0.02	0.12	<0.001
	Change in physical activity
	Increase (≥1 SD)	601	-0.11	0.007	-0.10	0.02	-0.10	0.005
	Stable (-1≤SD<1)	3312	0	Reference	0	Reference	0	Reference
	Decrease (<-1 SD)	556	0.09	0.04	0.09	0.03	0.10	0.004
	Abbreviations as in Tables 1 and 2.

* Model 1:

Table 4 .

 4 Estimated beneficial effect of lipid lowering drugs, healthy diet, and physical activity on LDL-change in the population at risk and the total cohort

	Mean LDL-cholesterol (mmol/L) change

* Here intervention stands for use of a lipid lowering drug among those needed such a treatment according to the European guidelines, improving diet among those with AHEI score <60, or increasing duration of physical activity among those with <2.5 hours per week. 1 SD increase in AHEI score is 0.6 point and 1 SD increase in physical activity is 17 minutes per week † Decline in LDL-cholesterol estimated for participants who met the criteria for intervention based on effects shown in

Table 3 ,

 3 Model 3. ‡ Participants with CVD risk score > 5% or prevalent CHD or diabetes at baseline, or lipid lowering medication at baseline or follow-up. § Participants with AHEI score <60 at baseline. Comparison of characteristics between participants included in the present analysis and participants not included but eligible at baseline (phase 3), N=7,583. Adjusted for sex, age at baseline, ethnicity, duration of follow-up, education level, BMI at baseline and longstanding illness at baseline, lipid lowering drug use, and diet score. † P-value for relative difference. ‡ In a supplementary analysis, the mean decline in LDL cholesterol among the 481 participants with lipid-lowering 5. Absolute change in serum LDL-cholesterol between the baseline (1991-1993) and follow-up (2003-2004) screenings as a function of change in physical activity (hours/week) and intensity of physical activity. (n=4,469). Moderate physical activity included sports such as dancing, swimming. † Vigorous physical activity included sports such as running, playing squash. ‡ Adjusted for sex, age at baseline, ethnicity, duration of follow-up, education level, BMI at baseline, and having a longstanding illness at baseline, lipid lowering drug use, and diet score. § P-value for relative difference. inserm-00588857, version 1 -26 Apr 2011 eTable 6. Absolute change* in serum HDL-cholesterol and triglyceride between the baseline (1991-1993) and follow-up (2003-2004) screenings according to different predictors (n=4,469) After adjustment for sex, age, ethnicity, educational level, BMI, and longstanding illness at baseline, and duration of follow-up. Predictors were mutually adjusted. † P-value for relative difference. ‡ Non-smoker at baseline and at follow-up. # Stopped smoking after baseline (phase 3). inserm-00588857, version 1 -26 Apr 2011 eTable 7. Proportion of variance (R 2 ) explained by lipid lowering drug, and change in diet and physical activity (n=4,469).

	inserm-00588857, version 1 -26 Apr 2011
	# Participants with physical activity<2.5 hours/week at baseline.

* AHEI = alternate healthy eating index; LDL = low-density lipoprotein; CI = confidence interval; SD = standard deviation; PUFAs/SFAs = ratio of polyunsaturated to saturated fatty acids. * Adjusted for sex, age at baseline, ethnicity, duration of follow-up, education level, BMI at baseline, and having a longstanding illness at baseline, lipid lowering drug use, and physical activity. † P-value for relative difference. ‡ "Decrease" in trans fat score corresponds to an increased consumption of trans fatty acids during follow-up. § "Decrease" in alcohol score corresponds to a "non-ideal" consumption of alcohol during follow-up. eTable * HDL = high-density lipoprotein; CI = confidence interval; SD = standard deviation. * * Baseline model includes sex, age at baseline, ethnicity, duration of follow-up, education level, BMI at baseline, and

Acknowledgments: All authors contributed to conception and design, and to analysis and interpretation of data; or, wrote the first draft of the article and revised it critically for important intellectual content. All approve the final version to be published.

We thank all participating men and women in the Whitehall II Study; all participating Civil Service departments and their welfare, personnel, and establishment officers; the Occupational Health and Safety Agency; and the Council of Civil Service Unions. The Whitehall II Study team comprises research scientists, statisticians, study coordinators, nurses, data managers, administrative assistants and data entry staff, who make the study possible. We also thank Drs Anthony Wierzbicki and Gill Rumsby for providing us with information on cholesterol measurements.

Funding: The Whitehall II study has been supported by grants from the Medical Research Council, UK; Economic and Social Research Council, UK; British Heart Foundation, UK; Health and Safety Executive, UK; Department of Health, UK; BUPA Foundation, UK; National Heart Lung and Blood Institute (R01HL036310), US; NIH: National Institute on Aging (R01AG013196; R01AG034454), US. GDB is a Wellcome Trust Fellow (WBS U.1300.00.006.00012.01), UK. MJS is supported by the British Heart Foundation. MK is supported by the BUPA Foundation, UK, the Academy of Finland, Finland, and the EU OSH ERA research programme.

Role of the Funding Source:

The study sponsors had no role in study design; in the collection, analysis, and interpretation of data; in writing of the report; or in the decision to submit the paper for publication.

Copyright licence statement: "The Corresponding Author has the right to grant on behalf of all authors and does grant on behalf of all authors, an exclusive licence (or non exclusive for inserm-00588857, version 1 -26 Apr 2011

Competing interests: None.


Jérémie Du Boisberranger
email: jeremie.du-boisberranger@prism.uvsq.fr

Danièle Gardy
email: daniele.gardy@prism.uvsq.fr

Xavier Lorca
email: xavier.lorca@mines-nantes.fr

Charlotte Truchet
email: charlotte.truchet@univ-nantes.fr

A Probabilistic Study of Bound Consistency for the Alldifferent Constraint

This paper introduces a mathematical model for bound consistency of the constraint AllDifferent. It allows us to compute the probability that the filtering algorithm effectively removes at least one value in the variable domains. A complete study of the bound consistency properties is then proposed. It identifies several behaviors depending on some macroscopic quantities related to the variables and the domains. Finally, it is shown that the probability for an AllDifferent constraint to be bound consistent can be asymptotically estimated in constant time. The experiments illustrate that the precision is good enough for a practical use in constraint programming.

Definition 2. A sample space Ω is a non-empty set. An event on Ω is a subset of Ω. The set of all possible events is the set of parts of Ω, denoted P(Ω). Two events are said mutually exclusive if and only if they have an empty intersection.

Introduction

Constraint Programming (CP) aims at solving hard combinatorial problems expressed as Constraint Satisfaction Problems (CSP): variables are the unknown of the problem, each variable has a domain of possible values and the constraints are logical predicates that link the variables. The CP operational nature is based on the propagation-search paradigm. The search part consists in an exploration of the possible assignments of domains values to the variables, while the filtering/propagation mechanism detects and suppresses inconsistent parts of the domains (i.e. values that cannot appear in a solution of the constraints).

In particular, filtering algorithms for global constraints [START_REF] Bessière | a Global Constraint[END_REF], which define logical relations on a subset of the variables, have been intensively studied. They are usually more efficient than the propagation of equivalent expressions as several binary or small arity constraints. One of the major issues in studying propagation is the pursuit of a fair balance between efficiency (time complexity) and effective performance, which can be expressed for instance as the number of inconsistent values detected by the filtering algorithms. It may happen that propagation algorithms are useless (no inconsistent values detected), and, even if they are often efficient, they are called each time a value is assigned to a variable. In the worst case, this makes a number of calls exponential in the number of variables.

This paper introduces a probabilistic model for bound consistency (BC) of the alldifferent constraint, relying on the inner combinatorics of this constraint. In this model, it defines the probability that the BC algorithm removes at least one value in the variable domains. Then, a complete study of this model is developed for two different probability distributions for the domains. The interest of this study is twofold: first, the probability computation leads to the identification of several distinct behaviors, depending on some macroscopic quantities of the problem. Secondly, we show that the probability that a BC algorithm is effective can be estimated in constant time. Experiments confirm that this asymptotical approximation is precise enough for a practical use.

This work strongly relies on the combinatorics embedded in many global constraints (e.g. at least all the cardinality constraints). This link has also been exploited by [START_REF] Zanarini | Solution counting algorithms for constraint-centered search heuristics[END_REF] to count the number of solutions of a constraint, in order to predict promising areas of the search space and guide search heuristics. Although their goal is different from ours, they also exploit the mathematics and combinatorics inside these constraints. In another way, triggering the filtering algorithm of a global constraint has also been proposed in [START_REF] Katriel | Expected-case analysis for delayed filtering[END_REF] for the global cardinality constraint. The author determines a threshold, based on the possible variable-values assignments, to determine if the filtering algorithm must be executed. Such an approach leads to a good tradeoff between calculation time and effective filtering.

In the following, Section 2 introduces a probabilistic model of the bound consistency AllDifferent constraint. Section 3 presents the mathematical results of the paper, for two distributions of the variables domains. Section 4 criticizes these results, and provides a practical validation. Section 5 concludes this paper and discusses some further works.

Probabilistic Approach of Bound Consistency

After some preliminaries definitions and propositions on BC for alldifferent and on probabilities, we introduce a probabilistic model for BC of alldifferent. Then we define the probability that an alldifferent constraint remains BC after an instantiation and give a general formula for it.

Consider an alldifferent constraint on n variables V 1 ...V n , with domains D 1 ...D n . The size of domain D i is d i = |D i |. Let E be the union of all the domains: E = ∪ 1≤i≤n D i , and m its size. For an integer interval E and a set I, we write I ⋐ E as a shortcut for : I ⊂ E and I is an integer interval.

Bound consistency for alldifferent

The alldifferent constraint is a well known global constraint for which many consistency algorithms have been proposed. The reader can be refered to Van Hoeve's survey [START_REF] Van Hoeve | The alldifferent constraint: A survey[END_REF] for a state of the art. We focus here on bound consistency, as proposed by [START_REF] Puget | A fast algorithm for the bound consistency of alldiff constraints[END_REF], and thus assume that all the domains D i are integer intervals. E can be assumed to be an integer interval without loss of generality (if E is not an interval, it can be cut into different pieces, with independent alldifferent constraints for each of them). Hall intervals are the subintervals of E that contain just enough values to ensure that every variable of K I can be assigned a value. Consequently, the other variables (those not in K I ) cannot take their values in I. Proposition 1. A alldifferent constraint on a set of variables V 1 ...V n , a set of domains D 1 ...D n is bound-consistent if and only if the two following conditions are true:

1. for I ⋐ E, |K I | ≤ |I|, 2. and for I ⋐ E, |K I | = |I| implies ∀i / ∈ K I , I ∩ D i = ∅.
In the following, we are interested in what happens during an instantiation. It can be assumed without loss of generality that the instantiation is done for the variable V n (rename the variables if necessary). V n is assigned a value x ∈ D n . We also assume that the binary constraints = have been filtered (that is, only the x value has been removed from the other domains, which is equivalent to a Forward Checking on the = clique).

The number of variables n is computed dynamically, that is, n is the number of free variables before the instantiation. Let E • be the state of E before the instantiation (E • = D 1 ∪ ... ∪ D n ), and E ⊗ be the state of E after the instantiation (E ⊗ = D 1 ∪ ... ∪ D n-1 ). In the same way, for an interval

I ⋐ E, I • = I ⊗ ∪ {x} if I ⊗ = I • and I ⊗ otherwise.
The following Proposition details in which case the constraint, being BC on V 1 ...V n , remains BC after the instantiation of V n .

Proposition 2. Consider a alldifferent constraint on variables V 1 ...V n , with domains D 1 ...D n , such that the constraint is BC. Assume that the variable V n is set to a value x ∈ D n , and let v be the position of x within E • (v = xmin(E • )). The constraint remains BC if and only if there exists I ⊗ ⋐ E ⊗ such that I ⊗ = I • and the two following conditions hold: Proof. The proof is based on the fact that an instantiation cannot create new intersections on the domains. Suppose that the problem is BC, then

∀I • ⋐ E • , |K I • | ≤ |I • |. Let I ⊗ ⋐ E ⊗ , and l = |I ⊗ | and α = min(I ⊗ ) -min(E ⊗ ). If α + l < v, that is, I ⊗ = I • , we have |K I ⊗ | = |K I • | ≤ |I • |.
Indeed, even a domain which had x for right bound before the instantiation, has its right bound out of I ⊗ after. Then, item 2. of Proposition 1 holds by the first remark. In that case, no inconsistency is created. If α > v, the argumentation is the same, interchanging left by right. If α+l ≥ v and α ≤ v, that is

I ⊗ = I • , there are 2 possibilities. If D n ⋐ I • , we have |I ⊗ | = |I • | -1 and |K I ⊗ | = |K I • | -1. If |K I • | = |I • |, then |K I ⊗ | = |I ⊗ |,
|K I • | < |I • |. If |K I • | < |I • | -1, then |K I ⊗ | < |I ⊗ | and 1. (prop. 1) holds. Otherwise, |K I • | = |I • | -1, then |K I ⊗ | = |I ⊗ |,
and an inconsistency can only come from an intersection between I ⊗ and at least one domain which is not included in I ⊗ . ⊓ ⊔

Some Probability Notions

Only the notions of discrete probability theory that are needed afterwards are presented here. For a good and complete introduction to probability theory, the reader can refer to [START_REF] Grimmett | Probability and Random Processes[END_REF]. For a given probabilistic phenomenon, the sample space is the set of all possible outcomes. For instance, consider the process of flipping a coin, the sample space would be the possible results of the coin flip, that is, the set {tails, heads}. In probability theory, events are what is observed and measured. In the example, an event could be {tails}, meaning that we want to observe the fact that the coin ended on tails. The events are defined as sets, but it is equivalent, and often more intuitive, to see them as predicates: "the result is tails". This event is for instance mutually exclusive with the event "the result is heads". A probability distribution is a tool to measure events. In the previous example, we can define a probability distribution by: P[{heads}] = p, P[{tails}] = 1p for a p ∈ [0, 1]. If p = 0.5, we have modeled the random process of flipping a perfectly fair coin. Other values of p model the same process with a biased coin. Definition 4. Two events A and B on a probability space (Ω, P(Ω), P) are said independent if and only if P[A ∩ B] = P[A]P[B]. Otherwise, the events are said correlated.

Intuitively, two events A and B are independent if A does not influence B, neither does B influence A. Definition 5. Let A and B be two events on a probability space (Ω, P(Ω), P). The conditional probability of B, knowing A, is P

[B|A] = P[A ∩ B]/P[A].
The question here is to quantify the probability of B, under the condition that A has happened, that is, in the subspace of Ω where A happened. This subspace is simply A itself, measured by P[A]. The probability of B within this subspace is P[A ∩ B]. Definition 6. Let S be a countable set and (Ω, P(Ω), P) a probability space. A discrete random variable X is a function

X : Ω → S. The distribution of X is P X : S → [0, 1] such that P X [s] = P[X -1 (s)] for s ⊂ S.
Proposition 3. The distribution of a discrete random variable is a probability distribution.

We do not detail the proof for Proposition 3 which can be found for instance in [START_REF] Grimmett | Probability and Random Processes[END_REF]. A discrete random variable is an event with a discrete or finite set of outcomes.

A probabilistic model for bound consistency

The constraint programmer's vocabulary includes expressions such as "this constraint alldifferent has little chance to filter here". The goal of this subsection is to propose a rigorous probabilistic model in which such expressions are well-defined. The key ingredients for consistency of an alldifferent constraint are the domains. Depending on their size and their relative position, the constraint may be consistent or not. However, sometimes it is not necessary to precisely know the domains in order to state if the constraint is consistent or not. For instance, an alldifferent constraint on three variables with domains of size 3 is always BC, whatever the exact positions of the domains. If the domains are of size 2, then the constraint may be BC or not, depending on the domains relative positions. But if E is also of size 2, the constraint is always inconsistent.

These basic remarks show that a partial knowledge on the domains and on E is sometimes sufficient to determine consistency properties. This is the basis of our probabilistic model: the domains become discrete random variables, with a given distribution (see in section 3). They are not fully determined: their exact sizes and positions are unknown. Only some macroscopic quantities are known.

Assume from now on that the domains D 1 ...D n are replaced by random variables with a known probability distribution. The sample space is naturally the set of subintervals of E = ∪ i D i . In the following we make the assumption that the D i variables are independent and that their distributions are identical. Let D be this distribution, with D(J) = P[D i = J] for J ⋐ E and 1 ≤ i ≤ n. This hypothesis, as well as all the hypotheses that are made later, are summed up and discussed in section 4.1.

We are interested in studying how this probability evolves during the search process. At each node explored during the solving process, one could consider that a new problem is stated. This new problem would be the initial CSP where all the instantiated variables become constants, and the constraints are dealt with accordingly. From a probabilistic point of view, this is a loss of information, because the successive CSPs are very unlikely to be independent. In order to analyze precisely the probability of being BC, we propose to study the probability that an alldifferent constraint, already BC, remains BC after an instantiation. Such a reasoning could be called conditional probability but for simplicity reasons we just call about "probability". This probability can be computed from Proposition 2. Proposition 4. For an alldifferent constraint on variables V 1 ...V n , where the domains are random variables with probability distribution D on an interval E of size m, the probability P m,n,v of remaining BC after instantiating the variable

V n to a value x at position v is P m,n,v = n-2 Y l=1 min(v, m -l -1) Y α = max(0, v -l) 1 -(1 -r m,l+1,α,v ) n -1 l ! p l m,l+1 " (1 -p m,l+1 ) n-l-1 -q n-l-1 m,l+1,α " !
where, for an interval I ⋐ E, of size l, at position α = min(I)min(E),

p m,l = P[D i ⊂ I], q m,l,α = P[D i ∩ I = ∅], r m,v,l,α = P[D i ⊂ I|x ∈ D i ].
and these I ⋐ E are assumed to be independent.

Proof. The constraint remains BC iff ∀I ⊗ ⋐ E ⊗ such that I ⊗ = I • , at least one of the conditions (1), (2) of Proposition 2 is false. Because the I ⊗ are assumed to be independent, "remaining BC" happens with probability:

I ⊗ ⋐ E ⊗ I ⊗ = I • (1 -P[(1)]P[(2)])
The subintervals of E are represented by their size l and position α. For a given size l, the condition I ⊗ = I • restricts the range for α to {max(0, vl)...min(v, ml -1)}. By definition, P[( 1)] = 1r m,l+1,α,v . Consider now the probability for [START_REF] Bessière | a Global Constraint[END_REF]. For l given domains, the probability that they are included in I • is p l m,l+1 , and there are n-1 l possibilities for choosing these domains among the n -1 domains. Consider now the nl -1 other domains: they must not be totally included in I ⊗ , which happens with probability (1p m,l+1 ) n-l-1 . In addition, one must forbid the case where they would all be totally outside I ⊗ , which happens with probability q n-l-1 m,l+1,α . Hence the formula.

⊓ ⊔

The "atomic probabilities" p m,l , q m,l,α and r m,v,l,α depend on the distribution D chosen for the domains (and their parameters of course). If they can be computed for a given distribution, then the formula gives the desired probability. Note that the formula relies on two products, each with n terms. Without further knowledge on the expressions of p m,l , q m,l,α and r m,v,l,α , the complexity of computing P m,n,v has an order of magnitude of O(n 2 ).

Computing the probabilities

In this section, we study two cases for the domains distribution D. For each of them, the atomic probabilities can be computed and inserted in Proposition 4. We still have to deal with the complexity of the formula, which has an order of magnitude at least n 2 . It is thus interesting to consider the asymptotic expansion of the probability when m tends towards infinity. The asymptotic expansion gives useful (and computationally cheap) numerical values for the probability of remaining BC.

Uniform domain distribution

In order to model the general case, that is, when the domains distribution is not biased toward specific domains (of a given lower bound, upper bound, etc), we define a uniform distribution for D i . Definition 7. Given an interval E of size m, a random variable D i on {J, J ⋐ E}, D i has a uniform distribution if and only if the probability P[D i = J] does not depend on J.

Remark 1. This implies:

-∀J ⋐ E, P[D i = J] = 1 |{J ′ ,J ′ ⋐E}| = 2 m(m-1) , -P[|D i | = d] = 2(m-d+1) m(m-1)
, thus the distribution of the domains sizes is biased toward small sizes.

With this distribution, the atomic probabilities p m,l , q m,l,α and r m,v,l,α of the formula in Proposition 4 can be computed.

Lemma 1. With the notations of Proposition 4, assume that D is a uniform distribution on E.

Then for an interval I ⋐ E, of size l, at position α:

p m,l = l(l-1) m(m-1) ; q m,l,α = α(α-1)+(m-l-α)(m-l-α-1) m(m-1) ; r m,v,l,α = (l-1)+(l-1+α-v)(v-α) (m-1)+(m-1-v)v .
Proof. From Proposition 4, we have p m,l = P[D i ⋐ I]. Considering the domains D i according to their size leads to:

P[D i ⋐ I] = m d=2 P[(D i ⋐ I) ∧ (|D i | = d)] = m d=2 P[(D i ⋐ I)|(|D i | = d)]P[|D i | = d] = m d=2 P[(D i ⋐ I)|(|D i | = d)] 2(m-d+1) m(m-1) from Remark 1 = m d=2 l-d+1 m-d+1 2(m-d+1) m(m-1) = l(l-1)
m(m-1) . For q m,l,α = P[D i ∩ I = ∅], the property is equivalent to: D i ⊂ E\I. The formula is thus similar to the computation for p m,l , by considering two subintervals of E, one strictly on the left of I and one strictly on the right.

Finally, we have

r m,v,l,α = P[D i ⋐ I|x ∈ D i ] = P[Di⋐I∧x∈Di] P[x∈Di]
. Thus, . The events {x ∈

D i |{|D i | = d}} and {{D i ⋐ I ∧ x ∈ D i }|{|D i | = d}} are respectively equivalent to {D i ⋐ E ∩ [x -d + 1, x + d -1]} and {D i ⋐ I ∩ [x -d + 1, x + d -1]}.
From there, the computation is similar to the one of p m,l .

⊓ ⊔

Assuming we know the quantities p m,l , q m,l,α and r m,v,l,α , Proposition 4 gives the probability of remaining BC. The following theorem gives an asymptotic expansion of this formula, when m tends toward infinity while the ratios n/m and v/(m -1) remain constant. Depending on the values of these ratios, different behaviors appear.

Theorem 1. Consider an alldifferent constraint on variables V 1 ...V n , with domains D 1 ...D n , such that the constraint is BC. Assume that the variable V n is set to a value x ∈ D n , and let v be the position of x within E (v = xmin(E)). Let ρ = n/m and ν = v/(m -1). Assume that the domains D i are uniformly distributed on E. Let P m,n,v be the probability that the alldifferent constraint remains BC after the instantiation. Then, when m → ∞ with fixed ρ and ν:

P m,ρm,ν(m-1) =            1 -4ρ m + O 1 m 2 if 0 < ρ < 1 and 0 < ν < 1 1 -2ρ(1-e -4ρ ) m + O 1 m 2 if 0 < ρ < 1 and ν = 0 or 1 1 -2(1-e -4 )+S m + O 1 m 2 if ρ = 1 and ν = 0 or 1 1 - 4+ S ′ 2ν(1-ν) m + O 1 m 2 if ρ = 1 and 0 < ν < 1
where S and S ′ are two constants that can be numerically computed:

S = ∞ k=1 2 k e -2k k k (k-1)! ≈ 1.94264 and S ′ = ∞ k=1 2 k e -2k k k (k+1) (k-1)! ≈ 11.9359.
The proof is detailed in Appendix A. It comes from using Lemma 1 in Proposition 4, and carefully bounding each term of the sum. Note that all these asymptotic expansions depend on the values of ρ and ν. However, they are always very close to 1. The first order term is known, with a second-order error term.

Corollary 1. The probability that an alldifferent constraint, in the uniform model, remains BC after an instantiation can be approximated, at the order O( 1 m 2 ), in time O(1), -depends on ρ = n/m, and ν = v/(m -1), that is, the number of available values for all the variables and the position of the instantiated value.

This corollary can be used in two ways. Firstly, it gives an approximation, in the limit m → ∞, with fixed ρ and ν, of the probability of remaining BC. This approximation can be computed in constant time, thus being competitive with any consistency algorithm. The precision of this approximation, of order 1 m 2 , is experimentally studied in Section 4.3. Secondly, it exhibits several different behaviors depending on the values of ρ and ν. Obviously, these quantities are meaningful in determining the behavior of an alldifferent constraint. This will be discussed in Section4.2.

Fixed-size domain distribution

It can also happen that the domains of a CSP are biased. Most of the time, they are biased toward a given size: for instance, many puzzle problems are stated on n variables with domains {1...n} (magic squares, sudoku, latin squares, etc). In order to model this case, we define a so-called fixedsize uniform distribution:

Definition 8. Given an interval E of size m, a fixed-size distribution of parameter d is an uniform distribution on {J ′ ⋐ E, |J ′ | = d}.
Remark 2. This implies: For this distribution, we add, in the notations, d as a parameter of the atomic probabilities: p m,l (d), q m,l,α (d) and r m,v,l,α (d). The atomic probabilities are given by the following lemma : Lemma 2. With the notations of Proposition 4, assume that D is a fixed-size distribution of parameter d on E. Then for an interval I ⋐ E, of size l, at position α:

-P[D i = J] = δ |J|,d m-d+1 , δ is the Kronecker delta: for a, b integers, δ a,b = 1 if a = b, 0 otherwise. -P[|D i | = d ′ ] = δ d,d ′ ,
p m,l = max 0, l-d+1 m-d+1 ; q m,l,α = max 0, α-d+1 m-d+1 + max 0, m-l-α-d+1 m-d+1 ; r m,v,l,α = H(l -d) min(v,α+l-d)-max(α,v-d+1)+1 min(v,m-d)-max(0,v-d+1)+1 . H is the Heaviside function: H(x) = 1 if x ≥ 0 and 0 otherwise.
Proof. The proof is exactly the same as for the uniform distribution, replacing

P[|D i | = k] by δ k,d .
⊓ ⊔

Assuming we know the atomic probabilities, we can compute the probability of remaining BC from Proposition 4. The following theorem gives an asymptotic expansion of this formula, when m tends toward infinity while the ratios ρ = n/m, ν = v/(m -1) and µ = d/m remain constant.

Theorem 2. Consider an alldifferent constraint on variables V 1 ...V n , with domains D 1 ...D n , such that the constraint is BC. Assume that the variable V n is set to a value x ∈ D n , and let v be the position of x within E (v = xmin(E)). Let ρ = n/m and ν = v/(m -1). Assume that the domains D i have a fixed-size distribution of parameter d on E, and let µ = d/m. Let P m,n,v (d) be the probability that the alldifferent constraint remains BC after the instantiation. Then, when m → ∞, and for fixed ρ, ν and µ:

P m,ρm,ν(m-1) (µm) =    1 if ν = 0 or ν = 1 or µ ≥ ρ 1 -o 1 m 2 if ρ < 1 and 0 < ν < 1 1 - Tνµ mΦνµ + O 1 m 2 if ρ = 1 and 0 < ν < 1
where Φ νµ = min(ν, 1µ)max(0, νµ) and

T νµ =              f (µ) if ν < µ and ν > 1 -µ f (µ) 2 + δ ν,µ f (µ) 2 -(1 -µ)g(µ) if ν ≥ µ and ν > 1 -µ f (µ) 2 -(1 -µ)g(µ) (δ ν,µ + δ ν,1-µ ) if ν ≥ µ and ν ≤ 1 -µ f (µ) 2 + δ ν,1-µ f (µ) 2 -(1 -µ)g(µ) if ν < µ and ν ≤ 1 -µ with g(µ) = ∞ k=1 k 1-µ k e -k 1-µ (k-1)! and f (µ) = ∞ k=1 (k + 1) k 1-µ k e -k 1-µ (k-1)! .
Again, the proof is detailed in Appendix B. It is very similar to the that of Theorem1. In this model, the asymptotic expansion depends on ρ and ν and also on the parameter µ. We can remark that the asymptotic expansions are closer to 1 than in the uniform model in some cases.

Corollary 2. The probability that an alldifferent constraint, in the fixed-size model, remains BC after an instantiation can be approximated, at the order O( 1 m 2 ), in time O(1), -depends on ρ = n/m, ν = v/(m -1) and µ = d/m, that is, the number of available values for all the variables, the position of the instantiated value, and the common size of the domains.

The same remarks as for Corollary 1 apply, and again this result will be discussed in Section4.

Analysis and Experiments

This section discusses the contributions of this paper, from several point of views: validity of the model, analysis of the two theorems, and experimental evaluation.

Validity of the Hypothesis

We propose a probabilistic model for BC of an alldifferent constraint. Like all models, it relies on a simplistic view of the reality, and this simplification is expressed by the mathematical hypotheses that have been used. The first hypothesis is on the domains, considered as random variables that are independent and identically distributed. As long as we do not consider other constraints, the independence assumption is reasonable, because the variables of the constraint do not interact outside the constraint under study. Going one step further, one could also consider the interactions between the constraints, for instance several alldifferent constraints as studied in [START_REF] Bessiere | Propagating conjunctions of alldifferent constraints[END_REF]. This is part of our further work. For the identical distribution, this is clearly a loss of information on the domains. Actually, loosing information on the domains is precisely the key point of the probabilistic model.

Another hypothesis holds on the subintervals of E used in Proposition 4. The I ⋐ E are assumed to be independent; more precisely, conditions (1) and ( 2) of Proposition 2 are assumed to be independent when I varies. These conditions express the "Hall status" of these intervals. The main argument to justify their independence is that this Hall property is local, that is, it cannot be transferred from an interval I to another. Given an interval I ⋐ E that is Hall for instance, there is no particular reason why other intervals I ′ ⋐ E should be Hall. The independence hypothesis seems thus reasonable.

The important results within the probabilistic model are the two theorems of Section 3, and they are valid in the limit m → ∞. This asymptotical result, which is rigorous, yields an approximated computation for P m,n,v , known until the second order error term. In practice, these theorems are valid for large values of m (at the beginning of the search process).

The last point is not a hypothesis, but also a limitation of the model: only two distributions for the domains have been considered. These distributions correspond to extreme scenarios: the uniform distribution implies that all the possible subintervals of E are equally weighted, that is, there is no particular bias in the domains distribution. On the contrary, the fixed-size uniform distribution restricts the domains to be of a fixed size, as it happens quite often, in problems coming from Artificial Intelligence for instance. To our knowledge, this should be sufficient to model quite a lot of real-life scenarios.

Technical Analysis

We propose the following terminology to discuss the Theorems 1 and 2. The number of variables over the total number of available values for them, ρ = n/m, determines if the problem is sharp (ρ = 1, exactly as many variables as values) or not (ρ < 1, some values will not be used in the end). The position of the instantiation ν = v/m is another important parameter. For ν = 0 or ν = 1, the instantiation is performed at a bound of E, which is possible, with a variable-value heuristics that chooses first a variable with a domain at a bound of E, say the minimum, then the minimum value of this domain. Note that there is a symmetry when ν is replaced by 1ν. Finally, if the domains size are fixed at d, then µ = d/m is the ratio of the domains size over the number of available values. A small value for µ mean that the domains are tight. If µ = 1, then the problem is not tight, and all the domains equal E.

Figure 2 shows the plots of the several limits given by Theorem 1. Problems that are not sharp (ρ < 1) have few chances to actually filter. As soon as m ≥ 50, the probability is higher than 0.9, meaning that there are at most 10% chances to remove a value (or more) from the domains. Notice that the curves are decreasing in ρ: sharper problems have better chances to filter. Instantiating Fig. 2. The asymptotic expansions of theorem 1, depending on the values of ρ and ν. The plain curves are for m = 50, the large dashed curves for m = 100 and the small dashed curves for m = 500. The plot range is [0, 1] for the first line, and is restricted to [0.9, 1] for the second line (otherwise the curves are too close to be identified).

at a bound (bottom left) yields a smaller probability to actually filter. For sharp problems, the behavior strongly depends on the value of ν.

The fixed-size model of Theorem 2 is quite different, as seen on Figure 3. For problems that are not sharp, the asymptotic expansion is 1 (not plotted): the domains being very specific, Hall intervals appear less frequently. For instance, the smallest possible Hall interval is of size d (2 in the uniform model). For sharp problems, the asymptotic expansion is of order 1/m, and depends on the tightness. First, note that the sizes of the problem, m, used to the left and right figures are different. Indeed, both functions f (µ) and g(µ) do not converge when µ → 0 and the validity of the approximation is not reached at the same union size m. On both figures, there are clearly 3 different phases, as stated by Theorem 2 for sharp problems. The probability goes through the 3 conditions, depending on the relative positions of ν, µ and 1µ. In addition, the behaviors are different depending on the domains size. In general, in order to filter more, it is preferable to instantiate at a bound.

Practical Evaluation

We have tested the validity of the asymptotic expansions of Theorems 1 and 2, with the BC algorithm for alldifferent provided by Choco [START_REF] Team | Choco: an open source java constraint programming library[END_REF]. For the experiments on Theorem 1 (resp. 2), given the parameters n and m (resp. n, m and d), we randomly generate n domains on the interval {1...m} according to the uniform distribution (resp. fixed-size uniform distribution of parameter d). If the generated domains do not cover E (which may happen for small values of n), then the experiment for these domains is removed.

An alldifferent constraint is then declared on n variables, with the randomly generated domains. The BC algorithm is called a first time, then an instantiation at position v is performed, v being a parameter of the test. Forward checking is applied on the binary difference constraints. This removes the obvious inconsistent values. We apply again the BC algorithm and check if the new filtering has removed at least one value (negative test), or no value at all (positive). Each test is repeated 3000 times for each parameter values. The proportion of positive and negative tests on these 3000 tests is represented as a dot on the plots (Figure 4). The theoretical curves are drawn with plain line.

We see on the plots that the dotted graphics are very close to the theoretical curves (Figures 4(a) and 4(b)). Very quickly (for m > 20), the error is around 1% (Figure 4(c)). These results experimentally validate the hypotheses of Section 4.1, and confirm the theoretical ones.

Conclusion

We have presented in this paper an accurate probabilistic indicator for the bound consistency of an alldifferent constraint. Moreover, this indicator can be computed in constant time. Not surprisingly, we still have to pay price; the intricate computations required to derived the easyto-use expressions of Theorems 1 and 2. In a few words, this paper shows that, considering an alldifferent constraint alone, bound consistency has a limited efficiency. On real-life problems, this leads us to think that its efficiency lies in its interactions with the other constraints.

However, our indicator allows us to tackle some challenges related to the practical uses of global constraints, e.g., triggering the filtering algorithms and guiding the heuristics. The filtering algorithms for global constraints are not effective all the time, and they may have a high complexity in some cases. We can prevent this phenomenon by limiting the practical complexity of the filtering by using the probabilistic indicator, one could inhibit most of the useless filtering. At another level, the consistency behavior differs, depending on some heuristic choices (variable value selection). The probabilistic model can thus help in designing heuristics on high level criteria (e.g., the ν parameter). Finally, which global constraints are good candidates for such a probabilistic approach? The global cardinality constraint and the NValue constraint have a combinatorial structure close to that of alldifferent. We hope to present a similar study of these constraints in further works.

A Proof of theorem 1

The probability P m,n,v , that an alldifferent constraint on n variables(with union of size m) stays consistent after the instanciation of a variable at the value x (at position v) is given by proposition 4. We set

L m,n,v,l,α = (1 -r m,v,l+1,α ) n-1 l p l m,l+1 (1 -p m,l+1 ) n-l-1 -q n-l-1 m,l,α
. Thus,

P m,n,v = n-2 l=1 min(v,m-l-1) α=max(0,v-l) (1 -L m,n,v,l,α ) = exp   n-2 l=1 min(v,m-l-1) α=max(0,v-l) log (1 -L m,n,v,l,α )   We also define X m,n,v,l = min(v,m-l-1) α=max(0,v-l) log (1 -L m,n,v,l,α ), such that P m,n,v = exp n-2 l=1 X m,n,v,l .
Let's set ρ = n/m and ν = v/(m -1). We have 0 < ρ ≤ 1 and 0 ≤ ν ≤ 1. We distinguish the 4 following cases : ρ < 1 and 0 < ν < 1; ρ < 1 and ν = 0 or 1; ρ = 1 and 0 < ν < 1; ρ = 1 and ν = 0 ou 1. In each case, we show that most of the terms are negligibles.

A.1 Case ρ < 1 and 0 < ν < 1 Let 0 < ǫ < 1/2, we cut the sum on l as follows :

l = 1, 2, 3; 3 < l < (n -1) ǫ ; (n -1) ǫ ≤ l ≤ n -2.
l = 1, 2, 3. We have

X m,n,v,1 = min(v,m-2) α=max(0,v-1) log (1 -L m,n,v,1,α ) = v α=v-1 log (1 -L m,n,v,1,α ) = log (1 -L m,n,v,1,v-1 ) + log (1 -L m,n,v,1,v ) .

The asymptotics are given by

L m,ρm,ν(m-1),1,ν(m-1)-1 = 2ρ m +O 1 m 2 and L m,ρm,ν(m-1),1,ν(m-1) = 2ρ m +O 1 m 2 . Thus X m,ρm,ν(m-1),1 = - 4ρ m + O 1 m 2 . (1)
In the same way, we can see that

X m,ρm,ν(m-1),2 = O 1 m 2 and X m,ρm,ν(m-1),3 = O 1 m 3 . (2)
-3 < l < (n -1) ǫ . As r m,v,l+1,α ≤ 1 and q m,l+1,α ≤ 1 -p m,l+1 ≤ 1, we have L m,n,v,l,α ≤ U m,n,l := n-1 l l(l+1) m(m-1) l . U m,n,l+1 U m,n,l = (n -l -1)(l + 2) m(m -1) l + 2 l l ≤ (n -1 -(n -1) ǫ )((n -1) ǫ + 2) m(m -1) e 2 because 0 < ǫ < 1/2 ≤ n -1 m -1 (n -1) ǫ m 1 + 2 (n -1) ǫ e 2 ≤ ρ 1+ǫ m 1-ǫ 1 + 2 1-ǫ e 2 because n ≥ 3 ≤ 3e 2 ρ 1+ǫ m 1-ǫ
It shows that at least ∀m ≥ m 0 = (3e 2 ρ 1+ǫ ) 1/(1-ǫ) , U decreases in the "l" direction. Thus for

l ≥ 4, L m,n,v,l,α ≤ U m,n,4 = n-1 4 4 4 5 4 m 4 (m-1) 4 . As U m,n,4 → 0 when m → ∞, ∃m 1 such that ∀m ≥ m 1 , L m,n,v,l,α ≤ 1/2, and so log(1 -L m,n,v,l,α ) ≥ -2L m,n,v,l,α . Then, ∀m ≥ m 1 , (n-1) ǫ -1 l=4 X m,n,v,l ≤ 2 (n-1) ǫ -1 l=4 min(v,m-l-1) α=max(0,v-l) U m,n,4 ≤ 4 4 5 4 12
ρ 4+ǫ m 3-ǫ
which means that

(n-1) ǫ -1 l=4 X m,n,l = O 1 m 3-ǫ = o 1 m 2 .
(3)

-(n -1) ǫ ≤ l ≤ n -2. As r m,v,l+1,α ≤ 1 and q m,l+1,α ≤ 1 -p m,l+1 , we have L m,n,v,l,α ≤ V m,n,l := n-1 l p l m,l+1 (1 - p m,l+1 ) n-l-1 . V m,n+1,l V m,n,l = n n -l 1 - l(l + 1) m(m -1) ≥ n n -l 1 - l(l + 1) n(n -1) = 1 + l(n 2 -n(l + 2)) n(n -1)(n -l) ≥ 1 because l ≤ n -2 It shows that V increases in the "n" direction, thus V m,n,l ≤ V m,m,l . Using √ 2πkk k e -k ≤ k! ≤ √ 2πkk k e -k e 1 12k
and m ≥ 3, we have :

m -1 l ≤ 1 √ 2π m -1 l(m -l -1) (m -1) m-1 l l (m -l -1) m-l-1 e 1 24 = e 1 24 √ 2π 1 √ m -1 1 l m-1 1 -l m-1 1 l m-1 l 1 -l m-1 m-l-1 (4)
Besides, we have

l(l + 1) m(m -1) l = l (m -1) 2l 1 + 1 l l 1 - 1 m l ≤ e l (m -1) 2l and 1 - l(l + 1) m(m -1) m-l-1 = 1 - l m -1 2 m-l-1 1 + 1 m + l -1 m-l-1 1 - 1 m m-l-1 ≤ 1 - l m -1 2 m-l-1 e (m-l-1) log (1+ 1 m+l-1 ) ≤ 1 - l m -1 2 m-l-1 e m-l-1 m+l-1 ≤ e 1 - l m -1 2 m-l-1 . Then V m,m,l ≤ e 2 e 1 24 √ 2π 1 √ m -1 1 l m-1 1 -l m-1 l m -1 l m-1 1 + l m -1 1-l m-1 m-1
We can see that

l m-1 1 -l m-1 -1
2 is maximal when l = (n -1) ǫ (at least for n sufficiently large), that is

1 l m-1 1 -l m-1 ≤ 1 (n-1) ǫ m-1 1 -(n-1) ǫ m-1 ≤ 1 (n-1) ǫ n-1 n-1 n n m m m-1 1 1 - 1 (m-1) 1-ǫ ≤ (n -1) 1 2 -ǫ 2 1 2 3 ρ 1 1 -1 √ 2 ≤ √ 6ρ -ǫ 2 (m -1) 1 2 -ǫ 2 (5)
Moreover, ∃x 0 ∈]0, 1[ such that the function x → x x (1 + x) 1-x , decreases on [0, x 0 ] and increases on ]x 0 , 1].

Thus,

l m-1 l m-1 1 + l m-1 1-l m-1
is maximal when l = (n -1) ǫ or when l = (n -2). We have :

  (n -1) ǫ m -1 (n-1) ǫ m-1 1 + (n -1) ǫ m -1 1- (n-1) ǫ m-1   m-1 = (n -1) ǫ m -1 (n-1) ǫ 1 + (n -1) ǫ m -1 (m-1)-(n-1) ǫ ≤ 1 (m -1) 1-ǫ ρ ǫ (m-1) ǫ 1 + 1 (m -1) 1-ǫ m-1 ≤ e -(m-1) ǫ ((1-ǫ)ρ ǫ log(m-1)-1) (6)
and

  (n -2) m -1 (n-2) m-1 1 + (n -2) m -1 1- (n-2) m-1   m-1 = (n -2) m -1 (n-2) 1 + (n -2) m -1 (m-1)-(n-2) ≤ 1 ρ 2 ρ n (1 + ρ)(1 + ρ) m-n ≤ 1 + ρ ρ 2 ρ ρ (1 + ρ) 1-ρ m ≤ 1 + ρ ρ 2 e m(ρ log ρ+(1-ρ) log(1+ρ)) (7)
for m sufficiently large, the case l = (n -1) ǫ dominates. Equations 5, 6 and 7 lead to

V m,m,l ≤ √ 6e 2 e 1 24
√ 2π (ρ(m -1)) -ǫ 2 e -(m-1) ǫ (ǫρ ǫ log(m-1)-1)

Thus,

n-2 l=(n-1) ǫ X m,n,v,l ≤ 2((n -2) -(n -1) ǫ + 1)(m -1) √ 6e 2 e 1 24 √ 2π (ρ(m -1)) -ǫ 2 e -(m-1) ǫ (ǫρ ǫ log(m-1)-1) ≤ 2 √ 6e 2 e 1 24 √ π ρ 1-ǫ 2 (m -1) 2-ǫ 2 e -(m-1) ǫ (ǫρ ǫ log(m-1)-1)
and finally

(n-2) l=(n-1) ǫ +1 X m,n,v,l = o 1 m 2 (8)
Pooling together equations 1, 2, 3 and 8 gives the following result : ∀ρ < 1 and ∀0 < ν < 1, when m → ∞,

P m,ρm,ν(m-1) = 1 - 4ρ m + O 1 m 2 . (9)
A.2 Case ρ < 1 and ν = 0 or 1 Firstly, we can potice that P m,n,v = P m,n,m-1-v , or equivalently P m,ρm,ν(m-1) = P m,ρm,(1-ν)(m-1) , by symmetry of the problem. Thus we only need to proove the theorem for ν = 0. Taking ν = 0 leads to

P m,n,0 = n-2 l=1 1 -(1 -r m,0,l+1,0 ) n -1 l p l m,l+1 (1 -p m,l+1 ) n-l-1 -q n-l-1 m,l+1,α .
The sum over α is reduced to α = 0, and we have X m,n,0,l = log(1 -L m,n,0,l,0 ). We cut the sum over l the same way as in the previous case.

l = 1, 2, 3. We have

L m,ρm,0,1,0 = 2ρ(1 -e -4ρ ) m + O 1 m 2 that is X m,ρm,0,1 = - 2ρ(1 -e -4ρ ) m + O 1 m 2 . ( 10
)
Besides,

X m,ρm,0,2 = O 1 m 2 X m,ρm,0,3 = O 1 m 3 (11)
-3 < l < (n -1) ǫ . Reducing the sum over α to α = 0, we can apply the result of previous section, that is :

(n-1) ǫ -1 l=4 X m,n,0,l ≤ 4 4 5 4 12 ρ 4+ǫ m 4-ǫ and (n-1) ǫ -1 l=4 X m,n,0,l = o 1 m 2 (12) -(n -1) ǫ ≤ l ≤ n -2.
The result of previous section can be used again here. Thus

(n-2) l=(n-1) ǫ X m,n,0,l ≤ 3e 2 e 1 24 √ 2π (ρ(m -1)) 1-ǫ 2 e -(m-1) ǫ (ǫρ ǫ log(m-1)-1)

and

(n-2)

l=(n-1) ǫ X m,n,0,l = o 1 m 2 (13)
Pooling together equations 10, 11, 12 and 13 gives the following result : ∀ρ < 1, when m → ∞,

P m,ρm,0 = P m,ρm,1 = 1 - 2ρ(1 -e -4ρ ) m + O 1 m 2 . ( 14
)
A.3 Case ρ = 1 and ν = 0 or 1

Here, we only need to poove the theorem for ν = 0 too. But this time, we have to cut the sum over l this way :

l = 1, 2, 3; 3 < l < (m -1) ǫ ; (m -1) ǫ ≤ l ≤ (m -1) -(m -1) ǫ , (m -1) -(m -1) ǫ < l ≤ m -2.
l = 1, 2, 3. We have

L m,m,0,1,0 = 2(1 -e -4 ) m + O 1 m 2 .
Then

X m,m,0,1 = - 2(1 -e -4 ) m + O 1 m 2 . ( 15
)
Besides,

X m,m,0,2 = O 1 m 2 X m,m,0,3 = O 1 m 3 (16)
-3 < l < (m -1) ǫ . Here, we can use the result of previous section, replacing ρ by 1, that is

(m-1) ǫ -1 l=4 X m,m,0,l ≤ 4 4 5 4 12 1 m 4-ǫ . Thus (m-1) ǫ -1 l=4 X m,m,0,l = o 1 m 2 . (17)
-(m -1) ǫ ≤ l ≤ (m -1) -(m -1) ǫ . We begin with the following equation (see section A.1) :

L m,m,0,l,0 ≤ e 2 e 1 24

√ 2π 1 √ m -1 1 l m-1 1 -l m-1 l m -1 l m-1 1 + l m -1 1-l m-1 m-1 l m-1 1 -l m-1 -1/2
is maximal when l = (m -1) ǫ and when l = (m -1) -(m -1) ǫ (by symmetry). Thus,

1 l m-1 1 -l m-1 ≤ 1 1 (m-1) 1-ǫ 1 - 1 (m-1) 1-ǫ ≤ 2(m -1) 1 2 -ǫ 2 Moreover, we have   (m -1) ǫ m -1 (m-1) ǫ m-1 1 + (m -1) ǫ m -1 1- (m-1) ǫ m-1   m-1 = 1 (m -1) 1-ǫ (m-1) ǫ 1 + 1 (m -1) 1-ǫ (m-1)-(m-1) ǫ ≤ e -(m-1) ǫ ((1-ǫ) log(m-1)-1) and   (m -1) -(m -1) ǫ m -1 (m-1)-(m-1) ǫ m-1 1 + (m -1) -(m -1) ǫ m -1 1- (m-1)-(m-1) ǫ m-1   m-1 = 1 - 1 (m-1) 1-ǫ (m-1)-(m-1) ǫ 2 - 1 (m-1) 1-ǫ (m-1) ǫ = e ((m-1)-(m-1) ǫ ) log " 1- 1 (m-1) 1-ǫ " +(m-1) ǫ log " 2- 1 (m-1) 1-ǫ " ≤ e -(m-1) ǫ (1-log 2)+ 1 2(m-1) 1-2ǫ ≤ e 1 2 e -(m-1) ǫ (1-log 2) .
Thus, at least for m sufficiently large,

L m,m,0,l,0 ≤ 2e 2 e 1 2 + 1 24 √ 2π (m -1) -ǫ 2 e -(m-1) ǫ (1-log 2)
and

(m-1)-(m-1) ǫ -1 l=(m-1) ǫ log(1 -L m,m,0,l,0 ) ≤ 4e 2 e 1 2 + 1 24 √ 2π (m -1) 1-ǫ 2 e -(m-1) ǫ (1-log 2)
and finally

(m-1)-(m-1) ǫ -1 l=(m-1) ǫ X m,m,0,l = o 1 m 2 . ( 18
L m,m,0,m-1-k,0 = 2 k e -2k k k (k -1)! 1 m + O 1 m 2 Let's set S N = N k=1 2 k e -2k k k (k-1)! and R N = ∞ k=N +1 2 k e -2k k k (k-1)! . We have 2 k e -2k k k (k -1)! ≤ 1 √ 2π √ k 2 e k Thus S N converges, and we set S = ∞ k=1 2 k e -2k k k (k-1)! ≈ 1.94264. Moreover, R N ≤ ∞ k=N +1 1 √ 2π √ k 2 e k ≤ 1 √ 2π ∞ k=N +1 k 2 e k = 1 √ 2π 2 e N +1 N 1 -2 e + 1 1 -2 e 2 Therefore R (m-1) ǫ = o 1 m . Finally, (m-1) ǫ k=1 log(1 -L m,m,0,m-1-k,0 ) = - S m + O 1 m 2 (19)
Pooling together equations 15, 16, 17, 18 and 19 gives the following result :

∀0 < ν < 1, when m → ∞, P m,m,0 = P m,m,m-1 = 1 - 2(1 -e -4 ) + S m + O 1 m 2 (20)
A.4 Case ρ = 1 and 0 < ν < 1

The argumentation is the same as the previous one.

l = 1, 2, 3. As in section A.1, replacing n by m, we have

X m,m,v,1 = log(1 -L m,m,v,1,v-1 ) + log(1 -L m,m,v,1,v ) with L m,m,ν(m-1),1,ν(m-1)-1 = 2 m + O 1 m 2 and L m,m,ν(m-1),1,ν(m-1) = 2 m + O 1 m 2 Thus, X m,m,ν(m-1),1 = - 4 m + O 1 m 2 (21)
Besides, we have

X m,m,ν(m-1),2 = O 1 m 2 and X m,m,ν(m-1),2 = O 1 m 2 (22)
-3 < l < (m -1) ǫ . We can use the results of previous section, with ρ = 1, that is

(m-1) ǫ -1 l=4 X m,m,v,l ≤ 4 4 5 4 12 1 m 3-ǫ Thus, (m-1) ǫ -1 l=4 X m,m,v,l = o 1 m 2 . ( 23
) -(m -1) ǫ ≤ l ≤ (m -1) -(m -1) ǫ .
We can use the results of previous section, with ρ = 1, that is

(m-1)-(m-1) ǫ -1 l=(m-1) ǫ X m,m,v,l ≤ 4e 2 e 1 2 + 1 24 √ 2π (m -1) 2-ǫ 2 e -(m-1) ǫ (1-log 2) thus (m-1)-(m-1) ǫ -1 l=(m-1) ǫ X m,m,v,l = o 1 m 2 (24) -(m -1) -(m -1) ǫ < l ≤ m -2. The substitution k = m -l -1 yields m-2 l=(m-1)-(m-1) ǫ min(v,m-l-1) α=max(0,v-l) log(1 -L m,m,v,l,α ) = (m-1) ǫ k=1 min(v,k) α=max(0,v-m+k+1) log(1 -L m,m,v,m-1-k,α ) As k ≤ (m -1) ǫ , we have v ≥ k ∀m ≥ 1 + ν -1 1-ǫ , and v -m + k + 1 ≤ 0 ∀m ≥ 1 + (1 -ν) -1 1-ǫ . Then m-2 l=(m-1)-(m-1) ǫ min(v,m-l-1) α=max(0,v-l) log(1 -L m,m,v,l,α ) = (m-1) ǫ k=1 k α=0 log(1 -L m,m,v,m-1-k,α ) Thus we have k = o( √ m) and α = o( √ m). Therefore L m,m,ν(m-1),m-1-k,α = 2 k e -2k k k (α + kν -2αν) mν(1 -ν)k! + O 1 m 2 and log(L m,m,ν(m-1),m-1-k,α ) = - 2 k e -2k k k (α + kν -2αν) mν(1 -ν)k! + O 1 m 2 Performing the sum over α gives k α=0 2 k e -2k k k (α + kν -2αν) mν(1 -ν)k! = 2 k e -2k k k mν(1 -ν)k! k(k + 1) 2 Let's set S ′ N = N k=1 2 k e -2k k k (k+1) (k-1)! and R ′ N = ∞ k=N +1 2 k e -2k k k (k+1) (k-1)! . We have 2 k e -2k k k (k + 1) (k -1)! ≤ 1 √ 2π √ k(k + 1) 2 e k Thus S ′ N converges, and we set S ′ = ∞ k=1 2 k e -2k k k (k+1) (k-1)! ≈ 11.9359. Moreover, R ′ N ≤ ∞ k=N +1 1 √ 2π √ k(k + 1) 2 e k ≤ 1 √ 2π ∞ k=N +1 k(k + 1) 2 e k = 1 √ 2π 2 e N +1 Q(N ) 1 -2 e where Q(N ) is a polynom of degree 2 in N . Then R ′ (m-1) ǫ = o 1 m . To conclude, m-2 l=(m-1)-(m-1) ǫ X m,m,ν(m-1),l = - S ′ 2ν(1 -ν)m + O 1 m 2 (25)
Finally, pooling together equations 21, 22, 23, 24 and 25 gives the following result : ∀0 < ν < 1, when m → ∞,

P m,m,ν(m-1) = 1 - 4 + S ′ 2ν(1-ν) m + O 1 m 2 (26) B Proof of theorem 2 We set D m,n,v,l,α (d) = (1 -r m,v,l+1,α (d)) n-1 l p l m,l+1 (d) (1 -p m,l+1 (d)) n-l-1 -q n-l-1 m,l,α (d) . Notice that for l < d -1, p m,l+1 (d) = 0. Thus, P m,n,v (d) = n-2 l=d-1 min(v,m-l-1) α=max(0,v-l) (1 -D m,n,v,l,α (d)) = exp   n-2 l=d-1 min(v,m-l-1) α=max(0,v-l) log (1 -D m,n,v,l,α (d))   We also define X m,n,v,l (d) = min(v,m-l-1) α=max(0,v-l) log (1 -D m,n,v,l,α (d)), such that P m,n,v (d) = exp n-2 l=d-1 X m,n,v,l (d) .
Let's set ρ = n/m, ν = v/(m -1) and µ = d/m. We have 0 < ρ ≤ 1, 0 ≤ ν ≤ 1 and 0 < µ ≤ 1. We distinguish the 3 cases : ν = 0 or ν = 1 or µ ≥ ρ ; 0 < ρ < 1 and 0 < ν < 1 ; ρ = 1 and 0 < ν < 1. We may use some results obtained in the proof of theorem 2.

B.1 ν = 0 or ν = 1 or µ ≥ ρ As P m,n,v (d) = P m,n,m-1-v (d), we only need to proove the result for v = 0, that is ν = 0. We have

P m,n,0 (d) = n-2 l=d-1 1 -(1 -r m,0,l+1,0 (d)) n -1 l p l m,l+1 (d) (1 -p m,l+1 ) n-l-1 -q n-l-1 m,l+1,0
with r m,0,l+1,0 (d) = min(0,l+1-d)-max(0,-d+1)+1 min(0,m-d)-max(0,-d+1)+1 . We have d ≥ 1, m ≥ d and l + 1 > d, thus all the min and max equal 0, that is r m,0,l+1,0

(d) = 1. Therefore, ∀0 < ρ ≤ 1 et ∀0 < µ ≤ 1, P m,ρm,0 (µm) = P m,ρm,m-1 (µm) = 1 (27)
The case µ ≥ ρ is trivial : the product over l goes from d -1 to n -2. Then, if d ≥ n, the product is reduced to 1. Thus, ∀µ ≥ ρ, P m,ρm,ν(m-1) (µm) = 1 (28)

B.2 0 < ρ < 1 and 0 < ν < 1

As r m,v,l+1,α ≤ 1 and q m,l+1,α ≤ 1p l+1,m , we have We have

W m,n+1,l (d) W m,n,l (d) = n n -l 1 - l -d + 2 m -d + 1 = n n -l m -l -1 m -d + 1
We can see that We have

q m,m-k,α (d) = max 0, α -d + 1 m -d + 1 + max 0, k -α -d -1 m -d + 1

Definition 1 .

 1 Let I ⋐ E. Let K I be the set of variables for which the domains are subintervals of I, K I = {i, D i ⋐ I}. I is a Hall interval if and only if |K I | = |I|.

( 1 )

 1 D n I • , (2) there are exactly |I • | -1 domains included in I • and at least one other domain is neither included in, nor outside I • .

  but by the BC of the problem before the instantiation, 2. (prop. 1) holds. Otherwise, |K I • | < |I • |, then |K I ⊗ | < |I ⊗ | and 1. (prop. 1) holds. If D n I • , we have |I ⊗ | = |I • | -1 and |K I ⊗ | = |K I • |, and by BC,

Fig. 1 .

 1 Fig.1. When a variable (here Vn, on the left) is assigned to a value x (here x = 2, on the right), new Hall intervals may appear (here, the interval {0, 1, 3} on the right). In this case, an alldifferent that was BC before the instantiation becomes inconsistent (here, domain D1 should be reduced to {4..7}). Such pre-Hall intervals (here, on the left, interval {0, 1, 2, 3}) are described in Proposition 2.

Definition 3 .

 3 A probability distribution is a function P from P(Ω) to [0, 1], such that P[Ω] = 1, and for any two mutually exclusive events A, B ⊂ Ω, P[A∪B] = P[A]+P[B]. The triplet (Ω, P(Ω), P) is called a probability space.

  r m,v,l,α = m P d=2 P[(Di⋐I∧x∈Di)|(|Di|=d)]P[|Di|=d] m P d=2 P[x∈Di|(|Di|=d)]P[|Di|=d]

  thus only domains of size d are kept.

Fig. 3 .

 3 Fig.3. The asymptotic expansions of theorem 2, for ρ = 1. On the left, µ = 0.4, and on the right, µ = 0.6. The plain curves are for m = 50 (resp 500), the large dashed curves for m = 100 (resp 1000) and the small dashed curves for m = 500 (resp 5000).

1 (

 1 a) Uniform model with m = 100. On the left, ρ varies, and ν = 0.4. On the right, ν varies, and ρ = 0.8. Ρm,Ν m 1 Μm (b) Fixed size uniform model. On the left, m = 100, ρ varies, ν = 0.4, and µ = 0.5. On the right, m = 500, ν varies, ρ = 1 and µ = 0.6. ∆P/P represents the relative difference between theoretical and measured probabilities. On the left, uniform model with ρ = 0.7 and ν = 0.3. On the right, fixed-size model with ρ = 1, ν = 0.4 and µ = 0.6.

Fig. 4 .

 4 Fig. 4. Theoretical (plain curves) and measured (dotted plots) probabilities

)-(m - 1 )

 1 -(m -1) ǫ < l ≤ m -2. The substitution k = m -1l yields : m-2 l=(m-1)-(m-1) ǫ X m,m,0,l = (m-1) ǫ k=1 X m,m,0,lThus, we have k = o( √ m), and then

D

  m,n,v,l,α (d) ≤ W m,n,l (d) := n -1 l p l m,l+1 (d) (1p m,l+1 (d)) n-l-1 .

W 1 ≥ 1 Thus, 1 - 1 / 2 is 3 2 3 2l 1 Xlog( 1 -log( 1 -

 1111233111 m,n+1,l (d) W m,n,l(d) decreases with l. Therefore,W m,n+1,l (d) W m,n,l (d) ≥ W m,n+1,d-1 (d) W m,n,d-1 (d) = n nd + 1 md md + 1 = 1 + (d -1)(md + 1) -(nd + 1) (nd + 1)(md + 1) ≥ 1 + mn (nd + 1)(md + 1)because d -1 ≥ W increases with n, and is bounded by W m,m,l (d). Then we haveD m,n,v,l,α (d) ≤ W m,n,l (d) = m -1 l p l m,l+1 (d) (1p m,l+1 (d)) maximal when l = d -1 or l = n -D m,n,v,l,α (d) ≤ e C µ,ρ 1 √ m -1 e -(m-1)(ρ log( ρ ρ-µ )+log(1-µ)) Thus, C µ,ρ (m -1) e -(m-1)(ρ log( ρ ρ-µ )+log(1-µ))and finally, ∀0 < µ < ρ < 1,P m,ρm,ν(m-1) (µm) ≥ 1 -C µ,ρ (m -1) e -(m-1)(ρ log( ρ ρ-µ )+log(1-µ))(29)in particularP m,ρm,ν(m-1) (µm) = o 1 m 2(30)B.3 ρ = 1 and 0 < ν < 1Let 0 < ǫ < 1/2. We cut the sum over l as follows :d -1 ≤ l < (m -1) -(m -1) ǫ and (m -1) -(m -1) ǫ ≤ l ≤ m -2. -d -1 ≤ l < (m -1) -(m -1) ǫ .From the previous section, we haveD m,m,v,l,α (d) increases with l. Thus, l < (m -1) -(m -1) ǫ ) implies 1 -1)-(m-1) ǫ = e ((m-1)-(m-1) ǫ ) log(1-(m-1)(d-2) m((m-1)-(m-1) ǫ ) ) = e ((m-1)-(m-1) ǫ ) log(1-µ(1-2 µm ) m-1)-(m-1) ǫ ) log(1-µ))-(m-1) ǫ 1) 2-ǫ 2 e -(m-1) ǫ (log(1-µ)+ 1 1-µ )and finally(m-1)-(m-1) ǫ l=d-m,m,v,l (d) = o 1 m 2 (31) -(m -1) -(m -1) ǫ ≤ l ≤ m -2. The substitution k = m -1l yields, for m sufficiently large, D m,m,v,l,α (d)) = D m,m,v,m-1-k,α (d))

As α ≤ k ≤ (m -1) ǫ and kα ≤ k ≤ (m -1) ǫ , there exists m ǫ such that ∀m ≥ m ǫ , q m,m-k,α (µm) = 0. In addition, we have r m,v,m-k,α (d) = min(v, m + αkd)max(α, vd + 1) + 1 min(v, md)max(0, vd + 1) + 1 The denominator is written in terms of ν and µ as min(ν(m -1), mµm)max(0, ν(m -1)µm + 1) + 1. We can see that for m sufficiently large, min(ν(m -1), mµm)max(0, ν(m -1)µm + 1) + 1 = mΦ νµ + χ νµ where Φ νµ = min(ν, 1µ)max(0, νµ), and

In the same way, as α ≤ k ≤ (m -1) ǫ and kα ≤ k ≤ (m -1) ǫ , there exists m sufficiently large suche that

In addition, we have

It yields

2

kν. We also have

(k-1)! . Thoses 2 series converge ∀0 < µ < 1, and their remainder term equal o 1 m . We denote the limits

Finally, we set (33)