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.

N urns are assigned m balls in a stochastic process based on a Pareto distribution. The process is as follows:

X is a Pareto random variable (xminimum = 1, alpha is a parameter) if X > N, throw the ball out Otherwise, put the ball in urn number floor(X)

Do this until m balls have been put in urns. Then rank the urns by number of balls.

What should the final distribution look like, as N and m approach infinity? Does it resemble any standard prob. distribution? Doing Monte Carlo simulations, it seems to be heavy tailed, but not a Pareto distribution. But I'm new to this - just getting my feet wet with stochastic processes.

Edit: Primary question is: What is prob. mass. function for balls in k-th urn (after ordering them). But I'm open to answers along the lines of: Look at it differently. Basic goal is - given a selection of choices, with balls assigned to them, but some choices a priori more popular, what is relationship between stochastic process and pmf of results? (And, yes, if you can't tell, I'm coming from an applied perspective... this question is a simplification of a model encountered assigning awards to favorites).

share|improve this question
    
Or, in general: What relationship is there between the random distribution of balls in an urn process, and the distribution of total balls collected in ranked urns? Under what conditions will they be the same? Under what conditions will they both be power laws? –  user7593 Feb 28 '11 at 8:10
    
What is the output of this process? As described, it seems to be an ordered list of $N$ non-negative integers adding up to $m$. –  Henry Feb 28 '11 at 8:16
    
Yes, Henry, that's exactly correct. I'm interested in the distribution of those integers. What is prob. mass func. of integer x? –  user7593 Feb 28 '11 at 8:19
    
This seems inconsistent. If the output of the process is an ordered list of $N$ non-negative integers, what did you mean by "it seems to be [...] not a Pareto distribution"? A list of integers couldn't have a Pareto distribution, since a Pareto random variable is real-valued. Do you mean the number of balls in some individual urn? If so, which one? In any case, I suspect that ranking the urns by the number of balls will probably make the problem very complicated. –  joriki Feb 28 '11 at 8:32
    
Maybe you want to throw out balls when $X>N+1$, otherwise, the $N$th urn will almost surely be empty. –  Raskolnikov Feb 28 '11 at 10:23
add comment

2 Answers

Ignoring the reranking (as jorki says, it seems to makes things too complicated), I think you can say something like:

The probability that the any particular ball which goes into an urn turns out to go into the $k$th urn [$1 \le k < N $] is $$P_k = \frac{1/k^{\alpha} - 1/(k+1)^{\alpha}}{1-1/N^{\alpha}}$$

With $m$ balls in total in the urns, the probability that there are $m_k$ in the $k$th urn is $$\Pr (M_k=m_k) = \binom{m}{m_k} P_k^{m_k} (1-P_k)^{m-m_k}$$ i.e. a binomial distribution $B(m,P_k)$

Taking the distribution over the urns together, rather than individual urns, this is a multinomial distribution, with the parameters $m$ and $P_1, P_2, \ldots$

share|improve this answer
1  
I guess you meant $P_k = k^{-\alpha}-(k+1)^{-\alpha}$ for the probability to go into the $k$th urn? –  Raskolnikov Feb 28 '11 at 12:54
    
@Raskolnikov: Thank you - I had not spotted the display had failed. What I wanted was $P_k = (k^{-\alpha}-(k+1)^{-\alpha})/(1 - N^{-\alpha})$ –  Henry Feb 28 '11 at 14:25
    
Fascinating! Very nice analysis. Amazingly simple. Now, onto part II: If we rerank a multinomial distribution, what do we get? In general, what is the effect of reranking a distribution? –  user7593 Feb 28 '11 at 14:53
    
@Marcus: Is there a particular reason why you want to rerank it? I think the more pressing question now is to see if some known distribution arises from an appropriate limit $N \to \infty$ and $m\to\infty$, maybe keeping the ratio $m/N$ constant or something like that. –  Raskolnikov Feb 28 '11 at 18:54
    
@Rashkolnikov - the rank order came up from the application. But I think I solved it! Can you please check my answer/ –  user7593 Mar 1 '11 at 13:50
add comment

Got it! Unbelievable. The process of accumulating and then ranking is identical to simply computing the CDF, then reflecting over the y=x axis (taking the inverse)!!! P(Urn X has x balls) = M*Pareto(X). Let f(z) = $CDF^{-1}(M*Pareto(z))$. That means that (using frequentist terminology) n*z urns have less than f(z) balls.

So the final answer - to the original question without simplifying - is $n * CDF^{-1}(M*Pareto(x))$. (Or, to preserve the order I mentioned in the question, reflecting that over the y-axis).

I'm still a novice here, so can I ask you experts to verify or disprove this?

share|improve this answer
    
I see at least one mistake - P(Urn X has x balls) equals $M*Pareto^{-1}(x)$ (truncated to n). –  user7593 Mar 1 '11 at 14:23
add comment

Your Answer

 
discard

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