6
$\begingroup$

PROBLEM

There is an urn with a set of balls where each ball is labeled with a different integer. The numbers on the balls are known and are not a range of integers. For example the set of balls could be $B_k$ = {1,4,67,3,12}. There are two robots, $A$ and $B$, which draw a set of $n$ balls with replacement. Let $a_i$ represent the set of number values on the balls drawn for robot $A$ where $i$ indexes the $n_a$ draws. $b_i$ and $n_b$ are analogously defined for $B$. The robots have some information about why they draw each ball and how many they will draw which we know nothing about except that the method for decision is similar between $A$ and $B$. Robots $A$ and $B$ draw sets of balls for $N_a$ and $N_b$ rounds where $N_a \approx N_b \approx 10^6$. Let $j$ index the rounds, so $n_{aj}$ balls are drawn each round and the ball numbers are recorded in $a_{ij}$ for $A$. $n_{bj}$ and $b_{ij}$ are defined analogously for $B$. The objective is to choose which robot is expected to be the optimal choice for a new sampling $x_{ij}$ where optimal maximizes the sum over all balls, $\Sigma_j \Sigma_i x_{ij}$. Simply put, which robot would you expect to draw the highest sum of ball numbers in the next million rounds?

ADDITIONAL INFORMATION

Since we have $a_{ij}$ and $b_{ij}$ we can say a bit about their distributions. The samples drawn on each round $a_i$ and $b_i$ have 0 balls drawn about 95% of the time. The second most common number of balls drawn per round is 1 and then 2 and 3 and so on so that a histogram balls per round, $n_j$, is monotonically decreasing.

Some rounds have multiple draws of a highly numbered ball which leads to outliers in the distribution of sum per round, $\Sigma_i a_{ij}$. This means that the sum of ball values per round is very hard to model analytically. There could be more information I am not thinking of using since this is a vast simplification of the real problem so please ask.

STANDARD SOLUTION

The standard solution given to me is to make the decision based on the mean and the standard error on mean for the sum of the balls in each round. Define: $\mu_a = \Sigma_j \Sigma_i a_{ij} / N_a = mean_j(\Sigma_i a_{ij} )$ and $ \sigma_{\mu_a} = \sqrt{var_j(\Sigma_i a_{ij} )/ N_a}$. The decision and confidence of that decision is calculated by comparing gausians $\mathcal{N}(\mu_a,\,\sigma^2_{\mu_a} ) $ and $\mathcal{N}(\mu_a,\,\sigma^2_{\mu_a} )$.

The motivation for this choice over $\mu^*_a = \Sigma_j \Sigma_i a_ij / \Sigma_j n_{aj}$ is that the probability for a second ball to be drawn in a round given that one already has ($\approx 0.2$) is much higher than the probability the first ball is drawn ($\approx 0.05$). This smells of Bayesian motivation but I am unable to do the derivation showing $\mu$ to be the empirical Bayes estimator.

QUESTION

Is the mean $\mu_a = \Sigma_j \Sigma_i a_ij / N_a$ really the best estimator and why? What about the sensitivity to outliers? Why not the mean over all the balls drawn, $\mu^*_a = \Sigma_j \Sigma_i a_ij / \Sigma_j n_{aj}$, which is less sensitive to outliers? It seems a lot of information is lost by not using the knowledge of the set $B_k$ so is something more Baysian advisable?

Improve this question
$\endgroup$
1
  • $\begingroup$ It has been pointed out that this is similar to a two-armed bandit problem where the rewards for each arm come from same set of payoffs. $\endgroup$
    – Keith
    Commented Jul 14, 2014 at 14:50

2 Answers 2

Reset to default
2
+50
$\begingroup$

I would suggest the following reason: You have a random variable X - the sum of balls in a round. Which is an independent identically distributed variable ( by assumption?) ( whereas $\mu*$ is not) You are interested in $Z=\frac{1}{N_x}\sum_{j=1}^{10^6}\sum_{j=1}^{n_j} x_{ij}$.
Well the central limit theorem tells you that Z 'approaches' a normal distribution with mean, st dev $\mu_X,\sigma_X/N_x$. see http://www.statisticalengineering.com/central_limit_theorem.html ... basically whatever distribution you start off with, the distribution of a million samples will look like a gaussian.

A further note ( and how the CLT is proved). The easiest way to calculate distributions of sums of n iid random variables is by doing a fourier transform of the individual distribution raising it to the nth power and then inverting the fourier transform. So you can actually quite directly test the convergence for your particular distribution by generating the empirical pdf from your million samples, and then calculate fft etc for 10 sums, 100 etc. ( see convolution and sums of independent random variables)

To convince yourself (or otherwise) that the CLT is applicable its probably simplest to use a bootstrap. a) sample with replacement your 1 million sums of balls 1 million times to generate one sample of Z =the sum of 1 million rounds, $z_k$. b) repeat a) 1000 or more times. c) generate histogram of the distribution of Z from your 1000 samples- compare to the normal approximation implied by the CLT.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I have done the bootstrap and of course got the same answer. I suppose that the mean is likely the best estimator but the problem still remains that it is a bad estimator since one outlier has been known to change the choice. $\endgroup$
    – Keith
    Commented Jul 24, 2014 at 22:31
  • $\begingroup$ Keith, I think your balls are just confusing things. Why don't you spell out the exact problem you are looking at, and show the histogram of sums, so one can see the outliers. Without understanding the context its hard to understand whether the outliers should be included or excluded. basically you could look up robust statistics and eg trimmed mean ( and then use normal distribution with that). $\endgroup$
    – seanv507
    Commented Jul 25, 2014 at 21:19
  • $\begingroup$ If you look at the two "Linked" questions there are rephrasings of the question. However, I think I have been thinking about it the wrong way all along by trying to find the best estimator to use in a t-test. What I should have been looking for is a better test. This then leads to a generalization of the Behrens–Fisher problem which will require a ton more research before I can pose a better question. Thanks though, I believe this is the optimal choice of estimator given that a Welch t-test is to be used but may not be the optimal method for a decision. $\endgroup$
    – Keith
    Commented Jul 26, 2014 at 16:25
0
$\begingroup$

Is the mean really the best estimator and why?

  • If you're looking for the highest reward (or highest sum of ball numbers), then yes, the mean is the best estimator. It's also consistent with common sense to pick the robot which had the highest average in earlier rounds. Especially because the robots don't draw the balls randomly (though as stipulated in the problem, we don't know why or how they choose the balls).

Why not the mean over all the balls drawn?

  • Correct, you do have to do that (for each robot seperately of course). And based on the formula in your "Standard Solution", that's exactly what you're doing (per robot).
    Though it doesn't match your interpretation in the line before that: "...make the decision based on the mean and the standard error on mean for the sum of the balls in each round".

What about the sensitivity to outliers?

  • In this case, I don't think outliers would cause a big problem for the very reasons you've given in your "Additional Information". If 0 is drawn 95% of the time, the second most common is a mere 1, etc. etc. You can do the math. The 'handful of times' that there are high numbered balls (even if there are several), it won't have a big impact if you're doing it a million rounds (and eventually thus devide by N (10^6) to get the mean). Plus, one would imagine the standard error to take this into account.

It seems a lot of information is lost by not using the knowledge of the set Bk so is something more Baysian advisable?

  • I'm going to refer to this paper by S.L. Scott because a) I couldn't put it better, b) I don't want to run the risk of oversimplifying the answer and c) I'm simply not sure with this particular problem: A modern Bayesian look at the multi-armed bandit

-

For a deeper understanding (including the 'regret' vs. 'reward' side of the story, etc.) I refer to: Best Arm Identification in Multi-Armed Bandit

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I have already read those papers and did not find them particularly helpful. What makes you think $\mu$ is the best estimator? Why not $\mu*$? I can assure you that there are outliers, this is why I started to doubt $\mu$ in the first place. $\endgroup$
    – Keith
    Commented Jul 21, 2014 at 20:08
  • $\begingroup$ I see you edited the post. Because it's not about a reward/no reward situation, but rather the value of the reward, I'd say the mean is a better estimator than a Bayesian approach. But I welcome other people's comments should they not agree. As the information is unknown about why the robots draw more balls (and how many), I think µ would be more of a robust estimator than µ* . But the 'unknown information' part is kinda throwing me. $\endgroup$
    – Glenn
    Commented Jul 21, 2014 at 20:42
  • $\begingroup$ Yea, I tried to make it more clear and add what I have learned. After all this effort I sort of hope that the best estimator is not the standard $\mu$. If no rigorous answer is given I will give you the "prize". $\endgroup$
    – Keith
    Commented Jul 21, 2014 at 20:50
  • $\begingroup$ Hope someone can give you the reply you've been waiting for. I understand that µ seems too simple or obvious. Where did you find this 'problem' or what do you want to apply it to? $\endgroup$
    – Glenn
    Commented Jul 21, 2014 at 21:04
  • $\begingroup$ It is a pretty standard split testing problem used everyday by data scientists. Think amazon.com. Balls are transactions and rounds are visitors to the web site. $\endgroup$
    – Keith
    Commented Jul 21, 2014 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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