4
$\begingroup$

Let $X_1,...,X_N$ be independent normal random variables. $X_i$ is normal with mean $\mu_i$ and standard deviation $\sigma_i$. Let $x_i$ be a single random sample from $X_i$.

Input: We get all $x_i$'s and all $\sigma_i$'s, but we don't get the $\mu_i$'s.

Question 1 Estimate the histogram of the $\mu_i$'s.

Question 2 Assume the means $\mu_i$ are independently drawn from a distribution $\mathcal{M}$. Generate an estimate of $\mathcal{M}$.

Note: Question 1 was answered below by @soakley but the solution didn't help my application, so I added Question 2.

Note that the goal is not to estimate the $\mu_i$'s individually, but rather to get a good estimate for the histogram, or the distribution, of all the $\mu_i$'s together. This estimate should hopefully be better than what we'd get by simply mixing the Gaussians around the $x_i$'s. A maximum-likelihood estimate should work, but I don't know how to produce it.

Warm up question: A simpler question is the above when all the $\sigma_i$'s are the same. This is easy: see answer at the bottom.

More details: I need a method that I can program and will run in reasonable time. So exponential-time algorithms will not be sufficient.

In my input, $N$ is around 5000, the standard deviations are mostly between 5 and 50, and the means are mostly between 0 and 40.

So far I've tried the naive solution of drawing a Gaussian around each $x_i$ and mixing all these Gaussians. The results don't look at all like the correct distribution of $\mu_i$'s. For example, imagine all $X_i$'s are standard normal RVs. Then my naive method would guess that the $\mu_i$'s lie in a pretty wide Gaussian around 0. However, given the samples $x_i$ and the standard deviations $\sigma_i$, a clever algorithm could clearly see that the best guess is that all $\mu_i$'s are equal to zero. Therefore, it should be possible to do much better than my naive algorithm, possibly with some clever use of Fourier Decomposition.

Answer to warm-up question: Question 1 doesn't have a good solution; to get a good solution, one would need to assume a posterior distribution. As for question 2: when all standard deviations are the same, then to get an estimate for the distribution $\mathcal{M}$ we simply need to de-convolve the distribution of $x_i$'s with a Gaussian. I don't see how to generalize this to the case of differing $\sigma_i$'s, though.

Motivation: I am a poker player playing a very swingy poker game (Pot Limit Omaha). We want to find out if the rake is too high, by figuring out the "true winrates" of the player pool. We have as data the winrates of all players in the player pool over a whole year (these are $x_i$), and the standard deviations of their winnings (this is $\sigma_i$) and we want to estimate the distribution of their "true winrates" (the $\mu_i$'s) in order to figure out if enough players are winning. This translates to the above problem.

Ongoing Research I just found a paper of Bovy et al which seems to address a generalization of my question and suggests an algorithm. It seems pretty relevant. I'll read it and report any findings here.

$\endgroup$
  • $\begingroup$ Can you clarify your terminology? There's a bunch of domain-specific language here, and it's not clear what exactly you are measuring. Specifically, (a) what is "winrate" and how is it measured? It sounds like a derived measure? Would the underlying measurement ("winnings"?) be more suitable if you have access to it? (b) how is this related to the standard deviation of the "winnings"? $\endgroup$ – Affine May 23 '13 at 17:45
  • $\begingroup$ Actually having written that out, does this interpretation of your situation correct? You have a dataset of $N$ poker players with $M_i$ hands of poker over one year, but you only have a summary of the $M_i$ hands: the standard deviation $\sigma_{i}$ of (unobserved) winnings $w_{ij}$, and a derived value winrate that is some calculation over (unobserved) winnings $R_i=f(w_{ij})$. You are interested in the distribution of $w_{ij}$. So how winrate is calculated is important, I think. $\endgroup$ – Affine May 23 '13 at 17:47
  • $\begingroup$ @Affine. Firstly, the whole discussion of "winrate" is just in the "Motivation" section. You can simply ignore it: I abstracted away all the domain-specific language in my whole question. But if you're curious, here's the explanation: I have a database of about 10 million poker hands. For each player, I know how much they won in total. But this total win is just a sum of (roughly independent) samples of a random variable. This random variable has some variance. The goal is to analyze the player pool and understand the distribution of means of these RVs, hopefully cancelling out the variance $\endgroup$ – eldodo42 May 23 '13 at 19:23
1
$\begingroup$

I'm not sure your objective is achievable. But here is an idea.

Can you construct a Bayesian model where the posterior for each $\mu_i$ has a known distribution? For example, suppose you can do this with normal distributions. If so, then you can easily find the probability that $\mu_i$ is in a given bin. Suppose you do this for each player for each bin, adding their partial contributions (probabilities) into the bins until you have exhausted your data.

Then divide each bin total by the number of players in your data. This is your estimate of the histogram of the $\mu_i$'s.

Question 2. This sounds like a standard CDF estimation problem. Check out the Dvoretzky-Kiefer-Wolfowitz inequality.

$\endgroup$
  • $\begingroup$ Thank you. You're right -- after thinking about it for a while I realize my objective is not achievable. Treating the samples as entirely separate RVs dos not give us any population to argue about, and thus we need to assign posterior distributions, as you suggest. However, my application would probably do badly with posterior distributions. Instead, I opt to make some assumptions on the $\mu_i$'s -- to assume they are independently chosen from a distribution. This is not perfect for my application, but it'll probably do. I'll opt to edit the original question. Thank you! for the answer! $\endgroup$ – eldodo42 May 25 '13 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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