gekleurde ballen [20+]

[wnvl]

Het lijkt erop dat dat naar verwachting gebeurt in stappen met 2 <= k <= n.

Hoe ben je daar op gekomen?

[wnvl]

http://math.stackexchange.com/questions ... same-color

Maar ik denk niet dat ik mij indertijd op bovenstaande heb gebaseerd. De link bevat trouwens geen oplossing.

Mogelijk heb ik mij op

https://www.google.be/url?sa=t&rct=j&q= ... 2980,d.d24

gebaseerd, maar die link werkt niet meer. Ik meen dat er een sluiten,de redenering was om de oplossing te bewijzen.

[David]

Dank je voor de links. Bij mij werken beide links. In de bovenste link wordt gespeculeerd over (n - 1)^2 als aantal stappen. Bewijs lijkt me nog sterk want volgens mij worden de resultaten gevonden door inspectie en alleen onderbouwd.
De onderste link vraagt me of ik een Pdf-bestand wil openen, maar de webpagina blijft wit. Doet hij dat bij jou? Anders kan ik hem je wellicht sturen. In dat bestand wordt bewezen dat het naar verwachting (n - 1)^2 'stappen' duurt voordat alle ballen dezelfde kleur hebben.

Hoe ben je daar op gekomen?

Inspectie. Ik had een matrix met vrij goede benaderingen, door het aantal iteraties, (~0.02 absoluut verschil van de schatting) van het aantal stappen om een kleur te verliezen als er nog k zijn.
Maar voor (n, k) = (7, 3) stond er bijv. 6.98 en voor (7, 2) bijv. 20.99. (n, 2) matched goed met etc.

[op=op]

Mogelijk heb ik mij op

https://www.google.be/url?sa=t&rct=j&q= ... 2980,d.d24

gebaseerd, maar die link werkt niet meer. Ik meen dat er een sluiten,de redenering was om de oplossing te bewijzen.

Die link werkt nog prima. Gebruik anders een andere browser, of nog beter, gooi windows het raam uit en stap over op linux.
De gegeven oplossing is alles behalve simpel te noemen.
En dat is toch wel jammer, want je had een elegante oplossing in het vooruitzicht gesteld.

[wnvl]

De onderste link vraagt me of ik een Pdf-bestand wil openen, maar de webpagina blijft wit. Doet hij dat bij jou? Anders kan ik hem je wellicht sturen. In dat bestand wordt bewezen dat het naar verwachting (n - 1)^2 'stappen' duurt voordat alle ballen dezelfde kleur hebben.

Als je aan die paper van Sergiu Hart kan, mag je hem me altijd sturen of even ergens anders zetten.
Ik kan hem niet openen.

[wnvl]

Die link werkt nog prima. Gebruik anders een andere browser, of nog beter, gooi windows het raam uit en stap over op linux.
De gegeven oplossing is alles behalve simpel te noemen.
En dat is toch wel jammer, want je had een elegante oplossing in het vooruitzicht gesteld.

Ik heb geprobeerd met Firefox en op Android, maar die website van de Hebreeuwse universiteit van Sergiu Hart is volgens mij verdwenen.

Ik heb op mijn bureau ook nog een Linux Mint versie staan, maar bij mij is dat veel minder stabiel dan Windows.Maar het gaat over een oude pc gerecupereerd om Linux op te installeren.

Ik herinner mij inderdaad een elegante oplossing, maar het is ook lang geleden. Ik weet ook niet zeker of ik het hier vandaan gehaald had. Het kan ook zijn dat ik mij gebaseerd heb op een paper of het boek van Philippe Flajolet. Hij is gestorven en dat boek is intussen verdwenen.

[op=op]

https://dl.dropboxusercontent.com/u/300 ... lors_1.pdf

[op=op]

Probeer anders Lubuntu of elementary OS, dat ik regelmatig op een oude pc gebruik.
Daar heb ik nooit problemen mee.

[wnvl]

Bedankt!

Ubuntu blokkeerde bij de installatie.
elementary OS had ik nog nooit van gehoord. Dat is trouwens wel een vervelend aspect van Linux dat je zoveel varianten hebt.

Ik denk niet dat ik toen die paper van Hart gelezen had. Ik had de oplossing van ergens anders.
Die relatief eenvoudig van hierboven, die trek ik wel terug. Met die 20+ bedoelde ik toen ook dat het niet voor secundair bedoeld was.

Er is trouwens iets wat ik niet begrijp onderaan p2, die genummerde vgl (1)

Waar kom die

"+ 1 · P(Ai|k)"

vandaan?

Dat ontbrak ook in jou eerste aanzet en ik kan dat niet plaatsen.

[op=op]

Er is trouwens iets wat ik niet begrijp onderaan p2, die genummerde vgl (1)

Waar kom die

"+ 1 · P(Ai|k)"

vandaan?

Die term kan ik ook niet plaatsen. Ik ben ook helemaal niet thuis in Markov ketens.

Ik had het trouwens over Lubuntu, niet over Ubuntu.
Lubuntu stelt minder eisen aan de pc.
Als het een laptop betreft is er ook een Ubuntu versie speciaal voor oudere laptops,
ubuntu netbook remix 9.10.

Het boek van Philippe Flajolet. Hij is gestorven en dat boek is intussen verdwenen.

Ik had nog nooit van de goede man gehoord. Zijn boek "Analytic combinatorics" is gratis op het internet te downloaden. Ik heb het heruntergeladen (om eens een ander woord te gebruiken).

[David]

Hieronder staan transitiematrices voor bakken met n = 2 tot en met 7 ballen met de bijbehorende partities van n. Voor als iemand hier verder onderzoek naar wil doen, daaronder de code. De code is voor PARI/gp: http://pari.math.u-bordeaux.fr/, en er daarin verder worden gerekend met wat je vindt. Ik ben benieuwd naar eventueel verder resultaat (Bijvoorbeeld, ik vraag me af wat de kans is dat, van twee willekeurige partities, het aantal mogelijkheden om van de ene partitie naar de andere te gaan in één stap, oneven is).

In de matrices staan elementen die kansen op overgangen voorstellen. Rij a en kolom a corresponderen met partitie a. Dus, een element uit de matrix geeft de kans om van de partitie bij de rij naar de partitie bij de kolom te gaan (gegeven een bak ballen te beschrijven als de partitie bij die rij).

Bijvoorbeeld, stel er zijn 5 ballen. bij rij 4 en kolom 2 staat 3/10. Bij rij 4 'hoort' partitie 1 + 1 + 3. Bij partitie 2 hoort partitie 1 + 4. Dit betekent dat als er drie verschillende kleuren zijn, met twee kleuren die elk één keer voorkomen en een kleur die drie keer voorkomt, de kans 3/10 is dat als je twee (verschillende!) ballen trekt, en de eerste de kleur van de tweede geeft, de kans 3/5 is dat er daarna nog twee kleuren over zijn waarvan een kleur 1 keer voorkomt en de andere vier keer.

Als er n ballen zijn, kan je op n(n-1) manieren twee verschillende ballen trekken waar volgorde telt. Met n = 5 zijn dat 20 manieren. Stel, we nummeren de ballen 1 tot en met n, en [a, b] betekent: trek bal a en bal b. Geef bal a de kleur van bal b.
Dan zijn de manieren uit de situatie hierboven:
Trek bal 1 of bal 2 als eerst en dan bal 3, 4 of 5.
Ofwel [a, b] in {[1, 3], [2, 3], [1, 4], [2, 4], [1, 5], [2, 5]}.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2 = 1 + 1


3 = 1 + 2 = 1 + 1 + 1


4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1


5 = 1 + 4 = 2 + 3 = 1 + 1 + 3 = 1 + 2 + 2 = 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1


6 = 1 + 5 = 2 + 4 = 3 + 3 = 1 + 1 + 4 = 1 + 2 + 3 = 2 + 2 + 2 = 1 + 1 + 1 + 3 = 1 + 1 + 2 + 2 = 1 + 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1 + 1


7 = 1 + 6 = 2 + 5 = 3 + 4 = 1 + 1 + 5 = 1 + 2 + 4 = 1 + 3 + 3 = 2 + 2 + 3 = 1 + 1 + 1 + 4 = 1 + 1 + 2 + 3 = 1 + 2 + 2 + 2 = 1 + 1 + 1 + 1 + 3 = 1 + 1 + 1 + 2 + 2 = 1 + 1 + 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1 + 1 + 1

Code: Selecteer alles

addhelp(transitiematrix, "De transitiematrix voor een bak met n ballen")
transitiematrix(n) = {my(m, j = 1);
parts = partitions(n); \\non-private. 
m = matrix(#parts, #parts);
\\table is een tabel waarvan element i de kleur van bal i geeft.
table = vector(#parts);
\\borders geeft elementen waarvan de eerste partitie zijn aantal termen heeft. Om het laatste element ook te vinden, 
\\doen er ook een partitie is met n + 1 termen.  
borders = vector(n+1);
for(i=1,#parts,table[i]=PartitionToBox(parts[i],n));
\\borders geeft de plaatsen van de eerste partitie met 1 term, met 2 termen, 
\\maar ook een 'fantoom' de eerste met n+1 termen, die waarde #parts + 1 heeft. 
\\~~> initialiseer 'borders' (voor functie 'newboxnr'). 
for(i=1,#parts,
	if(#parts[i]==j,borders[j]=i;j++)
);borders[n+1]=#parts+1;

\\voor alle partities (=toestanden)
for(j=1,#parts,
        \\Voor alle ballen, trek die bal
	for(oo=1,n,
                \\trek een bal met een lager nummer dan de vorige
		for(nn=1,oo-1,
                      \\Wat had je gekregen als je de eerste bal de kleur van de tweede had gegeven?
			k=newboxnr(j,nn,oo);
			m[j,k]++;
                       \\Wat als de tweede de kleur van de eerste kreeg?
			k=newboxnr(j,oo,nn);
			m[j,k]++
		)
	)
);
\\geeft de transitiematrix terug. Als je het aantal mogelijkheden wil, vervang de regel hieronder door 'm'. 
m/n/(n-1)
}

addhelp(PartitionToBox, "Van v, een partitie van n als vector, maak de box die het representeert, als vector.") 
\\Bijvoorbeeld, partitie [1,1,3] (van 5, de som van de elementen) is een
\\box met ballen in kleuren [1, 2, 3, 3, 3]; 1 bal in kleur 1, 1 bal in kleur 2 en 3 ballen in kleur 3.
PartitionToBox(v,{n=vecsum(v)}) = {my(r = vector(n),i=0);
for(j=1,#v,
	for(k=1,v[j],
		i++;
		r[i]=j	
	)
);r
}

addhelp(newboxnr, "Van partitie met nummer 'part', geef bal 'old' de kleur van bal 'nieuw' en zoek het nummer wat hoort bij de partitie van de nieuwe partitie.")
newboxnr(part,old,new) = {my(newbox=parts[part],npart=parts[part],qterms=#parts[part],addzero,i);
newbox[table[part][old]]--;
newbox[table[part][new]]++;newbox=vecsort(newbox);
\\Is er een kleur verdwenen? We concateneren een vector met een partitie uit de lijst. Welke bepalen we hieronder.
if(newbox[1]==0,qterms--;addzero=Vecsmall(0),addzero=Vecsmall([]));
\\zoek de partitie op die hoort bij de nieuwe box. (aantal termen 
for(i=borders[qterms],borders[qterms+1]-1,\\#parts,	
	if(newbox==concat(addzero,parts[i]),return(i))
);
}

[wnvl]

Wat bovenstande vergelijking (1) uit de paper betreft. Die vergelijking (1) is een differentie vergelijking voor het verwacht aantal stappen met als bijkomende voorwaarde dat in bovenstaande vergelijking gedefinieerd als 0 als kleur i uit de bak verdwijnt.

Daarom dat in die vergelijking (1) de 1 (die correspondeert met een extra stap in het proces) vermenigvuldigd moet worden met de kans dat in de eindsituatie alleen maar ballen van kleur i voorkomen. Zoniet is die toch gelijk aan nul.

In het bewijs van Lemma 3 in de paper komt iets gelijkaardigs (maar eenvoudiger) voor. Je vermenigvuldigt het aantal stappen met de kans dat je in de desbetreffende situatie zit.

Geen scherpe uitleg van mij, maar het stelt mij wel in staat om die bijkomende term iets of wat te kunnen vatten.

De rest van het bewijs is wat rekenen, de moeilijkheid is duidelijk die vergelijking voor opstellen en vooral dan het idee om gelijk te stellen aan nul.

[op=op]

Daarom dat in die vergelijking (1) de 1 (die correspondeert met een extra stap in het proces) vermenigvuldigd moet worden met de kans dat in de eindsituatie alleen maar ballen van kleur i voorkomen. Zoniet is die toch gelijk aan nul.

Het zal aan mij liggen, maar ik vat het niet.

Apropos, de afbeelding in map public zetten, en in rechtermuis menu
voor dropbox>copy public link... kiezen en het adres zit in het clipboard.

[wnvl]

Ik zag het wat die afbeelding betreft.
Ik krijg deze link. Op zich werkt die, maartussen die img tags wordt het inderdaad niet weergegeven.

https://www.dropbox.com/s/42jhesg9jbsaf ... r.jpg?dl=0

een map public heb ik wel niet. Ik heb nochthans vroeger ook al veel figuren gedeeld, maar het lukt niet meer.

Wat de grond van het probleem betreft, ik zoek nog wel eens naar een scherpere uitleg.

[op=op]

Maak dan zelf een map Public. Stop er iets in. Ga dan naar de dropbox website. Kijk in de map Public. Gebruik dan rechter muis knop en er zal Copy public link... bij staan.