Lanzar bolas en contenedores, estimar un límite inferior de su probabilidad

14

Esta no es una tarea, aunque parece. Cualquier referencia es bienvenida. :-)

Escenario: Hay bolas n diferentes y contenedores n diferentes (etiquetados de 1 a n , de izquierda a derecha). Cada bola se lanza de manera independiente y uniforme en los contenedores. Sea f(i) el número de bolas en el i -ésimo contenedor. Deje Ei denotar el siguiente evento.

Para cada ji , kjf(k)j1

Es decir, los primeros j contenedores (los j contenedores más a la izquierda ) contienen menos de j bolas, para cada ji .

Pregunta: Estima i<nPr(Ei) , en términos de n ? Cuando n va al infinito. Se prefiere un límite inferior. No creo que exista una fórmula fácil de calcular.

Ejemplo: limnPr(E1)=limn(n1n)n=1e . NotaPr(En)=0.

Mi suposición: supongo que i<nPr(Ei)=lnn , cuando n va al infinito. Mientras yo contemplaba los primeros lnn elementos de la suma.

Peng Zhang
fuente
1
Parece un subcase del problema de cumpleaños ...
Gopi
@Gopi No puedo convencerme de que mi pregunta es un problema restringido de cumpleaños. ¿Puedes explicarlo explícitamente? Muchas gracias. Nota: La restricción está en la suma de bolas en los primeros contenedores, no en el número de contenedores en un contenedor específico. j
Peng Zhang
De hecho, mi error, después de volver a leer el artículo de Wikipedia sobre el problema del cumpleaños, me di cuenta de que estaba considerando otro problema que se adaptó del problema del cumpleaños.
Gopi
2
Algunas ideas incorrectas ... Por lo tanto, piense en cómo codificar un estado: lea los contenedores de izquierda a derecha. Si el primer contenedor tiene i bolas, genere una secuencia de i ones, seguido de un 0. Haga esto para todos los contenedores de izquierda a derecha. Su codificación parece ser que está interesado en el i mayor, de modo que esta cadena binaria (que tiene n ceros yn unos) por primera vez contiene más unos que ceros. Ahora, vamos a hacer un salto de destino y generar el 0 y 1, con igual probabilidad . (Esto podría ser una completa tontería). Este problema está relacionado con los números catalanes y las palabras Dyck. Y...??? 1/2
Sariel Har-Peled
44
No veo en su definición por qué importa que las bolas sean diferentes. Además, la interpretación de la cadena tiene en cuenta el hecho de que los contenedores son diferentes.
Sariel Har-Peled

Respuestas:

11

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.

Pr(Em)l=1mPr(Fl)

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:kln

(nk)(ln)k(nln)nk

Calcule la probabilidad de que menos de bolas caigan en los primeros l contenedores F l :llFl

Pr(Fl)=k=0l1(nk)(ln)k(nln)nk

La probabilidad de que ocurra el evento, , anterior es menor que si consideramos cada uno de los F lElFl eventos ocurren independientemente y todos a la vez. Esto nos da un puente entre los dos:

Pr(Em)l=1mPr(Fl)=l=1m(k=1l1(nk)(lnk)(nln)nk)=l=1mF(l1;n,ln)

Donde es lafunción de distribución acumulativa para la distribución binomialconp=lF(l1;n,ln) . Simplemente leyendo unas pocas líneas en la página de Wikipedia y notando que(l-1pn), podemos usarla desigualdad de Chernoffpara obtener:p=ln(l1pn)

Pr(Em)l=1mexp[12l]=exp[12l=1m1l]=exp[12Hm]exp[12(12m+ln(m)+γ)]

Donde es el número armónico m ' , γ es la constante de Euler-Mascheroni y la desigualdad para el HHmmγ se toma de la página enlazada MathWorld de Wolfram.Hm

No preocuparse por el e1/4m de factores, esto finalmente nos da:

Pr(Em)eγ/2m

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=2048m también trazado para referencia:eγ/2m

enter image description here

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 :nm

enter image description here

Finalmente, llegamos a la pregunta original que quería que contestara, ya que sabemos que tenemos:Pr(Em)1m

i<nPr(Ei)n

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:Snx1/2

enter image description here

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.

usuario834
fuente
44
¿Cómo se obtiene ? Por ejemplo, para n = 100 , calculo que P r ( E 2 ) = 0.267946 > 0.14761 = P r ( F 1 ) P r ( F 2 ) .Pr(E2)Pr(F1)×Pr(F2)n=100Pr(E2)=0.267946>0.14761=Pr(F1)Pr(F2). Si le dicen que el primer contenedor está vacío, ¿esto hace que sea más o menos probable que los dos primeros contenedores tienen como máximo 1 ball? It's more likely, so Pr(F1)Pr(F2) is an underestimate.
Douglas Zare
@DouglasZare, I've verified your calculations, you're correct. Serves me right for not being more rigorous.
user834
15

The answer is Θ(n).

First, let's compute En1.

Let's suppose we throw n 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 are n 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 jth bin is proportional to j=1n1kj! in both distributions.

So let's consider a random walk where at each step, you go from t to t+1k 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 of 12 of going up or down 1 on each step, this would be the classical ballot problem, for which the answer is 12(n1). 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 height k, 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 as n 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).

Peter Shor
fuente
4

[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 that limni<nPr(Ei) grows as n. I do not have a proof but I think I have a convincing argument.

Let Bi=f(i) be a random variable that gives the number of balls in bin i. Let Bi,j=k=ijBk be a random variable that gives the total number of balls in bins i through j inclusive.

You can now write Pr(Ei)=b<jPr(EjB1,j=b)Pr(EiEjB1,j=b) for any j<i. To that end, let's introduce the functions π and gi.

π(j,k,b)=Pr(Bj=kB1,j1=b)=(nbk)(1nj+1)k(njnj+1)nbk

gi(j,k,b)=Pr(EiBj,ikEj1B1,j1=b)={0k<01k>=0j>il=0jb1π(j,l,b)gi(j+1,kl,b+l)otherwise

We can write Pr(Ei) in terms of gi:

Pr(Ei)=gi(1,i1,0)

Now, it's clear from the definition of gi that

Pr(Ei)=(ni)ni+1nnhi(n)

where hi(n) is a polynomial in n of degree i1. This makes some intuitive sense too; at least ni+1 balls will have to be put in one of the (i+1)th through nth bins (of which there are ni).

Since we're only talking about Pr(Ei) when n, only the lead coefficient of hi(n) is relevant; let's call this coefficient ai. Then

limnPr(Ei)=aiei

How do we compute ai? 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

ai=μi(1,i1,0)
where
μi(j,k,b)={0k<01k>=0i>jl=0jb11l!μi(j+1,kl,b+l)otherwise

Now, I wasn't able to derive a closed-form equivalent directly, but I computed the first 20 values of Pr(Ei):

N       a_i/e^i
1       0.367879
2       0.270671
3       0.224042
4       0.195367
5       0.175467
6       0.160623
7       0.149003
8       0.139587
9       0.131756
10      0.12511
11      0.119378
12      0.114368
13      0.10994
14      0.105989
15      0.102436
16      0.0992175
17      0.0962846
18      0.0935973
19      0.0911231
20      0.0888353

Now, it turns out that

Pr(Ei)=iii!ei=Pois(i;i)

where Pois(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

limni=1nPr(Ei)=x=1xxx!ex

Wolfram Alpha tells me this series diverges. Peter Shor points out in a comment that Stirling's approximation allows us to estimate Pr(Ei):

limnPr(Ex)=xxx!ex12πx

Let

ϕ(x)=12πx

Since

  • limxϕ(x)ϕ(x+1)=1
  • ϕ(x) is decreasing
  • 1nϕ(x)dx as n

our series grows as 1nϕ(x)dx (See e.g. Theorem 2). That is,

i=1nPr(Ei)=Θ(n)
ruds
fuente
1
Wolfram Alpha is wrong. Use Stirling's formula. It says that, xx/(x!ex)1/2πx.
Peter Shor
@PeterShor Thanks! I've updated the conclusion thanks to your insight, and now I am in agreement with the other two answers. It's interesting to me to see 3 quite different approaches to this problem.
ruds
4

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:

n!2nnk=0n2nkk!
and there is no closed-form answer.
Haran
fuente
Oeis is pretty awesome
Thomas Ahle