1
$\begingroup$

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?

  • 0
    No suggestions/insights?2012-10-01

1 Answers 1

1

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.

  • 0
    @joriki:I was able to reduce the recursion,I will be writing a complete proof2012-10-14