text:
# Probability of getting $4$ smallest Balls in $2$ Boxes

I have $2n$ balls labeled $1, 2, \ldots, 2n$, and two boxes, Box $1$ and Box $2$. I take $n$ of the balls at random without replacement and place them in the Box $1$. I take the remaining $n$ balls and place them in the Box $2$. I take the two smallest-numbered balls from each box. What is the probability that I end up with balls $1, 2, 3$ and $4$?

I'm trying this for small values of $n$ but am struggling to see the pattern. It is the probability $$1-P(\text{any 3 of balls 1,2,3,4 in the same box})-P(\text{all balls 1,2,3,4 in same box}) .$$ I'm having trouble finding the formula form here. Thanks!

Ok this part is more complicated. I have 3n balls and 3 boxes. I take n of the balls at random w/out replacement and place them in Box 1. I take n of the remaining 2n balls at random w/out replacement and put them in Box 2. I take the remaining n balls and put them in Box 3. I then take the smallest-numbered ball from each box and then the smallest-numbered ball among the balls remaining. What is the probability that I end up with balls 1,2,3,4?

So this time, it is okay to have two of Balls 1,2,3,4 in the one of boxes because he will take the smallest and come back for the next smallest. So I'm thinking that it is $\binom{4}{3}$ * ($\binom{3}{1}$$\binom{3n-3}{n-1})/\binom{3n}{n} *(\binom{2}{1}$$\binom{2n-2}{n-1}$)/$\binom{2n}{n}$

I'm not sure if I need that first factor of $\binom{4}{3}$ though. Thanks!

-
Your analysis is right. The probability of a two-two split is (somewhat) easier to get at directly than via the "complement" method that you suggest, but that will work too. – André Nicolas Oct 5 '11 at 8:30

Edit: Initially, we left out some details, since the question was homework. Now that time has passed, we add a few lines to give a complete answer.

When we take the two "smallest" balls from each box, we get the set $\{1,2,3,4\}$ precisely if $2$ of the $4$ smallest balls are in Box 1 (and therefore the other $2$ are in Box 2). So we need to find the probability that exactly $2$ of the $4$ smallest balls are in Box 1.

In deciding which balls go into Box 1, we have $\binom{2n}{n}$ choices. The problem specifies that these are all equally likely.

Now we count the number of choices in which exactly $2$ of our $4$ smallest balls end up in Box 1. Which $2$ of these $4$ will it be? These $2$ balls can be chosen from the $4$ in $\binom{4}{2}$ ways. For each way of deciding which of the $4$ smallest balls Box 1 will have, the remaining balls for Box 1 can be chosen in $\binom{2n-4}{n-2}$ ways.

Thus the number of "good" ways to choose the balls in Box 1 is equal to $\binom{4}{2}\binom{2n-4}{n-2}$. It follows that the required probability is $$\frac{\binom{4}{2}\binom{2n-4}{n-2}}{\binom{2n}{n}}.$$

After obtaining the above expression for the probability, we may want to "simplify." Or not. There is a lot of cancellation, since $(2n)!=(2n)(2n-1)(2n-2)(2n-30(2n-4)!$ and $n!=n(n-1)(n-2)!$. We end up with the following expression for the probability: $$\frac{3n(n-1)}{2(2n-1)(2n-3)}.$$

Comment: When I first read the problem, I thought that after the initial assignment of balls to Box 1 and Box 2, $2$ balls are chosen at random from each box, and we want the probability these give us the set $\{1,2,3,4\}$. That modified problem is not hard to solve once we have solved the original problem.

-
any comments as to my solution is right or wrong @nicolas ? – Bhargav Oct 5 '11 at 7:56
@168335: When $n=2$ the probability is clearly $1$. That is not what your formula gives. – André Nicolas Oct 5 '11 at 8:11
Thank you! This makes total sense. It is much simpler than my complement analysis! – caligirl11 Oct 6 '11 at 4:50
You could use the same idea to find the probability none of the $4$ is in Box 1 (which is same as probability all $4$ are) and also the probability exactly one is in Box 1 (which is same as probability three are). The various expressions will have similar shape to my probability of exactly two, with minor differences of detail. Then you can add up, subtract from $1$. Same idea, more work. – André Nicolas Oct 6 '11 at 5:04
There is another part that I added that is more tricky. – caligirl11 Oct 6 '11 at 17:13


text:
# taylor approximation

• August 14th 2009, 04:48 AM
chogo
taylor approximation
Hi

i am sorry if this is a stupid question but

is there a taylor approximation to the function

f = $ln(1-e^{-x})$

thanks
• August 14th 2009, 05:15 AM
Twig
Yes
• August 14th 2009, 05:24 AM
chogo
but

$ln(1-e^{-x}) = f(a) + f'(a)(x-a) +.....$

the first term $f(a)$ is $ln(0)$ which is undefined
• August 14th 2009, 06:15 AM
justchillin
Then try centering the series on something other than 0.

format: plain


text:
# P3500 [POI2010]TES-Intelligence Test

• 165通过
• 317提交
• 题目提供者 洛谷
• 评测方式 云端评测
• 标签 模拟 POI 2010 高性能
• 难度 提高+/省选-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

One of the tasks in the Byteotian Intelligence Test (BIT) is to cross out numbers from an initial sequence in such a way that leaves as a result certain given sequences.

Byteasar longs to become the IQ Master of Byteotia, but he is no good in this kind of tasks.

But since practice makes perfect, he intends to practise a lot.

So much in fact that he asks you to write a program that will facilitate the training by verifying his answers quickly.

Byteotian智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Byteasar很渴望成为Byteotian智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。

## 输入输出格式

输入格式：

The first line of the standard input contains one integer $m$ ($1\le m\le 1\ 000\ 000$).

The second line holds $m$ integers $a_1,a_2,\cdots,a_m$ ($1\le a_i\le 1\ 000\ 000$ for $1\le i\le m$), separated by single spaces, that constitute the initial sequence of the test.

The third line of the input holds one integer $n$.

The following $2n$ lines describe the sequences to be obtained by crossing out numbers from the initial sequence.

Each sequence's description takes two successive lines.

The first of these two lines contains an integer $m_i$ ($1\le m_i\le 1\ 000\ 000$).

The second contains an $m_i$-element long sequence of integers $b_{i,1},b_{i,2},\cdots,b_{i,m_i}$($1\le b_{i,j}\le 1\ 000\ 000$ for $1\le j\le m_i$)separated by single spaces. You may assume that the total length on given $n$ sequences does not exceed $1\ 000\ 000$.

第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=1000000），表示n个Byteasar经过一系列删除得到的序列，每个序列两行，第一行给出长度L（1<=L<=m），然后下一行为L个由空格分开的整数bi（1<=bi<=1000000）。

输出格式：

Your program should print out $n$ lines to the standard output.

The $i$-th line (for $1\le i\le n$) should hold one word, "TAK" (yes in Polish) if the $i$-th input sequence can be obtained by crossing out (i.e., removing) some, not necessarily contiguous, numbers from the initial sequence, or "NIE" (no in Polish) otherwise. Mind you, only the words should be printed, no quotation marks. Of course, the order of the numbers left after crossing out is important, as can be seen in the example.

共n行，如果Byteasar的序列确实是由最初的序列删除一些数得到，就输出TAK，否则输出NIE。

## 输入输出样例

输入样例#1： 复制
7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4
输出样例#1： 复制
TAK
NIE
TAK
NIE

## 说明

题目简述：给定一个数串，和m个小数串，问这些小串都是不是大数字串的子序列

感谢@Yhy9630 提供翻译

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。


text:
Home » Maths for Planet Earth » Profiting from Reforestation

# Profiting from Reforestation

A small company is planting trees in areas of the Amazon rainforest that have been affected by forest fires.

On any day, the cost to the company, $y, of planting x trees is modelled to be the sum of two elements: • a fixed cost • a cost that is proportional to the number of trees planted that day a) Write down a general equation linking y with x for this model. [2 marks] The company is subsidised$2 by the government for each tree planted.

On a day when 80,000 trees are planted, the company makes a profit of £500

On a day when 30,000 trees are planted, the company makes a loss of £80

Using the above information,

b) Show that $$y = 0.84x + 428$$

[3 marks]

c) With reference to the model, interpret the significance of the value 0.84 in the equation.

[1 mark]

d) Find the least number of trees that must be planted on any given day for the company to make a profit that day.

[3 marks]

## More Maths for Planet Earth

GCSE
##### Climate Striking Students
The pie chart shows information about students going to a ‘Fridays for Future’ climate strike. 3360 more female students went to the strike than
GCSE
##### A Changing Transport System
Cars and transport, and the gases and particulates that they emit from their exhausts have a serious effect on the environment and on human
A Level
##### A Carbon Negative Company
A small company’s carbon dioxide (CO₂) emissions since 2000 can be modelled using the parametric equations [12x = t, y = 8t – 4.9t^{2}
GCSE
##### Trucking Company’s Carbon Increase
Jean owns a trucking company (with ten trucks) which produces 1062.8 tonnes of carbon dioxide in the year 2015. The company’s carbon emissions increase


text:
Journal article

Cosmological Constraints on Perturbative Supersymmetry Breaking

Abstract:

We discuss the cosmology of string models with perturbative supersymmetry breaking at a scale of ${\cal O}$(TeV). Such models exhibit Kaluza-Klein like spectra and contain unstable massive gravitinos/gravitons. We find that considerations of primordial nucleosynthesis constrain the maximum temperature following inflation to be not much larger than the supersymmetry breaking scale. This imposes conflicting requirements on the scalar field driving inflation, making it rather difficult to constr...

Publication status:
Published

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Physics
Sub department:
Theoretical Physics
Role:
Author
Journal:
Phys.Lett.B
Volume:
342
Issue:
1-4
Pages:
40-46
Publication date:
1994-09-19
DOI:
ISSN:
0370-2693
Language:
English
Keywords:
Pubs id:
pubs:180133
UUID:
uuid:39193218-c10e-4b21-b92d-dc8709c718ab
Local pid:
pubs:180133
Source identifiers:
180133
Deposit date:
2012-12-19

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP


text:
# Factors And Factorials

Let $$42 ^ {N}$$ be the highest power of 42 that divides $$1000!$$. What is the value of $$N$$?

×


text:
## A macro to automate the creation of indicator variables in SAS

In a recent blog post, I introduced an easy and efficient way to create indicator variables from categorical variables in SAS.  This method pretends to run logistic regression, but it really is using PROC LOGISTIC to get the design matrix based on dummy-variable coding.  I shared SAS code for how to do so, step-by-step.

I write this follow-up post to provide a macro that you can use to execute all of those steps in one line.  If you have not read my previous post on this topic, then I strongly encourage you to do that first.  Don’t use this macro blindly.

Here is the macro.  The key steps are

1. Run PROC LOGISTIC to get the design matrix (which has the indicator variables)
2. Merge the original data with the newly created indicator variables
3. Delete the “INDICATORS” data set, which was created in an intermediate step
%macro create_indicators(input_data, target, covariates, output_data);

proc logistic
data = &input_data
noprint
outdesign = indicators;
class &covariates / param = glm;
model &target = &covariates;
run;

data &output_data;
merge    &input_data
indicators (drop = Intercept &target);
run;

proc datasets
library = work
noprint;
delete indicators;
run;

%mend;

I will use the built-in data set SASHELP.CARS to illustrate the use of my macro.  As you can see, my macro can accept multiple categorical variables as inputs for creating indicator variables.  I will do that here for the variables TYPE, MAKE, and ORIGIN.

## An easy and efficient way to create indicator variables (a.k.a. dummy variables) from a categorical variable in SAS

#### Introduction

In statistics and biostatistics, the creation of binary indicators is a very useful practice.

• They can be useful predictor variables in statistical models.
• They can reduce the amount of memory required to store the data set.
• They can treat a categorical covariate as a continuous covariate in regression, which has certain mathematical conveniences.

However, the creation of indicator variables can be a long, tedious, and error-prone process.  This is especially true if there are many categorical variables, or if a categorical variable has many categories.  In this tutorial, I will show an easy and efficient way to create indicator variables in SAS.  I learned this technique from SAS usage note #23217: Saving the coded design matrix of a model to a data set.

#### The Example Data Set

Let’s consider the PRDSAL2 data set that is built into the SASHELP library.  Here are the first 5 observations; due to a width constraint, I will show the first 5 columns and the last 6 columns separately.  (I encourage you to view this data set using PROC PRINT in SAS by yourself.)

COUNTRY STATE COUNTY ACTUAL PREDICT
U.S.A. California $987.36$692.24
U.S.A. California $1,782.96$568.48
U.S.A. California $32.64$16.32
U.S.A. California $1,825.12$756.16
U.S.A. California $750.72$723.52

PRODTYPE PRODUCT YEAR QUARTER MONTH MONYR
FURNITURE SOFA 1995 1 Jan JAN95
FURNITURE SOFA 1995 1 Feb FEB95
FURNITURE SOFA 1995 1 Mar MAR95
FURNITURE SOFA 1995 2 Apr APR95
FURNITURE SOFA 1995 2 May MAY95

## Use the LENGTH statement to pre-set the lengths of character variables in SAS – with a comparison to R

I often create character variables (i.e. variables with strings of text as their values) in SAS, and they sometimes don’t render as expected.  Here is an example involving the built-in data set SASHELP.CLASS.

Here is the code:

data c1;
set sashelp.class;

* define a new character variable to classify someone as tall or short;
if height > 60
then height_class = 'Tall';
else height_class = 'Short';
run;

* print the results for the first 5 rows;
proc print
data = c1 (obs = 5);
run;

Here is the result:

Obs Name Sex Age Height Weight height_class
1 Alfred M 14 69.0 112.5 Tall
2 Alice F 13 56.5 84.0 Shor
3 Barbara F 13 65.3 98.0 Tall
4 Carol F 14 62.8 102.5 Tall
5 Henry M 14 63.5 102.5 Tall

What happened?  Why does the word “Short” render as “Shor”?

## Odds and Probability: Commonly Misused Terms in Statistics – An Illustrative Example in Baseball

Yesterday, all 15 home teams in Major League Baseball won on the same day – the first such occurrence in history.  CTV News published an article written by Mike Fitzpatrick from The Associated Press that reported on this event.  The article states, “Viewing every game as a 50-50 proposition independent of all others, STATS figured the odds of a home sweep on a night with a full major league schedule was 1 in 32,768.”  (Emphases added)

Screenshot captured at 5:35 pm Vancouver time on Wednesday, August 12, 2015.

Out of curiosity, I wanted to reproduce this result.  This event is an intersection of 15 independent Bernoulli random variables, all with the probability of the home team winning being 0.5.

$P[(\text{Winner}_1 = \text{Home Team}_1) \cap (\text{Winner}_2 = \text{Home Team}_2) \cap \ldots \cap (\text{Winner}_{15}= \text{Home Team}_{15})]$

Since all 15 games are assumed to be mutually independent, the probability of all 15 home teams winning is just

$P(\text{All 15 Home Teams Win}) = \prod_{n = 1}^{15} P(\text{Winner}_i = \text{Home Team}_i)$

$P(\text{All 15 Home Teams Win}) = 0.5^{15} = 0.00003051757$

Now, let’s connect this probability to odds.

It is important to note that

• odds is only applicable to Bernoulli random variables (i.e. binary events)
• odds is the ratio of the probability of success to the probability of failure

For our example,

$\text{Odds}(\text{All 15 Home Teams Win}) = P(\text{All 15 Home Teams Win}) \ \div \ P(\text{At least 1 Home Team Loses})$

$\text{Odds}(\text{All 15 Home Teams Win}) = 0.00003051757 \div (1 - 0.00003051757)$

$\text{Odds}(\text{All 15 Home Teams Win}) = 0.0000305185$

The above article states that the odds is 1 in 32,768.  The fraction 1/32768 is equal to 0.00003051757, which is NOT the odds as I just calculated.  Instead, 0.00003051757 is the probability of all 15 home teams winning.  Thus, the article incorrectly states 0.00003051757 as the odds rather than the probability.

This is an example of a common confusion between probability and odds that the media and the general public often make.  Probability and odds are two different concepts and are calculated differently, and my calculations above illustrate their differences.  Thus, exercise caution when reading statements about probability and odds, and make sure that the communicator of such statements knows exactly how they are calculated and which one is more applicable.

## The advantages of using count() to get N-way frequency tables as data frames in R

#### Introduction

I recently introduced how to use the count() function in the “plyr” package in R to produce 1-way frequency tables in R.  Several commenters provided alternative ways of doing so, and they are all appreciated.  Today, I want to extend that tutorial by demonstrating how count() can be used to produce N-way frequency tables in the list format – this will magnify the superiority of this function over other functions like table() and xtabs().

#### 2-Way Frequencies: The Cross-Tabulated Format vs. The List-Format

To get a 2-way frequency table (i.e. a frequency table of the counts of a data set as divided by 2 categorical variables), you can display it in a cross-tabulated format or in a list format.

In R, the xtabs() function is good for cross-tabulation.  Let’s use the “mtcars” data set again; recall that it is a built-in data set in Base R.

> y = xtabs(~ cyl + gear, mtcars)
> y
gear
cyl      3     4     5
4        1     8     2
6        2     4     1
8        12    0     2

## How to Get the Frequency Table of a Categorical Variable as a Data Frame in R

#### Introduction

One feature that I like about R is the ability to access and manipulate the outputs of many functions.  For example, you can extract the kernel density estimates from density() and scale them to ensure that the resulting density integrates to 1 over its support set.

I recently needed to get a frequency table of a categorical variable in R, and I wanted the output as a data table that I can access and manipulate.  This is a fairly simple and common task in statistics and data analysis, so I thought that there must be a function in Base R that can easily generate this.  Sadly, I could not find such a function.  In this post, I will explain why the seemingly obvious table() function does not work, and I will demonstrate how the count() function in the ‘plyr’ package can achieve this goal.

#### The Example Data Set – mtcars

Let’s use the mtcars data set that is built into R as an example.  The categorical variable that I want to explore is “gear” – this denotes the number of forward gears in the car – so let’s view the first 6 observations of just the car model and the gear.  We can use the subset() function to restrict the data set to show just the row names and “gear”.

> head(subset(mtcars, select = 'gear'))
gear
Mazda RX4            4
Mazda RX4 Wag        4
Datsun 710           4
Hornet 4 Drive       3
Valiant              3

## Performing Logistic Regression in R and SAS

#### Introduction

My statistics education focused a lot on normal linear least-squares regression, and I was even told by a professor in an introductory statistics class that 95% of statistical consulting can be done with knowledge learned up to and including a course in linear regression.  Unfortunately, that advice has turned out to vastly underestimate the variety and depth of problems that I have encountered in statistical consulting, and the emphasis on linear regression has not paid dividends in my statistics career so far.  Wisdom from veteran statisticians and my own experience combine to suggest that logistic regression is actually much more commonly used in industry than linear regression.  I have already started a series of short lessons on binary classification in my Statistics Lesson of the Day and Machine Learning Lesson of the Day.    In this post, I will show how to perform logistic regression in both R and SAS.  I will discuss how to interpret the results in a later post.

#### The Data Set

The data set that I will use is slightly modified from Michael Brannick’s web page that explains logistic regression.  I copied and pasted the data from his web page into Excel, modified the data to create a new data set, then saved it as an Excel spreadsheet called heart attack.xlsx.

This data set has 3 variables (I have renamed them for convenience in my R programming).

1. ha2  – Whether or not a patient had a second heart attack.  If ha2 = 1, then the patient had a second heart attack; otherwise, if ha2 = 0, then the patient did not have a second heart attack.  This is the response variable.
2. treatment – Whether or not the patient completed an anger control treatment program.
3. anxiety – A continuous variable that scores the patient’s anxiety level.  A higher score denotes higher anxiety.

Read the rest of this post to get the full scripts and view the full outputs of this logistic regression model in both R and SAS!

## The Chi-Squared Test of Independence – An Example in Both R and SAS

#### Introduction

The chi-squared test of independence is one of the most basic and common hypothesis tests in the statistical analysis of categorical data.  Given 2 categorical random variables, $X$ and $Y$, the chi-squared test of independence determines whether or not there exists a statistical dependence between them.  Formally, it is a hypothesis test with the following null and alternative hypotheses:

$H_0: X \perp Y \ \ \ \ \ \text{vs.} \ \ \ \ \ H_a: X \not \perp Y$

If you’re not familiar with probabilistic independence and how it manifests in categorical random variables, watch my video on calculating expected counts in contingency tables using joint and marginal probabilities.  For your convenience, here is another video that gives a gentler and more practical understanding of calculating expected counts using marginal proportions and marginal totals.

Today, I will continue from those 2 videos and illustrate how the chi-squared test of independence can be implemented in both R and SAS with the same example.

## Machine Learning and Applied Statistics Lesson of the Day – Positive Predictive Value and Negative Predictive Value

For a binary classifier,

• its positive predictive value (PPV) is the proportion of positively classified cases that were truly positive.

$\text{PPV} = \text{(Number of True Positives)} \ \div \ \text{(Number of True Positives} \ + \ \text{Number of False Positives)}$

• its negative predictive value (NPV) is the proportion of negatively classified cases that were truly negative.

$\text{NPV} = \text{(Number of True Negatives)} \ \div \ \text{(Number of True Negatives} \ + \ \text{Number of False Negatives)}$

In a later Statistics and Machine Learning Lesson of the Day, I will discuss the differences between PPV/NPV and sensitivity/specificity in assessing the predictive accuracy of a binary classifier.

(Recall that sensitivity and specificity can also be used to evaluate the performance of a binary classifier.  Based on those 2 statistics, we can construct receiver operating characteristic (ROC) curves to assess the predictive accuracy of the classifier, and a minimum standard for a good ROC curve is being better than the line of no discrimination.)

## Video Tutorial – Calculating Expected Counts in a Contingency Table Using Joint Probabilities

In an earlier video, I showed how to calculate expected counts in a contingency table using marginal proportions and totals.  (Recall that expected counts are needed to conduct hypothesis tests of independence between categorical random variables.)  Today, I want to share a second video of calculating expected counts – this time, using joint probabilities.  This method uses the definition of independence between 2 random variables to form estimators of the joint probabilities for each cell in the contingency table.  Once the joint probabilities are estimated, the expected counts are simply the joint probabilities multipled by the grand total of the entire sample.  This method gives a more direct and deeper connection between the null hypothesis of a test of independence and the calculation of expected counts.

I encourage you to watch both of my videos on expected counts in my YouTube channel to gain a deeper understanding of how and why they can be calculated.  Please note that the expected counts are slightly different in the 2 videos due to round-off error; if you want to be convinced about this, I encourage you to do the calculations in the 2 different orders as I presented in the 2 videos – you will eventually see where the differences arise.

## Video Tutorial – Calculating Expected Counts in Contingency Tables Using Marginal Proportions and Marginal Totals

A common task in statistics and biostatistics is performing hypothesis tests of independence between 2 categorical random variables.  The data for such tests are best organized in contingency tables, which allow expected counts to be calculated easily.  In this video tutorial in my Youtube channel, I demonstrate how to calculate expected counts using marginal proportions and marginal totals.  In a later video, I will introduce a second method for calculating expected counts using joint probabilities and marginal probabilities.

In a later tutorial, I will illustrate how to implement the chi-squared test of independence on the same data set in R and SAS – stay tuned!


text:
# Dhalion: self-regulating stream processing in Heron

Dhalion: Self-regulating stream processing in Heron Floratou et al., VLDB 2017

Dhalion follows on nicely from yesterday’s paper looking at the modular architecture of Heron, and aims to reduce the “complexity of configuring, managing, and deploying” streaming applications. In particular, streaming applications deployed as Heron topologies, although the authors are keen to point out the principles could be applied in other engines too.

Dhalion is a system that essentially allows stream processing frameworks to become self-regulating. Dhalion has been implemented and evaluated on top of Twitter Heron and we are in the process of releasing it to open-source as a contributed to the Heron code base. However, its architecture and basic abstractions are also applicable to other streaming engines as well.

And does self-regulating mean exactly? Floratou et al. break it down into three components:

• The system should be able to self-tune: given a topology and a desired SLO, it should be able to automatically tune configuration parameters to achieve the stated objective.
• The system should then be able to self-stabilise to continue to maintain that SLO in the face of changing workload (e.g., a sudden surge of tweets). (This functionality is more commonly referred to as auto-scaling).
• The system should be able to detect service degradations (gray failures?), diagnose the internal faults causing them, and take actions to recover from them. (Self-healing).

Let’s pause for a moment and think about what might be necessary to achieve those goals. Clearly there has to be some kind of monitoring to observe the system status (perhaps from multiple perspectives), with alerts/events generated when an abnormal situation is detected or SLOs are not being met. Then we’ll need a way to map from alert conditions back to causes, and finally given a determined cause or cause(s) we’ll need a way to take corrective action to address the situation. While we’re doing all this, we’ll need to be careful about feedback loops too in case our interventions themselves cause the system to become unstable or to oscillate between configurations degrading performance.

The first three of those requirements are satisfied by Dhalion’s symptom detectors, diagnosers, and resolvers. Dhalion has only rudimentary mechanisms to control feedback though: actions shown not to help can be blacklisted (“if it hurts, stop doing it!”), and after taking an action, the system waits for a reasonable period of time before considering any further interventions. In the evaluation, these two measures seem to be enough to exhibit desirable behaviours, but it would have been nice to have some reference to control theory, which is a whole branch of science dedicated to achieving stability around a setpoint.

Symptom detectors collect metrics from the underlying streaming system (for example, tuple processing rates, and number of packets pending). From these metrics Dhalion looks for symptoms that may be evidence of a problem – for example, is the system having to apply backpressure, or is there processing skew across the tasks of a particular pipeline stage? A symptom description contains a compact representation of the symptom together with the metric values used to identify it.

Detected symptoms are passed to the diagnosers which seek to find explanations for the symptoms. Such

For example, the existence of backpressure can be attributed to various reasons such as resource underprovisioning at a particular stage, slow hosts/machines or data skew. Dhalion produces all the possible diagnoses that can explain the observed symptoms.

In the examples given in the paper, the diagnosers all look to be hand-coded rules, but you could in theory plug in machine learned classifiers or other such trickery.

Given a set of (possible) diagnoses, resolver selection explores possible actions to resolve the situation, which are then carried out by the resolvers. Typically there is a one-to-one mapping between diagnoses and resolvers. Major topology changes such as scaling up and down resources or restarting containers are typically invoked through the Heron Scheduler component.

… after every action is performed, Dhalion evaluates whether the action was able to resolve the problem or brought the system to a healthier state. If an action does not produce the expected outcome then it is blacklisted and it is not repeated again.

(Strictly, Dhalion tracks the ratio of unsuccessful interventions to invocations for a given action and diagnosis, and blacklists the action for that diagnosis when the ratio crosses a given threshold).

Let’s see how this all comes together for a couple of use cases: dynamic resource provisioning, and SLO maintenance.

### Dynamic resource provisioning (autoscaling)

The Dhalion Dynamic Resource Provisioning Policy tries to maximise throughput while also avoiding under-utilisation. There are three different symptom detectors, four diagnosers, and four possible resolution.

#### Detectors

• The pending packets detector monitors the number of pending packets in Heron instance queues for bolts. It looks to see whether all of the instances have a similar queue size or whether there are outliers.
• The backpressure detector generates a symptom description whenever backpressure is being applied. This description includes the bolt that is the source of the backpressure and the amount of time input data consumption was suspended during the 300 second measurement period.
• The processing rate skew detector looks for mismatches in the number of tuples processed by each Heron instance.

#### Diagnosers.

• The resource overprovisioning diagnoser looks at the symptoms from the pending packets and backpressure detectors and considers. If there is no backpressure and the average number of pending packets across instances of a bolt is almost zero, then it is possible the resources assigned to the bolt are over-provisioned.
• The resource underprovisioning diagnoser considers whether observed backpressure could be the result of of underprovisioned resources. It attributes the cause when all the instances of a bolt have similar processing rates and queue sizes.
• The slow instance diagnoser attributes observed backpressure to a slow instance when the instances initiating backpressure have a much higher number of pending packets than their peers and the similar processing rates. (The processing rates are similar because all instances operate at the speed of the slow instance).
• The data skew diagnoser attributes observed backpressure to data skew when the instances initiating backpressure have a higher processing rate and a higher number of pending packets than their peers.

#### Resolution

• If a resource overprovisioning diagnosis is made, then the bolt scale down resolver decreases the number of Heron instances associated with the bolt. The scale down factor is a configuration option. If the action results in backpressure the operation will be blacklisted and a subsequent scale up operation will bring the topology back to a healthy state.
• The restart instance resolver moves slow instances to new containers (i.e., kills the slow one and restarts it?).
• The data skew resolver adjusts the hash function used to distributed data to the bolts.
• The scale up resolver scales up the resources dedicated to a bolt initiating an underprovisioning diagnosis. “To determine the scale up factor, the Resolver computes the percentage of the total amount of time that the Heron Instances spent suspending the input data over the amount of time where backpressure was not observed.”

Here’s an example of dynamic resource provisioning at work while the workload is manipulated:

### SLO maintenance

We observe that in a large number of streaming applications, users spend a significant amount of time tuning the topology to meet the requirement of a throughput above a certain threshold.

In their experiment, the authors simply submit a topology with a single Heron instance provisioned for each spout and bolt, and provide an SLO asking for at least 4 million tuples a minute at steady state. Dhalion is able to figure out a configuration that meets this objective as you can see in the figure below – although it does take about 70 minutes to do so!

The Dynamic Resource Provisioning Policy that we previously presented, assumes that the input data rate is given and attempts to allocate resources so that the system can handle the input data load as it varies over time. The Throughput SLO Policy goes a step further by attempting to adjust the input data rate by increasing the number of Heron Instances that belong to the spouts, in order to meet the performance SLO.

It uses an additional symptom detector, diagnoser, and resolver:

• The emit count detector computes the total rate at which a spout emits data and forwards it to the throughput SLO violation diagnoser.
• The diagnoser checks whether the topology is in a healthy state. If it is healthy, and the throughput doesn’t meet the required SLO, it emits a diagnosis that is forwarded the spout scale up resolver.
• You can probably guess what the spout scale up resolver does: it scales up the resources associated with the spout.

### The last word

Note that although Dhalion has been implemented on top of Heron, its architecture and basic policy abstractions can be adopted by other streaming engines as long as they provide a metrics collection API and potentially a scaling API.


text:
# How does one interpret regression coefficients when no dummy variables nor intercept are dropped?

I am familiar with how to interpret linear regression coefficients when the independent variables are dummy coded and one of them is dropped. And this question helped me understand how to interpret the coefficients when the intercept is dropped instead.

I am also aware of the dummy variable trap, and why it is necessary to drop one of the dummy coded categories. ( $X^TX$ will not be invertible )

However, I've found that by using regularization $X^TX + \lambda I$ is never singular and therefore invertible. This seems to allow me to not have to drop any dummy variable nor the intercept.

The problem is, I couldn't find a way to interpret the coefficients when neither of those columns are dropped.

e.g.:

Let the dataset be talking about height measurements in males and females and the gender column is dummy coded into $x_f$ and $x_m$.

Let the resulting ridge regression be $\hat{y} = \beta_0 + \beta_fx_f + \beta_m x_m$

How can I interpret the values of $\beta_0$, $\beta_f$ and $\beta_m$?

Does it change if my category has more then 2 possible values?

Does it change if I have multiple categories?

Is this even a valid way of doing regression?

• Why should the interpretation depend on the procedure you used to fit the model? The underlying model hasn't changed. Thus, the predicted value for males is $\beta_0+\beta_m$ while the predicted value for females is $\beta_0+\beta_f,$ just as always (assuming indicator coding for the dummies). – whuber Mar 21 '18 at 22:03
• Even though the underlying model hasn't changed, the interpretation of the meaning of the values of the beta coefficients varies drastically depending on how the model came to be. For instance, when you drop one of the dummy variables, your coefficients are now referencing changes from that variable. – wmaciel Mar 21 '18 at 23:05
• That may be so, but it doesn't create any new difficulties. The interpretation of any coefficient remains the same: plug in two values for one regressor (such as gender), compute the corresponding predictions, and subtract: that's how the prediction changes with a change in the regressor. Without the ridge regression your model would be unidentifiable, but it could still be fit and the coefficient interpretations would be exactly the same. – whuber Mar 21 '18 at 23:14
• Your comment was quite helpful in solving my underlying problem of how to explain the rate of change caused by the independent variables. If you write an answer about it I would totally upvote it. However, it doesn't really answer the core of the question which is if the $\beta$ coefficients have any real meaning. I highly appreciate you taking the time to comment. – wmaciel Mar 21 '18 at 23:54
• That is a good point, and I agree with you now. I think your comment answers my question well. In the sense that the $\beta$ coefficients have no inherent meaning in this case, and should only be "interpreted" in a difference scenario. – wmaciel Mar 22 '18 at 0:54

It is certainly a valid way to run a regression. The interpretation of the coefficients in your example ridge regression is simple:

• If you are a male, then your predicted value is $\widehat{y}=\beta_0+\beta_m$
• If you are a female, then your predicted value is $\widehat{y}=\beta_0+\beta_f$
• The predicted difference between males and females is $\beta_f-\beta_m$

Then the interpretation is completely analogous if you have more than one categorical value, or if your variable has more than two categories. For example, if gender had a "not given" category that you wanted to include in your model with $x_n$, then you would simply add that:

• If gender is not given, then your predicted value is $\widehat{y}=\beta_0+\beta_n$
• The predicted difference between males and "not given"'s is $\beta_m-\beta_n$
• The predicted difference between females and "not given"'s is $\beta_f-\beta_n$

And you can keep adding similar examples. There's no limitation on the interpretation of the coefficients because of the intercept/dummy issue.

• I understand that $\hat{y} = \beta_0 + \beta_m$ and so forth, it makes sense. What I am struggling to understand is how to interpret the $\beta$s by themselves. Especially $\beta_0$. e.g. When you drop the male dummy variables $\beta_0$ is the average $\hat{y}$ when the $x_f = 0$. And $\beta_f$ is the average variation in $\hat{y}$ when $x_f = 1$. – wmaciel Mar 21 '18 at 23:02
• If people can be only female or male, such that $x_m+x_f=1$, then $\beta_0$ on its own has no clear interpretation. This does not mean in the least that the model is incorrectly specified or anything like that. It just means the number on its own means nothing. Think of it this way: if I tell you that that the price of a ticket is $Price=10+2*(Male)+4*(Female)$ (i.e., males pay \$12 and females pay \$14), what does the 10 represent? It's a perfectly valid equation and yet the 10 doesn't have a clear interpretation. – user3208442 Mar 22 '18 at 0:32
• @user3208442 excellent job pointing out how two rank-dependent(nonsingular) covariates can be combined to estimate the usual "slope" term. One thought, how does one get the variance of ridge estimates? I'm curious if the post-hoc estimate yields similar variances to the full-rank solution. – AdamO Mar 22 '18 at 16:48
• I had to look this up because I've never needed to get the variance of a ridge coefficient :-) Here's a link to some slides with the formula; check slide 7: web.as.uky.edu/statistics/users/pbreheny/764-F11/notes/9-1.pdf. – user3208442 Mar 22 '18 at 17:05

A trace plot can help elucidate how and why this works-ish

set.seed(123)
n <- 100
x <- rbinom(n, 1, 0.4)
y <- rnorm(n, -3 + 0.5*x)

X <- cbind(1, model.matrix(~-1+factor(x)))
I <- diag(3)
ridge <- function(w) solve(t(X)%*%X + w*I, t(X)%*%y)

matplot(t(sapply(seq(0, 100, by=1)[-1], ridge)), type='l', xlab='Ridge weight', ylab='Parm estimate')
legend('bottomright', lty=1:3, col=1:3, c('Intercept', 'X0', 'X1'))

Gives:

Taking a very small penalty tells us what might be one of the pseudoinverse solutions to the rank deficient solution to the least squares regressors: $\beta = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^TY$.

> ridge(0.001)
[,1]
-1.8752108
factor(x)0 -1.1421614
factor(x)1 -0.7330494

This approximates the left limits of the trace plot I showed above. Note also some empirical statistics about the sample:

> mean(y[x==0])
[1] -3.017391
> mean(y[x==1])
[1] -2.608278
> mean(y[x==0]*mean(x==0))
[1] -1.810435
> mean(y[x==0]*mean(x==1))
[1] -1.206956

You can see the "quasi-intercept" is heading toward about -1.8. This is the prevalence of $\neg X$ multiplied by the mean of $Y$ when $X=0$. e.g. $E[Y|X=0]E[1-X]$ (see the third command). The "quasi-X0" term is the prevalence of $X$ multiplied by the mean of $Y$ when $X=0$ e.g. $E[Y|X=0]E[X]$ (see the fourth command). Together they add up to $E[Y|X=0]$ (see the first command). The "quasi-X1" term is the mean of $Y$ when X=1 minus the intercept term. That is $E[Y|X=1]-E[Y|X=0]E[X=0]$, so subtract the second term from the third term = -2.5 + 1.8 = -0.7.

So, in my opinion these contrasts are utter nonsense! They are redundant and don't tell us anything useful that a simple slope/intercept would.

• I am sorry, I don't quite understand what you mean. - Could you elaborate on what is going on in that R snippet? - What are the "prevalence" comments you had about where the intercept was heading. I am very lost in your answer, sorry. – wmaciel Mar 21 '18 at 21:49
• @wmaciel I edited to include more detail. If you're still unclear, please say more. – AdamO Mar 21 '18 at 21:59
• I've followed your calculations, I think I understand what you did and I highly appreciate your time on this. However, I don't see how you concluded that the coefficients don't tell us anything from the math you showed on your answer. – wmaciel Mar 21 '18 at 23:17
• @wmaciel thanks for clarifying. I was trying to point out that the interpretation is very strange. The X1 coefficient has a negative slope when X has a positive trend with Y. To summarize, the coefficients do have an interpretation. But it is far afield from normal parametrizations. – AdamO Mar 22 '18 at 14:02