Explosioner och hugg i matematiska träd
Man kan tänka sig ett matematiskt träd som ett släktträd med barn och förfäder. I sin avhandling studerar matematikern Cecilia Holmgren egenskaper för slumpmässiga så kallade ”splitträd” inom matematiken och introducerar också nya metoder för att undersöka den här typen av matematiska träd. Avhandlingen försvaras den 19 februari vid Uppsala universitet.
Urfadern i ett matematiskt släktträd med barn och förfäder är roten, som finns placerad högst upp i trädet. Ättlingarna befinner sig längre ned i trädet och kallas “noder” och noderna och deras närmaste förfader är förbundna med linjer som kallas “kanter”. Splitträd konstrueras genom att man delar ut ett visst antal bollar till noderna med hjälp av en slumpmässig splittningsprocess. Splitträd omfattar en stor klass av träd, där de flesta kommer från datavetenskap och där används som effektiva sökalgoritmer. Det mest kända och enklaste splitträdet är det binära sökträdet, som är lika gammalt som datavetenskapen själv.
Tillsammans med N. Broutin vid INRIA i Paris har Cecilia Holmgren undersökt ”explosioner” i splitträd. Med explosioner menas att trädet blåser upp till ett oändligt träd (exploderar). Explosionsproblem introducerades redan 1874 av Galton och Watson, som studerade sannolikheten för att familjer överlever (trädet exploderar) eller dör ut (trädet är ändligt). I explosionsproblem är man intresserad av under vilka betingelser som trädet går från att vara ändligt till oändligt.
– Våra resultat har direkta kopplingar till kommunikationskanaler, som till exempel radio, Internet, mobila nätverk eller satellitkanaler, som delas av flera användare. När flera användare sänder meddelanden samtidigt krockar dessa och informationen kan inte sändas korrekt. Man kan lösa detta problem genom att tänka sig användarna som bollar i ett splitträd, förklarar Cecilia Holmgren.
Genom att splittras och delas upp på olika tidsintervall kan användarna klara av att sända sina meddelanden utan kollisioner. Under tidens gång tillkommer nya användare. Dessa motsvaras av nya bollar som tillförs till splitträdet. Så länge trädet är ändligt så kan all information överföras inom en ändlig tid. Om trädet blir oändligt på grund för många nya användare så tar det oändligt lång tid att överföra meddelandena korrekt och kanalen är således inte användbar. I avhandlingen beskrivs under vilka förhållanden som kanalen är användbar.
I avhandlingen använde Cecilia Holmgren förnyelseteori som en ny metod för att karaktärisera splitträd. Förnyelseteori är ett delområde av sannolikhetsteori, som är anpassad till att studera summor av slumpmässiga värden. Ett klassiskt exempel är en glödlampa, som slocknar efter en slumpmässig tid och därefter ersätts med en ny varje gång den slocknar. Man är intresserad av hur många gånger lampan har bytts ut under en given tidslängd. I avhandlingen visas att förnyelseteori lämpar sig väl för studier av splitträd, och Cecilia Holmgren visar hur den kan tillämpas för att studera splittningsprocessen för hur bollarna fördelas till noderna, vilket innebär en övergripande beskrivning av hela splitträdets egenskaper.
I avhandlingen studeras också hur många slumpmässiga hugg som krävs för att hugga ner ett slumpmässigt splitträd. Huggningar av träd har tillämpningar i till exempel fysik. Slumpmässigt väljs en nod där hugget sker och noden samt dess ättlingar tas bort. Detta upprepas tills urfadern (roten) huggs. För splitträd är detta ett avancerat problem, eftersom både huggen och trädet man hugger i är slumpmässiga. Cecilia Holmgren visar att antalet hugg för allmänna splitträd får en stabil fördelning. Stabila fördelningar bildar en viktig klass av fördelningar, som bland annat innehåller normalfördelningen.
Kontaktinformation
För mer information kontakta Cecilia Holmgren, tel: 018-471 32 90, 0708-110 899,
e-post: cecilia.holmgren@math.uu.se
