Hey,
I was trying to solve this expected value problem. I was thinking of using indicator random variables and linearity of expectation but somehow couldn't arrive at the answer. Please help.
Problem: Given a number N, take any random permutation of numbers R = [1, 2, ..., N]. You need to find the expected number of special points in the resulting permutation. An element R[i] is special if:
1. R[i] = R[i-1] + R[i+1] (for 1 <=i <= N-2)
2. R[i] = 2*R[i+1] (for i==0)
3. R[i] = 2*R[i-1] (for i==N-1)
Return the denominator and numerator of the answer. (Fraction should not be further reducible)
Are you sure the problem is correct?
Because according to property 2 and 3, we get R[i - 1] = R[i + 1], which can't be true because the permutations conatains each number from 1 to N exactly once.
properties 2 and 3 hold only for first and last element, dont they?
Thanks for pointing out. I missed it.