There is a array of length A. We have to perform B operations. In each operation, we can select a subarray of any length and increase all its elements by 1. All subarrays are equiprobable. Find the expected value of the square of the sum of elements. (mod 1e9+7)
Constraints:
1<=A,B<=1e9
Sample Input 1:
A=2
B=2
There are 9 different order of operations.
(0,0) + (1,1) = 2
(0,0) + (0,0) = 2
(1,1) + (0,0) = 2
(1,1) + (1,1) = 2
(0,1) + (0,0) = 3
(0,1) + (1,1) = 3
(0,0) + (0,1) = 3
(1,1) + (0,1) = 3
(0,1) + (0,1) = 4
Expected Value= [4*(2^2) + 4*(3^2) + (4^2)]/9 = 68/9 (mod 1e9+7) = 555555567
How do I approach this problem?
Note: I used $$$n$$$ and $$$k$$$ for $$$a$$$ and $$$b$$$ respectively. I also assumed based on the example that the array starts out with all zeroes.
If $$$A(n,k)$$$ is the answer for the input $$$n,k$$$,
where
In an operation, a subarray of length $l$ is chosen from an array of size $$$n$$$. $$$E_1(n)$$$ denotes the expected value of $$$l$$$ and $$$E_2(n)$$$ denotes the expected value of $$$l^2$$$.
Claim: $$$A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$$$
If we denote the length of the subarray chosen in operation $$$i$$$ as $$$l_i$$$, we can see that the problem wants us to find the expected value of
Expanding this out we get
Using linearity of expectation we get that the answer is the expected value of
Using the definitions of $E_1(n)$ and $$$E_2(n)$$$ given above, we get
as desired.
Claim: $$$E_1(n) = \frac{n+2}{3}$$$
Since expected value is just the average value, we want to find the average value of $$$l$$$ which is
The summation just goes through all the possible subarray sizes, $$$sz$$$ and multiplies it by the number of subarrays of size $$$sz$$$, $$$n+1-sz$$$.
We can simplify this to get
Using the fact that $\sum_{i = 1}^{n}i = \frac{n(n+1)}{2}$$$ and $$$\sum_{i = 1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$$$ this simplifies to $$$$$$E_1(n) = \frac{n+2}{3}$$$$ as desired.
Claim: $$$E_2(n) = \frac{(n+1)(n+2)}{6}$$$
Similar to how we found $$$E_1(n)$$$, we can see that
This simplifies out to
Using the fact that $\sum_{i = 1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$$$ and $$$\sum_{i = 1}^{n}i^3 = \left(\frac{n(n+1)}{2}\right)^2$ this simplifies to
as desired.
Thank you so much.
You have explained it so well here.
Could you suggest some similiar problems or articles where I could practice?
Here are two tutorials by Errichto that I found pretty helpful, Part 1 and Part 2. They also have problems to help practice the techniques.
Some problems that I can remember off the top of my head that use expected value are these:
GR 10 H — This solution in my opinion is more intuitive and easier to understand than the official one.
Merge Cards — O(n) solution by Errichto
Edu 57 F
There are also some nice resources out there like this one that aren't all expected value problems but in my opinion, help to build an intuitiveness that can help solve expected value problems.
I will go through them. Thank you again.