Esta no es una tarea, aunque parece. Cualquier referencia es bienvenida. :-)
Escenario: Hay bolas diferentes y contenedores diferentes (etiquetados de 1 a , de izquierda a derecha). Cada bola se lanza de manera independiente y uniforme en los contenedores. Sea el número de bolas en el -ésimo contenedor. Deje denotar el siguiente evento.
Para cada ,
Es decir, los primeros contenedores (los contenedores más a la izquierda ) contienen menos de bolas, para cada .
Pregunta: Estima , en términos de ? Cuando va al infinito. Se prefiere un límite inferior. No creo que exista una fórmula fácil de calcular.
Ejemplo: . Nota.
Mi suposición: supongo que , cuando va al infinito. Mientras yo contemplaba los primeros elementos de la suma.
reference-request
co.combinatorics
pr.probability
Peng Zhang
fuente
fuente
Respuestas:
EDITAR: (2014-08-08) Como Douglas Zare señala en los comentarios, el argumento a continuación, específicamente el 'puente' entre las dos probabilidades, es incorrecto. No veo una forma directa de solucionarlo. Dejaré la respuesta aquí porque creo que todavía proporciona algo de intuición, pero sé que no es cierto en general.
Esta no será una respuesta completa, pero con suerte tendrá suficiente contenido para que usted o alguien más conocedor que yo pueda terminarlo.
Considere la probabilidad de que exactamente bolas caigan en los primeros l (de n ) contenedores:k l n
Calcule la probabilidad de que menos de bolas caigan en los primeros l contenedores F l :l l Fl
La probabilidad de que ocurra el evento, , anterior es menor que si consideramos cada uno de los F lEl Fl eventos ocurren independientemente y todos a la vez. Esto nos da un puente entre los dos:
Donde es lafunción de distribución acumulativa para la distribución binomialconp=lF(l−1;n,ln) . Simplemente leyendo unas pocas líneas en la página de Wikipedia y notando que(l-1≤pn), podemos usarla desigualdad de Chernoffpara obtener:p=ln (l−1≤pn)
Donde es el número armónico m ' , γ es la constante de Euler-Mascheroni y la desigualdad para el HHm m γ se toma de la página enlazada MathWorld de Wolfram.Hm
No preocuparse por ele−1/4m de factores, esto finalmente nos da:
A continuación se muestra un gráfico log-log de un promedio de 100,000 instancias para en función de m con la función e - γ / 2n=2048 m también trazado para referencia:e−γ/2m√
Mientras las constantes están desactivadas, la forma de la función parece ser correcta.
A continuación se muestra un gráfico log-log para variar siendo cada punto el promedio de 100,000 instancias en función de m :n m
Finalmente, llegamos a la pregunta original que quería que contestara, ya que sabemos que tenemos:Pr(Em)∝1m√
Y como verificación numérica, a continuación se muestra un gráfico log-log de la suma, , frente al tamaño de la instancia, n . Cada punto representa el promedio de la suma de 100,000 instancias. La función x 1 / 2 se ha trazado para la referencia:S n x1/2
Si bien no veo una conexión directa entre los dos, los trucos y la forma final de este problema tienen muchos puntos en común con el problema de cumpleaños, como se adivinó inicialmente en los comentarios.
fuente
The answer isΘ(n−−√) .
First, let's computeEn−1 .
Let's suppose we thrown balls into n bins, and look at the probability that a bin has exactly k balls in it. This probability comes from the Poisson distribution, and as n goes to ∞ the probability that there are exactly k balls in a given bin is 1e1k! .
Now, let's look at a different way of distributing balls into bins. We throw a number of balls into each bin chosen from the Poisson distribution, and condition on the event that there aren balls total. I claim that this gives exactly the same distribution as throwing n balls into n bins. Why? It is easy to see that the probability of having kj balls in the j th bin is proportional to ∏nj=11kj! in both distributions.
So let's consider a random walk where at each step, you go fromt to t+1−k with probability 1e1k! . I claim that if you condition on the event that this random walk returns to 0 after n steps, the probability that this random always stays above 0 is the probability that the OP wants to calculate. Why? This height of this random walk after s steps is s minus the number of balls in the first s bins.
If we had chosen a random walk with a probability of12 of going up or down 1 on each step, this would be the classical ballot problem, for which the answer is 12(n−1) . This is a variant of the ballot problem which has been studied (see this paper), and the answer is still Θ(1n) .
I don't know whether there is an easy way to compute the constant for the Θ(1n) for this case.
The same paper shows that when the random walk is conditioned to end at heightk , the probability of always staying positive is Θ(k/n) as long as k=O(n−−√) . This fact will let us estimate Es for any s .
I'm going to be a little handwavy for the rest of my answer, but standard probability techniques can be used to make this rigorous.
We know that asn goes to ∞ , this random walk converges to a Brownian bridge, i.e., Brownian motion conditioned to start and end at 0 . From general probability theorems, for ϵn<s<(1−ϵ)n , the random walk is roughly Θ(n−−√) away from the x -axis. In the case it has height t>0 , the probability that it has stayed above 0 for the entire time before s is Θ(t/s) . Since t is likely to be Θ(n−−√) when s=Θ(n) , we have Es≈Θ(1/n−−√) .
fuente
[Edit 2014-08-13: Thanks to a comment by Peter Shor, I have changed my estimate of the asymptotic growth rate of this series.]
My belief is thatlimn→∞∑i<nPr(Ei) grows as n−−√ . I do not have a proof but I think I have a convincing argument.
LetBi=f(i) be a random variable that gives the number of balls in bin i . Let Bi,j=∑jk=iBk be a random variable that gives the total number of balls in bins i through j inclusive.
You can now writePr(Ei)=∑b<jPr(Ej∧B1,j=b)Pr(Ei∣Ej∧B1,j=b) for any j<i . To that end, let's introduce the functions π and gi .
We can writePr(Ei) in terms of gi :
Now, it's clear from the definition ofgi that
wherehi(n) is a polynomial in n of degree i−1 . This makes some intuitive sense too; at least n−i+1 balls will have to be put in one of the (i+1) th through n th bins (of which there are n−i ).
Since we're only talking aboutPr(Ei) when n→∞ , only the lead coefficient of hi(n) is relevant; let's call this coefficient ai . Then
How do we computeai ? Well, this is where I'll do a little handwaving. If you work out the first few Ei , you'll see that a pattern emerges in the computation of this coefficient. You can write it as
Now, I wasn't able to derive a closed-form equivalent directly, but I computed the first 20 values ofPr(Ei) :
Now, it turns out that
wherePois(i;λ) is the probability that a random variable X has value i when it's drawn from a Poisson distribution with mean λ . Thus we can write our sum as
Wolfram Alpha tells me this series diverges. Peter Shor points out in a comment that Stirling's approximation allows us to estimatePr(Ei) :
Let
Since
our series grows as∫n1ϕ(x)dx (See e.g. Theorem 2). That is,
fuente
Exhaustively checking the first few terms (by examining all n^n cases) and a bit of lookup shows that the answer is https://oeis.org/A036276 /nn . This implies that the answer is ∼n12π√2 .
More exactly, the answer is:
fuente