(4) You are given two Gaussian variables: X_1 and X_2 with means m_1, m_2 and variance v_1, v_2. Suppose you know the sum X_1 + X_2 is equal to n. What is the expected value of X_2?

For question 1, we recall that a positive definite symmetric matrix is one with all eigenvalues greater than 0. Thus, one method would be to calculate the eigenvalues of this matrix. We call the matrix M. We let the nxn matrix A be the matrix with all a's. We then note that: M = A - (a-1)I, where I is the identity matrix. This is a matrix polynomial of A (call this polynomial p(x) = x-(a-1)). By the spectral mapping theorem, we note that the eigenvalues of M are p(t), where t is an eigenvalue of A. Thus, it suffices to find the eigenvalues of A. Since A clearly has rank n-1, the eigenvalue 0 appears with multiplicity n-1. One can see that another eigenvalue is na, or this can be noted by deriving the matrix's characteristic polynomial. The trace is na. All other coefficients are 0 because the eigenvalue 0 has rank n-1 (to see this, note that the characteristic polynomial is (x-t)x^(n-1), where t is the other eigenvalue. Solving for the root of this polynomial gives that an eigenvalue is na. It follows that the eigenvalues of M are 1-a and an-a+1. Because they must be positive, we get that -1/(n-1)1.

Question 2) seems incomplete. Do you mind showing the complete question? Thanks!

For question 2, you can do as follows: Suppose that the first n is broken into n_1+n_2. We have two subproblems now: one starting with n_1 and S_1 is the tally we keep for this subproblem and one starting with n_2 and S_2 is the tally we keep for this subproblem. S=S_1+S_2+n_1n_2. If we use the hypothesis that someone above suggested (n(n-1)/2), strong induction yields the required result.

for q2: My first solution was via induction, as in the solution above. However, that the answer is n_C_2 (read n choose 2) seemed like this problem should have a direct (i.e. w/o induction) solution. And here is one: Think of this problem as talking about the edge set in a complete graph K_n - note that there are n_C_2 edges. You partition the edge set into what are called bipartite edge sets: Given the vertex set V, break it up as V_1, V_2 (of sizes n_1, n_2). All of the edges between V_1 and V_2 form our first bipartite graph (with n_1 x n_2 edges). Repeat with V_1, separately with V_2. Thus, sum across the partitions of the corresponding n_1 x n_2 values = total # of edges in the complete graph to begin with = n_C_2.

Question 3: Let p = proportion of heads = 0.502 p0 = supposed fair coin proportion of heads = 0.5 n = number of tosses = 1,000,000 (p - p0)/√(p0(1-p0)/n) ≈ 4 So P > 4 is essentially 0.

There was a typo above, the final answer is that a must be between -1/(n-1) and 1 assuming n is greater than 1.

Regarding question 1: a positive definite matrix M satisfies v^T M v > 0 for ANY v. Thus choose v = (1,1,...,1). Consequently we have Mv = 1+(n-1)a, and v^T(Mv) = n(1+(n-1)a), which must be > 0. Thus a > -1/(n-1). I dont see how akshat derived the bound that a < 1.

Sorry about q2: At the start we have a number n, and S=0. After some steps, we have a collection {n_1, ..., n_k} of numbers and some value of S. At each step we pick a number n_i and split it into 2 numbers that sum to n_i, and add the product of those two numbers to S (e.g. we could split 7 into 4 and 3, and add 12 to S). We keep going until we reach the numbers {1,1, ..., 1} - when we reach this point, what is the value of S?

To generalize .. (factorial(Million)/502000!*498000!)/(2^Million) forgot a division before 2^Million.

S = n(n-1)/2, I just arrived at this by trying to evaluate for n=1, 2, 3, .. etc, but don't really know how to provide a proper solution.

Can anyone post a solution to last question involving two gaussians ?

For estimating the probability: consider a smaller problem for e.g. you are tossing the coin four times, then what is the probability of getting three heads? Total number of outcomes = 2^n = 16 Number of ways in which Head can come three times = 4!/(3!*1!) ==> HHHT HTHH, HHTH, THHH. = 4 so probability = 4/16 = 0.25. To generalize .. (factorial(Million)/502000!*498000!)(2^Million)