Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given: A list of integers is there.Now there are 2 buckets -bucket A and bucket B.This step is repeated as long as there are numbers left in the list.Integers from start or end of the list are removed from the list and added to bucket A. The probability of picking a number from the start or the end is equal to 0.20 . Then similarly,the next number picked from start or the end is added to B. Then to A and so on.

Required: Expected values in Bucket A and Bucket B.

Eg  1 ,2m3

 1 or 8 can be added to bucket A.
1) 1-> 4 or 8 can be added to B.
   a)B picks 4 -> A picks 8
   b)B picks 8->  A picks 4
2) 8-> 1 or 4 can be added to B.
   a)B picks 1 ->A picks 4
   b)B picks 4 ->A picks 1
So E(A)=(((8+4)/2+1)+((4+1)/2+8))/2=8.25 

I tried to get a general formula for E(A) and E(B) .I was getting a tree structure with 2^n-1 nodes but I wasn't able to derive a specific formula. Can anyone derive this? I tried for a general list a,b,c,d having 4 integers.

E(A)=1/4((c+d)/2+b)+((b+c)/2+d))+a/2+1/4((b+c)/2+a+c+(b+a)/2)+d/2

Also,clearly the problem is symmetrical from both ends of the list.That is coefficient of a and d is same, b and c is same in E(A) Can anyone simplify this for any general list having m numbers?

share|improve this question
    
No suggestions/insights? –  user43255 Oct 1 '12 at 18:02

1 Answer 1

up vote 1 down vote accepted

For a list $(a_0, \ldots, a_n)$ of $n+1$ numbers let $f(a_0, \ldots, a_n)$ denote the expected value for bucket $A$. Then the expected value for bucket $B$ is $\sum_{k=0}^na_k-f(a_0,\ldots,a_n)$. Therefore we have $$\tag1 f(a_0, \ldots, a_n) = \frac12\left(a_0+\sum_{k=1}^na_k-f(a_1,\ldots,a_n)\right)+ \frac12\left(a_n+\sum_{k=0}^{n-1}a_k-f(a_0,\ldots,a_{n-1})\right)\\ =\sum_{k=0}^na_k-\frac12\bigl(f(a_1,\ldots,a_{n})+f(a_0,\ldots,a_{n-1})\bigr).$$ It should be clear that $f$ depends linearly on the $a_k$, i.e. there are constants $c_{n,k}$ for $n,k\in\mathbb N_0$, $0\le k\le n$, such that $$\tag2 f(a_0, \ldots, a_n) = \sum_{k=0}^n c_{n,k}a_k.$$ From $(1)$ we find $$\tag3 c_{n,k} = 1-\frac12(c_{n-1,k-1}+c_{n-1,k})$$ (with $c_{n,-1}=c_{n,n+1}=0$ understood) and of course $c_{0,0}=1$. One verifies that the recursion is fulfilled by $$\tag4c_{n,k}=\sum_{r=0}^k\sum_{s=0}^{n-k}(-2)^{r+s}{r+s\choose r}.$$ Thus for example $$f(a_0,a_1,a_2) =\frac34 a_0+\frac12 a_1+\frac34 a_2.$$ I am sure that $(4)$ can be simplified a lot, but I won't do that tonight.

One may consider $\hat c_k:=\lim_{n\to\infty} c_{n,k}$. From $(3)$ we find $\hat c_k=1-\frac12(\hat c_{k-1}+\hat c_k)$, hence $ \hat c_k=\frac23-\frac13 \hat c_{k-1}$, which leads to $\hat c_0=\frac23$, $\hat c_1=\frac49$, $\hat c_2=\frac{14}{27}$ and in general $\hat c_k=\frac12+\frac16(-\frac13)^{k}$. As one might have expected, both players have about the same chance of getting list entries that are not too close to the ends.

share|improve this answer
    
:I think this formula gives he wrong answer for a simple case 5,5,5,5 answer E(a)=10 .But I am getting something else using your formula –  user43255 Oct 1 '12 at 18:39
    
Indeed. The condition $c_{n,-1}=c_{n,c+1}$ got lost on the way. I'll rewrite using generating functions. –  Hagen von Eitzen Oct 1 '12 at 20:11
    
How did you get (3)? –  user43255 Oct 1 '12 at 20:16
    
I think there is a small error in (3) .Hope you can check it out? –  user43255 Oct 1 '12 at 20:17
    
Internal Summation f(s+1)=(-2)*(r/(s+1)+1)f(s) ?Is it correct? How to solve it further? –  user43255 Oct 2 '12 at 5:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.