3
$\begingroup$

Let $X$ be a beta distributed variable with parameters $a$, $b$. Let $Y$ be a beta distributed variable with parameters $c$, $d$. Let $Z = \max(X, Y)$.

Does anybody know of a fast way to compute the mean and variance of $Z$ given $(a, b, c, d)$?

$X$, $Y$ don't necessarily need to have beta distributions, but they should be similar -- in $[0, 1]$.

What I really want to find is a way to quickly approximate the distribution of the sample max of a bunch of random variables. Let $Z = \max(\{X_1, X_2,\dots , X_n\})$. If I know parameters (not necessarily beta-distribution) for $X_1, X_2,\dots, X_n$, can I quickly compute a set of parameters (same distribution as $X_i$) to form a distribution that closely approximates $Z$?


EDIT:
To clarify, the purpose of this has to do with programming AI for board games. If we are evaluating a position in a chess game and we determine one move leads to a 60% chance of winning while all others have a 20% chance of winning, then we value the position as a 60% win. This is the minimax algorithm... However, what I'm curious about is whether this can be improved upon. In the simple case, we approximate: $$ \mu_c = \max(\{\mu_1, \mu_2,\dots, \mu_n\}) $$ where $\mu_c$ is the expectation from the current position and $\mu_i$ is the expectation from each of the sub-trees.

It seems like we should be able to do better than this. Can we find a function f that replaces max and closely approximates parameters for the distribution of the sample maximum? $$ (\mu_c, \sigma_c) = f\left(\{(\mu_1,\sigma_1), (\mu_2,\sigma_2), \dots, (\mu_n, \sigma_n)\}\right) $$ In this case, we still want $\mu_i$ to be the expectation from each of the nodes. However, $\sigma_i$ does not necessarily need to be variance/standard deviation; just a parameter that represents uncertainty.

Just as: $$ \max(\{a, b, c\}) = \max\left(\{\max(\{a, b\}), c\}\right) $$ We should expect: $$ f\left(\{a, b, c\}\right) \approx f\left(\{f(\{a, b\}), c\}\right) $$ So $f$ does not necessarily need to take parameters for more than two nodes.

One thing, however, is that $f$ should be relatively fast to compute. If the integrals must be calculated, I think doing double exponential integration might work well, but I'm not sure --

$\endgroup$
4
$\begingroup$

I think I can help with this.

So, when $Z = \max(\{ X_1, X_2, \ldots, X_n\})$ takes on a particular value $Z=z$, this tells you that:

    * You have one sample $X_i = z$
    * Your remaining $n-1$ samples are all $\leq z$

As such, we can say by inspection that $$ p(Z = z) \propto p(X=z)P(X \leq z)^{n-1} $$ where I'm using lowercase $p$ to indicate a probability density, and uppercase to indicate an actual probability. $P(X \leq z)$ you can get using the cumulative density function of your distribution. You'll need to find the normalisation term too to ensure the whole thing integrates to $1$;

As for quickly approximating it, I suspect that unless this has a nice closed form, you're going to be looking at numeric methods. But that should be pretty straight forward:

    * Generate a load of samples using a uniform distribution in the range $[0,1]$
    * Use importance sampling to weight them by $P(Z=z)$ (remember that when using importance sampling, you do not need a normalised distribution).
    * Fit your approximating distribution to the data using the importance sampling weights.

and you're done.

Bear in mind that as $n$ grows, most of the probability mass of your distribution will concentrate near $1$. It may be worth using a slightly more complicated sampling procedure than just uniform to ensure you have a good number of samples in this region.

EDIT: It's been pointed out below that I assume identically distributed data in the above. Yeah, that's wrong. I think we're still ok though.

let's take the two variable situation, where we want to find the distribution over $Z = \max(X,Y)$. Just using some standard marginalisation, and assuming independence of $X$ and $Y$, $$ p(Z = z) = \int_x \int_y p(Z=z|X=x,Y=y)p(X=x)p(Y=y) dy dx. $$ (For brevity, I'm not going to keep writing $p(X=x)$, $p(Y=y)$, etc and just use $p(X)$ and $p(Y)$. Hopefully all still clear.)

Given $Z$ is the max of $X$ and $Y$, I'm gonna say $$ p(Z=z|X,Y) = \delta(\max(X,Y),z) $$ where the delta function uses its standard definition. So now we have $$ p(Z = z) = \int_x \int_y \delta(\max(X,Y),z)p(X)p(Y) dy dx. $$ We can split up the integration ranges into $X>Y$, $Y>X$ and $Y=X$ as follows, $$ p(Z = z) = \int_y \int_{x<y}\delta(\max(X,Y),z)p(X)p(Y) dx dy + \int_x \int_{y<x} \delta(\max(X,Y),z)p(X)p(Y) dy dx + \int_x \int_{y=x} \delta(\max(X,Y),z)p(X)p(Y)dydx. $$ I think those ranges are correct. They look right on paper.

That makes our max functions nice and easy to evaluate. $$ p(Z = z) = \int_y\int_{x<y} \delta(Y,z)p(X)p(Y) dx dy + \int_x\int_{y<x} \delta(X,z)p(X)p(Y) dy dx + \int_x \int_{y=x} \delta(X,z)p(X)p(Y)dxdy $$ which in turn let's us use the sifting property of the delta function to say $$ p(Z = z) = \int_{x<z} p(X)p(Y=z) dx + \int_{y<z} p(X=z)p(Y) dy + \int_{y=z}p(X=z)p(Y)dy. $$ Tidying all this up, and using similar notation to before to show probabilites rather than density functions, we get $$ p(Z = z) = p(Y=z)P(X<z) + p(X=z)P(Y<z) + 0, $$ where I'm pretty sure the last term just integrates away to $0$.

Assuming the above is all correct, I'm guessing a similar form applies when dealing with more than 2 variables.

$\endgroup$
  • $\begingroup$ After "we can say by inspection" you appear to take all the $X_i$ to be identically distributed and independent. The point of this question is that the $X_i$ are not identically distributed. (The OP appears to assume they are independent, though.) $\endgroup$ – whuber Nov 12 '12 at 17:20
  • $\begingroup$ Oh, oops, yes, you're right. I messed that up. I have a feeling though that the above solution can be salvaged by summing over all the variables, which if they're independant gives an answer $\propto \sum_{i=1}^n p(X_i=z)\prod_{j \neq i}^n P(X_j \leq z)$. I've only quickly scribbled out the math for that though, may have missed something along the way... $\endgroup$ – Pat Nov 13 '12 at 10:10
  • $\begingroup$ I'm looking into importance sampling. Thanks.. I've wanted to not make use of any MC type methods though. It seems like somebody must have worked out an approximate solution to this problem (the idea of extending the "max" function to parameterized distributions as opposed to specific values). I was hoping to find a parametric family of distributions such that taking the max of two random variables in this distribution results in another random variable in the same distribution, but it doesn't seem like such a distribution exists (well, not any that are general enough). $\endgroup$ – BobIsNotMyName Nov 13 '12 at 11:07

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.