notwoodstock skrev:Lite undrande om det alltid är v53, varje år.

Nix, det är inte varje år.

Vecka 1 är alltid den vecka som har minst fyra dagar under januari, vecka 53 blir det bara om den veckan har minst fyra dagar i december.

Jag hittade på ett problem som kanske kan kallas matematisk men egentligen är ganska allmän. Den är enkel att förklara i alla fall, du har tre bollar. Låt oss säga en röd, grön och en blå. Oh så har du ett mynt. Du ska singla slant så att du väljer en boll. Varje boll ska såklart ha lika stor chans att väljas och du ska singla så få gånger som möjligt.

Jag har inte letat efter nån lösning på detta utan ville försöka själv. Så om ni vill leta efter nåt facit kan ni ju hålla det utanför ett tag iaf.

Här är mitt förslag. Jag tänkte simulera det i datorn för att få ett medelvärde på antal ggr man måste singla, återkommer.

Jag kallar klave = 0 och krona = 1 för enkelhetens skull

https://i.imgur.com/ljqpthE.jpg

Okej mitt medel blev 2,67092 baserat på 100000 körningar.

Om nån vill testa en metod kan jag koda och simulera det åt er

8/3 blir det förstås. Bevis?

nescio skrev:8/3 blir det förstås. Bevis?

Kan du utveckla?

wolframalpha.com säger:

Jag gjorde ett program själv och fick 2,6668 på 100 miljoner körningar.

Coolt, verkar stämma ja. Men undrar fortfarande om det finns nån bättre metod, med färre kast i medel. Har inte lyckats komma på nåt. Sen kan man också undra om det finns metoder som har högre medel men som planar ut lägre så att man kan förvänta sig färre kast när man har extrem otur.

Om vi tillåter oss att göra flera försök på en gång kan vi låta utfallen representeras en sträng i talbas 3 och sedan slumpa ett binärt tal mellan 0 och 3^n-1. Ett binärt tal kostar (grovt förenklat) ett kast per bit.

Låt oss säga att vi ska välja boll slumpmässigt 3 gånger i följd med återläggning. Det finns då 27 möjliga utfall.

Alla möjliga utfall räknas upp- och representeras av talen a*(3^2)+b*(3^1)+c*(3^0), där a,b och c är heltal [0,2], dvs

000, 001, 002, 010, 011, 012, 020, 021, 022 osv upp till talet 222 i talbas 3.

Att slumpa en sträng av 3 bollar kostar då "mindre" än 5 bitar (5 kast). Med din metod är kostnaden för strängen 8 kast (2.67*3) i snitt.

Att slumpa en sträng med 10 bollar kräver mindre än 16 kast (jämfört med 27) osv. Man måste dock kompensera "kanteffekter" om man vill bibehålla en helt "sann" binomialfördelning.

RapeRegs skrev:Att slumpa en sträng av 3 bollar kostar då "mindre" än 5 bitar (5 kast). Med din metod är kostnaden för strängen 8 kast (2.67*3) i snitt.

Jag har inte hunnit sätta mig in exakt i hur du tänkt, men medel för tre bollar är 2,67 för mig inte 3*2,67. Man har utfallen 00, 01, 10, 11 varje omgång. Chansen är 3/4 att klara sig med 2 kast, de första tre fallen. Sen kommer termen 0,6666... från att det är 3/16 chans att det blir 4 kast, och 3/64 chans att det blir 6 kast, 3/256 för 8 och så vidare i all oändlighet. Nämnaren gångras med 4 för varje term och antal kast ökar med 2. Skriver du upp utfallen så ser du det.

antor skrev:Jag har inte hunnit sätta mig in exakt i hur du tänkt, men medel för tre bollar är 2,67 för mig inte 3*2,67.

Nej, med tre bollar menar jag att du ska välja en boll i en serie av 3 omgångar. En sådan serie kan t.ex. vara 1 Röd boll, 1 Blå boll, 1 Blå boll.

Med din metod måste du utföra minst 2 kast för varje omgång, ibland fler. I snitt 2.67 kast per omgång. Väntevärdet är därför 3 * 8/3 = 8

Om Röd är 0, grön är 1 och blå är 2 så representeras utfallet [Röd, Blå, Blå] av talet 022 i bas 3, dvs talet 8 decimalt eller talet 1000 binärt (5 bitar). Är du med?

RapeRegs skrev:

antor skrev:Jag har inte hunnit sätta mig in exakt i hur du tänkt, men medel för tre bollar är 2,67 för mig inte 3*2,67.

Nej, med tre bollar menar jag att du ska välja en boll i en serie av 3 omgångar. En sådan serie kan t.ex. vara 1 Röd boll, 1 Blå boll, 1 Blå boll.

Med din metod måste du utföra minst 2 kast för varje omgång, ibland fler. I snitt 2.67 kast per omgång. Väntevärdet är därför 3 * 8/3 = 8

Om Röd är 0, grön är 1 och blå är 2 så representeras utfallet [Röd, Blå, Blå] av talet 022 i bas 3, dvs talet 8 decimalt eller talet 1000 binärt (5 bitar). Är du med?

Okej jag tror jag förstår hur du tänker. Men jag ska försöka översätta det till nåt praktiskt då så får du rätta mig om jag har fel. För att välja en boll tre gånger:

Utfall - Binärt
000 - 00000
001 - 00001
002 - 00010
010 - 00011
011 - 00100
012 - 00101
020 - 00110
021 - 00111
022 - 01000
100 - 01001
101 - 01010
102 - 01011
110 - 01100
111 - 01101
112 - 01110
120 - 01111
121 - 10000
122 - 10001
200 - 10010
201 - 10011
202 - 10100
210 - 10101
211 - 10110
212 - 10111
220 - 11000
221 - 11001
222 - 11010

Jag stöter på samma problem som jag gjorde själv, vilket du kanske redan vet. I mitt fall finns ett utfall som inte passar in och det var 11 och jag valde då att upprepa proceduren, vet ej om man kan göra nåt bättre. I ditt fall har vi för fem kast utfallen 11011, 11100, 11101, 11110, 11111 som inte är tilldelade någonting. Vad gör man i dessa fall om man sitter och använder metoden rent praktiskt? Om jag gör samma sak att jag upprepar, så får jag 5,92291 i medel baserad på en miljon tester. Det är bättre än 8 för tre bollar

Det borde gå att göra en allmän procedure för detta, där man väljer metod efter hur många bollar man vill välja. Ska testa det sen.

antor skrev:Chansen är 3/4 att klara sig med 2 kast, de första tre fallen. Sen kommer termen 0,6666... från att det är 3/16 chans att det blir 4 kast, och 3/64 chans att det blir 6 kast, 3/256 för 8 och så vidare i all oändlighet. Nämnaren gångras med 4 för varje term och antal kast ökar med 2. Skriver du upp utfallen så ser du det.

Med tre bollar och ett mynt krävs det 6 kast att alla tre bollarna blir valda. Men eftersom du skriver 8/3 antar jag att du är ute efter sannolikheten för att en boll blir vald dividerat med sannolikheten för att det blir krona-krona? Då stämmer din talföljd.

antor skrev:Om jag gör samma sak att jag upprepar, så får jag 5,92291 i medel baserad på en miljon tester. Det är bättre än 8 för tre bollar

Jättebra! Det teoretiska värdet är 160/27 eller om man så vill 1.98 bitar / boll (jämfört med 2.67 bitar per boll tidigare).

Som du noterar räcker det nu att "kasta bort" 5/32 istället för 1/4 av alla tal som genereras. Det går faktiskt att använda de överblivna talen i nästa runda (dynamisk programmering). Med lite hokuspokus kan man åtminstone komma upp i en effektivitet av 30/32 i snitt. Men dessa metoder blir snabbt mycket krångliga, särskilt om man vill bevara en strikt binomialfördelning och inte fuskar med lookuptables.

Betydligt enklare och mer effektivt är att anpassa strängens längd n till antal tärningskast m (antal bitar). För ett givet n blir m det minsta heltal som uppfyller



Om vi istället för 3 väljer att räkna på 5 omgångar, dvs n=5, m=8 får vi



Eller om man så vill 1.69 bitar / boll.

Det går naturligtvis att hitta bättre en anpassning än så, faktum är att det hela blir ett intressant minimeringsproblem som har ett vackert lägsta värde. I praktiken är dock 5 ett mycket bra val.

RapeRegs skrev:Som du noterar räcker det nu att "kasta bort" 5/32 istället för 1/4 av alla tal som genereras. Det går faktiskt att använda de överblivna talen i nästa runda (dynamisk programmering). Med lite hokuspokus kan man åtminstone komma upp i en effektivitet av 30/32 i snitt. Men dessa metoder blir snabbt mycket krångliga, särskilt om man vill bevara en strikt binomialfördelning och inte fuskar med lookuptables.

Varför binominalfördelning? Jag tolkar Antor som att alla bollar ska ha lika stor chans att väljas, inte som att den mittersta bollen ska ha mycket större chans än de två andra.

Vildsvin skrev:Varför binominalfördelning? Jag tolkar Antor som att alla bollar ska ha lika stor chans att väljas

Ja, det är korrekt. Det jag avsåg var att experimentet består av 1) ett fixt antal Bernoulliförsök som antingen ger utfallet 0 eller utfallet 1, båda med exakt samma sannolikhet samt 2) försöken är identiska och oberoende. Jag menar INTE att utfallet 110 är samma sak som 011.

Vid fallet med m=5, n=3 får vi t.ex. 2^5-3^3=5 ufall över, alla med _samma_ sannolikhet. Detta kan översättas till 2 äkta bitar (och ett överblivet utfall). Om vi ska försöka använda _alla_ överblivna utfall måste vi se till att algoritmen fortfarande ger ett resultat som har samma väntevärde för olika delsträngars förekomst och samma varians (bland annat).

Kopplingen till binomialfördelningen gör att vi kan använda redan färdiga formler för strängars väntevärde och varians när vi ska studera om en algoritm som "lånar" bitar från en omgång till en annan är väntevärdesriktig och inte biaserad.

Allmän orientering och bra start https://sv.wikipedia.org/wiki/Bernoullif%C3%B6rdelning

RapeRegs skrev:

Alltså jag vet inte vad jag ska säga. För du gör enkla saker väldigt invecklade, utan att komma fram till lösningen på själva matteproblemet.


En generell lösning om antalet val är förutbestämt är att multiplicera antaletBollar.* antaletVal och skapa ett slumptal som är mindre än närmast större tvåpotens.

Sen dividerar man slumptalet med närmast mindre potens av antaletBollar. Heltalsresten är numret på bollen som väljs. Multiplicera det med närmast mindre potens av antaletBollar och subtrahera det från slumptalet. Fortsätt så tills alla bollar är valda.

Vildsvin skrev:Alltså jag vet inte vad jag ska säga. För du gör enkla saker väldigt invecklade, utan att komma fram till lösningen på själva matteproblemet.

Det var tråkigt att du tycker att jag komplicerar i onödan. Kanske beror det på att vi pratar om helt olika saker. Den intressanta frågan är vad som är det lägsta antalet tärningskast som behövs per boll samtidigt som strängen man generar fortfarande är helt slumpmässig.

En generell lösning om antalet val är förutbestämt är att multiplicera antaletBollar.* antaletVal och skapa ett slumptal som är mindre än närmast större tvåpotens.

Sen dividerar man slumptalet med närmast mindre potens av antaletBollar. Heltalsresten är numret på bollen som väljs. Multiplicera det med närmast mindre potens av antaletBollar och subtrahera det från slumptalet. Fortsätt så tills alla bollar är valda.

Ja, förutom lite oklarheter verkar det här vara exakt den metod jag beskriver ovan och som TS redan implementerat. Det vi sedan pratar om är mer effektiva metoder där man drar nytta av eventuellt överblivna bitar i det genererade slumptalet eller hur man väljer strängens längd mer optimalt.

Kanske klarnar det om du förklarar vad du menar med "antaletBollar.* antaletVal". Hur stort tal (dvs hur många tärningskast) hade du t.ex. tänkt slumpa fram för fallet med en stränglängd 3 bollar (där varje boll kan väljas på tre olika sätt)?