Is this an easy problem about this topic?

For Paths in tree (2) can anyone (with spoiler maybe) explain how to do this with contribution method. For some reason centroid and dp solutions comes to mind but not contribution method.

Unless this is what is meant by contribution method in the context of the problem:

Thanks for such awesome blog.
I tried to work on above problems myself. For problem, Max of N under EV easy problem, I am not sure whether my approach is correct or not. So can someone please confirm, whether it's correct or let me know where I am going wrong.

Is it correct approach ?

Start in 15 minutes.

Can somebody explain why test examples for this problem is 0.8 and 0.26?

If you have one probability 0.1 and other one 0.2 why it isn't 0.3?

Errichto Thanks for the lecture. The first few minutes of the video seems to be missing. Any chance of re-uploading the missing part.

Is ans of Problem 8 in EV problem (which was left as homework) 8?

My working-

Lets call Expected value R.

Base case- We can get HH in first 2 tosses itself, with probability of .

(Not reduced purposefully).

Recurrence- If we dont get HH, then we used 2 tosses. The probability of not getting HH is , so with probability of we will get (2 + R)

Final Expression-

Is it correct? :)

How to find the sum over squares of lengths of paths?

I know only with FFT, but for sure there is some nice solution.

For Q1 P(getting an ace) = (C(4,1) + C(4,2) + C(4,3) + C(4,4))/C(52,10) Is this correct?

How to solve the last part of Question 9 Volleyball ? I feel like it is somehow related to Bayes' theorem, but i am unable to calculate the expected wins of the winner.

In 9th question on volleyball, expected number of total matches won by winner = 3 + expected number of matches won by winner in group stage. What is expected number of matches won by winner in group stage? Is it 11/8

https://codeforces.net/problemset/problem/601/B — Also a problem of Contribution technique (after being decomposed into simpler form). Try this out guys.

guys can anyone explain how to solve this question: link:https://www.codechef.com/AMR18ROL/problems/MARTING1

Can someone please explain the solution of Eating Ends? I can't understand the no. of ways for an element to remain till last.

For the 9th question of EV easy problems, is the answer to the problem EV of the number of matches won by the winner of the whole tournament 29/6 ?

Hi. Just like EV easy problems 6-8, how to solve something flipped (updated) like Calculate Expected Value of "Number of consecutive triples of Heads" in $$$N$$$ coin tosses.

My approach, Let $$$R_n$$$ be required result for $$$n$$$ coin tosses. Then, we have that Case 1: if $$$nth$$$ toss is Tails, then we need to add $$$R_{n-1}$$$ to answer.

Case 2: if $$$nth$$$ toss is Heads, then we need to consider two cases again, if $$$n-1th$$$ toss is Tails, we add $$$\frac{ R_{n-2} }{2}$$$ to answer, if $$$n-1th$$$ toss is Heads then again if $$$n-2th$$$ toss is Tails then we add $$$\frac{R_{n-3}}{4}$$$, else we add $$$\frac{1 + R_{n-3}}{4}$$$.

So, $$$R_{n}$$$ = $$$R_{n-1} + \frac{R_{n-2}+R_{n-3}}{2}+ \frac{1}{4}$$$. It doesn't seem right to me. Also, since $$$R_0=R_1=R_2=0$$$, we get $$$R_3=\frac{1}{4}$$$, and $$$R_4=\frac{1}{2}$$$. So, basic examples do seem correct incorrect. Can someone verify this and/or give a different, perhaps easier approach. I like to ask for verification, because when I do so many cases, I always feel like I have done something wrong. Thanks a lot in advance.

UPD: Obviously incorrect, because $$$R_3=\frac{1}{8}$$$.

UPD2 : I think I found the error, I missed the multiplier of $$$\frac{1}{2}$$$ for $$$nth$$$ toss. So that makes it $$$R_n = \frac{R_{n-1}}{2} + \frac{R_{n-2} + R_{n-3}}{4} + \frac{1}{8}$$$. Now all I need for satisfaction, is to solve this recurrence with $$$R_0=R_1=R_2=0$$$ and get the formula provided by Errichto. ( Substitution of formula in place of $$$R_n$$$, for sufficiently large $$$n$$$ (such that we don't have to worry about max function ) does not satisfy the recurrence. ) Can someone point out what's wrong with this approach, thanks.

There is a training, contains 13 problems on probability theory and expected value, 10 of them published on codeforces and can be solved, 3 problems (A,B,C) for beginers can be solved on e-olymp: A. Difficult path, B. A coincidence, C. A full set.

Game on Trees, a nice problem on this topic.

Though I understood the solution better by thinking in way of contribution rather than Linearity of Expectation.

Could someone just go through some/all the bonus parts so that I can have something to check my ideas with?

A nice problem on expected value Your text to link here...

In Volleyball Find EV of the number of matches won by Poland, assuming that they won the whole tournament. I think the answer to the above question will be E(won by Poland) = E(won by Poland in the group stage) + E(won by Poland in the tournament) = 1 + 3 Is that right?

And the other question the EV of played matches of Poland will be E(played matches of Poland) = P(Poland lose in group stage) * 2 + P(Poland lose in the quarter-final) * 3 + P(Poland lose in the half-final) * 4 + P(Poland lose in the final) * 5 + P(Poland won the final) * 5 = 1/3 * 2 + 2/3 * 1/2 * 3 + 2/3 * 1/2 * 1/2 * 4 + 2/3 * 1/2 * 1/2 * 1/2 * 5 + 2/3 * 1/2 * 1 / 2 * 1/ 2 * 5 = 19/6 And I think the symmetric solution is quite elegent. Cool solution. Thanks to your blog

If anyone is interested, this article contains some nice examples (with exercises) of how to calculate the EV with some generalizations, as addition.

In the first problem, the expected value of number of aces, when 10 cards are drawn at random without replacement will be different than the EV when the cards are drawn with replacement.

Is this correct?

From a statistical perspective the important thing about linearity of expectation is that the variables do not need to be independent for linearity of expectation to hold.

Example from https://brilliant.org/wiki/linearity-of-expectation/

"Let that sink in for a moment, as it can be quite counter-intuitive! As an example, this means that the expected value for the amount of rain this weekend is precisely the expected value for the amount of rain on Saturday plus the expected value for the amount of rain on Sunday, even though we do not think that the amount of rain on Saturday is independent of the amount of rain on Sunday (for example, a very rainy Saturday increases the likelihood of a rainy Sunday)."

So even if $$$X$$$ and $$$Y$$$ have some interaction (not independent), we can still decompose expectation of $$$X+Y$$$ into components expectation of $$$X$$$ and expectation of $$$Y$$$.

Here is another example. Suppose you flip 6 coins. Let $$$X$$$ be the RV that counts the number of heads from the first three coins (coins 1, 2, 3). Let $$$Y$$$ be the RV that counts the number of heads from the odd numbered coins (coins 1, 3, 5). Clearly $$$X$$$ and $$$Y$$$ are not independent, because intuitively given a high value of $$$X$$$ a high value of $$$Y$$$ is more likely. Formally $$$P(Y=y) \ne P(Y=y|X=x)$$$. But we can still calculate the expectation of the sum by considering $$$X$$$ and $$$Y$$$ independently. $$$E[X+Y] = E[X] + E[Y]$$$

If anyone is struggling (like I did) to find the actual rigorous meaning of a Random Variable, and what it means actually to "find the sum" of two random variables, here goes:

First of all, random variable is not AT ALL a variable. That's a very misleading name, and for me, was the source of much confusion. A random variable $$$X$$$ is defined as a function which maps occurrences to real values (at least in the scope of Competitive Programming). What it means that $$$X:S->R$$$ , where $$$S$$$ is the sample space, takes in an outcome (an element of the set $$$S$$$) as input and outputs a real value (an element of the set $$$R$$$). The function is defined according to the given problem. For example, if we want to find the "expected number of pips" in a dice throw, the function $$$X$$$ returns the number of pips in the occurrence.

Then what does it mean to add two random variables? If we define $$$X=X_1+X_2$$$, where $$$X_1$$$ and $$$X_2$$$ are two random variables, then $$$X$$$ is actually the composite sum function. This just means that for each occurence $$$w \in S$$$,

$$$X(w)=X_1(w)+X_2(w)$$$. (This is the definition of composite functions.)

Now, about the notation $$$P(X==x_0)$$$: Note that it is not obvious what it should mean, unless it is defined. We shouldn't just use our intuition to guess the meaning of symbols. This is because the $$$P$$$ function is defined only for events (you should read up on Axioms of Probability Theory if you are not sure about the exact definition of Probability itself), and it is not clear what $$$X==x_0$$$ even means.

Let $$$E$$$ be an event (an event is a subset of sample space, so each element of the set "event" is an occurrence. I used to mix up events and occurrence so here was a gentle reminder) consisting of all occurrences $$$w$$$ such that $$$X(w)==x_0$$$. Then $$$P(X==x_0)$$$ is defined as $$$P(E)$$$. So $$$P(X==x_0)$$$ can now be read as the probability of the event that the occurrence has preimage (output of a function) equal to $$$x_0$$$ for the function $$$X$$$.

For the definition of Expected Value of a Random Variable and a very simple proof of linearity of expectation you can click here

I am sorry if all of this is very obvious to experienced coders, but I wanted to put at one place all my thoughts about various definitions and results about random variables.

I didn't quite understood the dp approach for problem 4. Max Of N in EV Easy Problems. If anyone can explain, Thank you!

What is the solution to the total no of matches won by the winner of the tournament? My attempt till now: The winner must win quarter-final, semi-final and final. So we need to only find expected no of matches won by a qualifying team in group stage.

To find that, I wrote all the cases (assuming team A is the team required to qualify and matches are in order AB BC and CA). A qualifies in the following cases: A B A (winners in order), A C A, B B A, A C C, A B C (followed by random selection of A), B C A (followed by random selection of A)

So the expected no of wins in group stage is: 2*(1/4) + 1*(1/4) + 1*(1/4)*(2/3) = 11/12. But this seems wrong because: Total wins = 3. And both qualifying teams will have same expected no of wins. So expected number of wins of not qualifying team = 3-2*(11/12) = 14/12 which is greater than 11/12.

I am surely missing something. Any help would be appreciated :)

Errichto I am having trouble in solving a particular type of expected value problems. In problems, where we move from one state to another with some probabilty and when we reach a special state, we are taken back to the initial state(the state from where we started), I am unable to take into account the part where we move to the initial state. I couldn't find any relevant resource to learn this concept. It would be very helpful if you could give some insight or briefly explain the generalized approach for these kind of problems.

Two problems related to the above concept:

ABC189_f

Codedrills_ICPC_Practice_Session_6

It would be very helpful if anyone can help me with this concept. Thanks in advance!

Super helpful blog!

Google Kickstart 2020 Round D — Beauty of Tree is also a cool problem that can be solved with the "contribution" technique.

About the "Imbalanced Array" problem in O(N) solution without fact that we have permutation. Isn't this just a standard stack problem?

I just wanna add a nice question in the list:

https://codeforces.net/contest/1777/problem/D

solution for Math encoder (Code Jam Kickstart 2017 round B)

#include <bits/stdc++.h>
using namespace std;
int n;
// O(N^2)
double solve1(vector<double> &arr){
	double ans = 0;
	n = arr.size();
	for(int i=0;i<n;i++){
		for(int j =i+1;j<n;j++){
			double x = arr[j] - arr[i];
			double p = powl(2,j-i-1);
			double c = p * x;
			ans += c;
		}
	}
	ans /= powl(2,n-1);
	return ans;
}

// O(N)
double solve2(vector<double> &arr){
	double ans = 0;
	n = arr.size();
	double ev_max = 0;
	double ev_min = 0;
	for(int i=0;i<n;i++){
		double x = arr[i];
		double p = powl(2,n-i-1);
		double c = p * x;
		ev_min += c;
	}
	for(int i=n-1;i>=0;i--){
		double x = arr[i];
		double p = powl(2,i);
		double c = p * x;
		ev_max += c;
	}
	ans = ev_max - ev_min;
	ans /= powl(2,n-1);
	return ans;
}
int main()
{
	vector<double>arr = {1,1,2,3,4,5,7};
	sort(arr.begin(),arr.end());
	double ans1 = solve1(arr);
	double ans2 = solve2(arr);
	cout<<"ans1="<<ans1<<"\n";
	cout<<"ans2="<<ans2<<"\n";
    return 0;
}

In Easy EV section regarding ques 8, its patterning like

honestly i tried to many times to understand this topic but cant get even once, i m dumb hope someday i will find my expected value