MIN-MAX trees have been studied for thirty years as models of game trees in artificial intelligence. Judea Pearl introduced a popular probabilistic model that assigns random independent and identically distributed values to the leaves. Among the dependent models, incremental models assume that terminal values are computed as sums of edge values on the path from the root to a leaf. We study a special case called the scSUM model where the edge values follow a Bernoulli distribution with mean p. Let $V sb{n}$ be the root's value of a complete b-ary, n-level scSUM tree. We prove the E$V sb{n}$/n tends to a uniformly continuous function ${ cal V}(p)$. Surprisingly, ${ cal V}(p)$ is very nonlinear and has some flat parts. More formally, for all b, there exist $ alpha, beta in$ (0, 1) such that, cases{${ rm if} p in lbrack0, alpha rbrack$&:E$V sb{n}$ has a finite limit cr ${ rm if} p in lbrack1- alpha,1 rbrack$&:$n-{ rm E}V sb{n}$ has a finite limit cr ${ rm if} p in lbrack beta,1- beta rbrack$&:E$V sb{n}/n$ tends to 1/2 cr} inally $ beta$ and $ alpha$ tend to zero when b tends to infinity.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.57007 |
| Date | January 1992 |
| Creators | Kamoun, Olivier |
| Contributors | Devroye, Luc (advisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 001326485, proquestno: AAIMM87758, Theses scanned by UMI/ProQuest. |
Page generated in 0.0013 seconds