Die Arbeit behandelt die Verwendung von Markov-Erneuerungstheorie in der Analyse von zufälligen Strings und verwandten Baumstrukturen, sowie iterierten Funktionensystemen. Die Modelle beinhalten Markov-Modulation durch eine positiv rekurrente diskrete Markov-Kette. Teil I untersucht Baumstrukturen, insbesondere Tries, die in der Analyse von Algorithmen auftreten und aus zufälligen Strings konstruiert werden. Ein String wird von einer Markov Source erzeugt, bildet also eine Markov-Kette und gleichzeitig die Steuerkette eines Markov-modulierten Hilfsprozesses. Wir bestimmen in der ersten Hälfte das Grenzverhalten charakteristischer Parameter wie Tiefe und Imbalance Factor, und entwickeln in der zweiten Hälfte ein Resultat für die Average-Case Analyse weiterer charakteristischer Parameter. Teil II untersucht iterierte Funktionensystem aus Markov-modulierten Lipschitz-stetigen Funktionen. Wir betten unser Modell ein in das stationäre Regime von Elton, und geben Bedingungen für polynomielle und geometrische Konvergenz.