PUMaC 2019 · 加试 · 第 5 题

5. Using part 3 and linearity of expectation, note that Var( aX ) = E (( aX ) ) − E ( aX ) = 2 2 2 2 2 2 2 2 a E ( X ) − a E ( X ) = a ( E ( X ) − E ( X ) ) = a Var( X ). 2.1 Grading 1 points for each part. 3 1.4.3 [5 points] We induct on the number of sets. Note that P ( A ∪ A ) = P ( A ∪ ( A \ A )) = P ( A ) + P ( A \ A ) ≤ P ( A ) + P ( A ) . 1 2 1 2 1 1 2 1 1 2 By induction we can find that P ( A ∪ · · · ∪ A ) ≤ P ( A ∪ · · · ∪ A ) + P ( A ) , 1 n 1 n − 1 n hence the desired result. 3.1 Grading 2 for having the idea to use induction, 5 for complete proof. 4 1.4.4 [10 points] We find that ∑ E ( X ) = x P ( X = x ) x ∑ ≥ x P ( X = x ) ( t is nonnegative) x ≥ t ∑ ≥ t P ( X = x ) x ≥ t = t P ( X ≥ t ) . This proves the desired statement. 4.1 Grading 4 points for writing out the formula for expected value, 10 for finishing the proof. 5 1.5.1 1 7 [5 points] If X is the value of the roll of a die, then E ( X ) = (1 + 2 + 3 + 4 + 5 + 6) = . 6 2 2 1 7 35 2 2 2 2 2 2 2 2 The variance is Var( X ) = E ( X ) − E ( X ) = (1 + 2 + 3 + 4 + 5 + 6 ) − = . 2 6 12 2 For one hundred rolls, let the values be X , . . . , X . Since the rolls are independent 1 100 E ( X + · · · + X ) = 100 E ( X ) = 350. For the variance, we find Var( X + · · · + X ) = 1 100 1 1 100 875 100 Var( X ) = . 1 3 2 5.1 Grading 2 points for expected value, 3 for variance. 6 1.5.2 [5 points] We have three cases: if we roll RR we are done; if we roll RB we have to start over with two extra rolls; if we roll B we start over with one extra roll. Therefore, 1 1 1 E ( R ) = (2) + (2 + E ( R )) + (1 + E ( R )), so E ( R ) = 6. 4 4 2 1 1 25 25 Similarly, E ( K ) = (2) + · ( E ( K ) + 2) + ( E ( K ) + 1). Solving for E ( K ) gives 2 26 26 26 26 E ( K ) = 702. For the random variable M , we claim that this is the random variable representing the minimal number of draws needed to draw one red card plus 1. To observe this, note that P ( M = t ) implies that the last two cards drawn are either RR or RB, and that for every pair of adjacent cards before, they are either BB or BR. But this requires that the first t − 2 cards are B and the t − 1st card is red. Hence, it suffices to compute the minimal number of draws it takes to draw a red card, and then add 1. To do this, we repeat the 1 1 E same argument as before: E = + ( E + 1), which means that = 1 and so E = 2, which 2 2 2 means that E ( M ) = 3. 6.1 Grading 1 point for each of R, B, K and 2 points for each M . Subtract at most 1 point if there is a calculation error but the reasoning is correct. 7 1.5.3 11 21 231 [10 points] First, E ( X X ) = · = . 10 20 2 2 4 For the variance, ( ) 2 Var( X X ) = E ( X X ) 10 20 10 20 2 2 2 2 = E ( X X ) + E ( − 2 X X ) + E ( X X ) 10 20 10 20 10 20 ( ) ( ) 2 2 2 2 1 + · · · + 10 1 + · · · + 20 2 = − E ( X X ) 10 20 10 20 ( ) 2 11 · 21 21 · 41 11 · 21 = − 6 6 4 35035 = . 16 2 21 · 11 11 · 10 2 3 4 By manual computation, we observe E ( X ) = , E ( X ) = , and E ( X ) = 10 10 10 6 4 25333 . This means 10 2 2 3 4 2 Var( X ( X − X )) = E ( X X ) − 2 E ( X X ) + E ( X ) − E ( X X ) 10 20 10 20 10 20 10 20 10 10 106799 2 2 2 +2 E ( X X ) E ( X ) − E ( X ) = 10 20 10 10 80 3 7.1 Grading 3 for expectation of X 0 X 0, 3 for variance 4 for variance of X 0( X 0 − X 0). Subtract up 1 2 1 2 1 to 2 points for an error in calculation with correct reasoning. 8 1.5.4 [5 points] A is the event that the second coin lands heads. B is the event that the first coin lands head. We want to compute P [ A | B ] = P [ A ∩ B ] / P [ B ] . We have that 1 1 1 1 P [ A ] = + · = 3 3 2 2 1 1 1 1 1 1 1 P [ A ∩ B ] = · · + · · = 3 2 2 3 2 2 6 So, the answer is (1 / 6) / (1 / 2) = 1 / 3 . If you return the first coin, the second coin is independent of the first coin. From symmetry, answer is 1 / 2. 8.1 Grading 3 points for first part a d 2 points for the second part. 9 1.5.5 [20 points] Let p = 3 k + 1 be a prime sufficiently large (so that S have distinct modulos in p). Consider T = { k + 1 , . . . , 2 k + 1 } . Modulo p , T is sum-free. We will pick a random ∗ a ∈ Z and compute the number of elements in S which land in T (modulo p ). This subset p will be sum-free. The probability that s ∈ S will land in T is ( k + 1) / ( p − 1) > = 1 / 3 there is a unique a which makes s equal to k+1, k+2, . . . , 2k+1. From Linearity of Expectation, the expected number of elements that land in T is (1 / 3) | S | , which suffices for the proof. 9.1 Grading 5 points for trying to use expectation, another 5 for looking at the probability that s ∈ S land in T . 10 1.5.6 [10 points] ( ) n 3 There are triangles. Each triangle has a probability of p of being in the graph. So, 3 ( ) n 3 there are p expected triangles. 3 4 10.1 Grading 5 points for looking at each triangle separately. 10 for complete solution. Subtract up to 2 points for error in computation with correct reasoning. 11 1.5.7 [30 points] Take 32 n edges, randomly, uniformly, independently with repetitions from A to n B , then fix X ⊆ A, Y ⊆ B , | X | = | Y | = . Now we have that P (no edge is from X to Y ) = 4 2 n ( ) 2 n 1 32 n 32 n − 2 n 2 n 16 (1 − ) = (1 − ) < e . There exists only pairs of X, Y which is < 2 . n 2 16 n 4 2 n − 2 n Thus since 2 e << 1 there is such graph. 11.1 Grading 5 points for looking at 32 n edges randomly uniformly independently and 10 looking at the probability at P (no edge is from X to Y ). The rest for finishing the proof. 12 2.1.1 [20 points] Second part implies the first part. The second part is equivalent to proving that as m goes to infinity the probability of P being not ε -regular goes to 0, and this follows from the ∑ union bound, namely P ( U, W not ε -regular) ≤ P ( X, Y is not ε regular) ≤ any pair X, Y , | X | ≥ ε | U , | Y | ≥ ε | W |

12.1 Grading 5 points for proving that second part implies the first part. Another 5 for doing manipulation with probabilities. The rest for finishing the proof. 13 2.1.2 ( ) ∑ n 2 [10 points] Since d ( U, W ) ≤ 1 for all U, W and | U || W | ≤ , where n is the U,W, unordered 2 1 number of vertices of the graph it follows that q ( P ) ≥ 0 , q ( P ) ≤ . 2 13.1 Grading 4 for looking at d ( U, W ) ≤ 1 and 4 for looking at unordered pairs. The rest for finishing the proof. 14 2.1.3 [10 points] Follows immediately from lemma 2 . 1 . 1. 5 14.1 Grading At most 5 points if a solutin mentions lemma 2 . 1 . 1 but is not completed. 15 2.1.4 [30 points] Since ( U, W ) is not ε -regular there exists U , W ⊆ U, W , | U | ≥ ε | U | , | W | ≥ 1 1 1 1 2 n ε | W | , | d ( U , W ) − d ( U, W ) | ≥ ε . Let Z be as before. We have that var ( z ) = ( q ( U , W ) − 1 1 | U || W | q ( U, W )). On the other hand since Z differs from E ( z ) = d ( U, W ) by ≥ ε with probability | U || W | | U || W | 1 1 1 1 2 ≥ thus var ( z ) ≥ ε . The result follows from this. | U || W | | U || W | 15.1 Grading 2 n 10 points for showing that var ( z ) = ( q ( U , W ) − q ( U, W )). Another 10 for looking at | U || W | E ( z ) and difference with d ( U, W ). At most 20 for looking at these but not finishing the proof. 16 2.1.5 n (1 − ε ) n [50 points] Put ≥ c = | V | = ... = | V | ≥ . For all 1 ≤ i < j ≤ k define a 1 k k k partition V of V into ≤ 2 parts and a partition of V int ≤ 2 parts as follows: if ( V , V ) ij i j i j is ε -regular V , V are trivial(only one part) otherwise we partition as in previous proof. ij ji Take a paritition V of each V defined by the Venn diagram of all k − 1 partitions of V . i i i,j | V | c i k − 1 V has at most 2 parts. To make their sizes equal let b = [ ] = and split each part i k k 4 4 of V into disjoint sets of sizes b each, and if there is something remaining add it to the i c n ′ ′ k − 1 k − 1 exceptional sets V . Now | V | ≤ | V | + bk 2 ≤ | V | + k 2 ≤ | V | + ( n is the number 0 0 0 k k 0 0 4 2 c k of vertices of the graph), since ck ≤ n . Also note that l ≤ k ≤ k 4 . Since P is not ε -regular b 2 c 1 ′ 2 4 5 by problem 2 . 1 . 4 and by lemma 2 . 1 . 1 we have that q ( P ) ≥ q ( P ) + εk ε ≥ q ( P ) + ε , 2 n 2 3 where the last inequality follows from kc ≥ (1 − ε ) n ≥ n . 4 16.1 Grading ′ 35 for showing that there exists a new partition of V such that it’s equitable and | V | ≤ i 0 n | V | + . 10 for mentioning problem 2 . 1 . 4 and lemma 2 . 1 . 1 0 k 2 17 2.1.6 εn [15 points] Start with any partition into t equal parts such taht | V | ≤ t ( ≤ for large 0 2 1 5 n ). As long as it is not ε -regular apply 2 . 1 . 5 and note that index increases by at least ε 2 1 and is never bigger than so it stops in at most s steps and the size of the exceptional set 2 6 6 n 1 nε nε nε nε 1 t − 2 incerases by at most s ≤ (1 + ) = + ≤ . (because 2 ≥ ). t 5 6 2 4 4 4 2 e ε 17.1 Grading 10 points for applying 2 . 1 . 5 by starting from a partition. 6 18 2.2.1 ε 10 [50 points] Take, say, regular partition of G with t = , which exists by Collegiate 10 ε Splitting theorem. V = v ∪ V ...V , t ≤ k ≤ T = T ( t, ε ). Remove now the following edges: 0 1 k 2 εn