Границы Пуассона и Мартина для двумерных случайных блужданий тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Куркова, Ирина Анатольевна

• Куркова, Ирина Анатольевна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Куркова, Ирина Анатольевна

Оглавление

Введение

0.1. Случайные блуждания в Ъ\ Ъ л (г+)2

1. Граница Пуассона

1.1. Основные определения

1.2. Граница Пуассона для случайных блужданий в г2,

и (г+)2

1.3. Обобщения для случайных блужданий в {Ъ+)к xZraи (2+)п

2. Граница Мартина

2.1. Основные определения

2.2. Результаты

2.2.1. Необходимые утверждения

2.2.2. Случайное блуждание в Т?

2.2.3. Случайное блуждание в Ъ х Ъ+\ Ех > О, Еу > 0

2.2.4. Случайное блуждание в Z х Е^ < О, Еу < 0

2.2.5. Случайное блуждание в (2+)2: Еж > О, Еу > 0

2.2.6. Случайное блуждание в (%+)2: Еж < О, Еу < 0, уход

на бесконечность по одной оси

2.2.7. Случайное блуждание в (Я+)2: Ех < д^^^Ь^ход

на бесконечность по двум осям

2.3. Доказательства

2.3.1. Общая схема доказательств

2.3.2. Случай Ъ2

2.3.3. Случай Ъ х Ех > О, Еу > 0

2.3.4. Случай г+ х Ъ: Ех < О, Еу < 0

2.3.5. Случай (г+)2: Ех > О, Еу > 0

2.3.6. Случай Ех < 0, Еу < 0, уход на бесконечность по одной оси

2.3.7. Случай (г+)2: Ех < 0, Еу < 0, уход на бесконечность по двум осям

3. Скорость сходимости к границе

3.1. Бесконечночастичная модель и результат

3.2. Доказательство

Литература

Введение диссертации (часть автореферата) на тему «Границы Пуассона и Мартина для двумерных случайных блужданий»

Введение

Одной из важнейших задач в исследовании транзиентных цепей Маркова является нахождение границ Пуассона и Мартина. С одной стороны, ее решение позволяет описать "финальное поведение" процесса и "различать" "предельные точки" траекторий. С другой стороны, оно дает интегральное представление всех ограниченных гармонических функций в случае границы Пуассона, и, более того, всех неотрицательных гармонических функций в случае границы Мартина.

Интегральное представление послужило мотивом для создания теории границ Мартина в 1941 году. Мартин в [43] исследовал множество положительных решений уравнения Лапласа в области евклидова пространства.

Компактификация Мартина была введена Дубом [27] и Хантом [35]. Это пополнение X* пространства состояний X транзиентной цепи в метрике, зависящей от асимптотики функции Грина. Тогда граница Мартина есть дХ = Х*/Х. Дуб в [27] дал вероятностную интерпретацию результатов Мартина: непосредственные выводы относились к вине-ровскому процессу, но Дуб показал возможность их распространения на счетные дискретные цепи. В его работе сначала невероятностными методами вводится интегральное представление гармонических функций, а затем из него вытекает теорема о финальном поведении траекторий. Новый подход был предложен Хантом в [35]: сначала из вероятностных соображений доказывается теорема о финальном поведении, а после этого, с помощью /г-процесса, выводится интегральное представление. Эта теория получила дальнейшее развитие в работе Дынкина [2].

Интегральное представление гармонических функций вдоль дХ не единственно. Чтобы добиться единственности, надо исключить из дХ некоторые точки. Полученное множество называется в [2] пространством выходов, или в других работах [38, 49, 51] — минимальной границей Мартина.

Для определении границы Пуассона в настоящий момент существует много подходов, они изложены в [31, 36, 37, 50].

Перечислим работы, в которых были исследованы границы Пуассона и Мартина для случайных блужданий на графах и группах. В [28] найдена минимальная граница Мартина для случайных блужданий в Ъ\ она состоит не более, чем из двух точек. Однако неминимальная граница может быть шире, как показывает пример в [19], § 7. Анализ гармонических функций для случайных блужданий размерности А > 1 был начат в [34] и [20]. Ней и Спицер в [44] и Спицер в [11] нашли границу Мартина для пространственно одонородных случайных блужданий в

¿> 2, если экспоненциальный момент скачка за один шаг конечен. В [44] рассмотрен случай, когда средний скачок за один шаг отличен от нуля: доказано, что граница Мартина гомеоморфна сфере. В [11] рассмотрен случай нулевого среднего скачка: граница Мартина тогда состоит из одной точки. В обоих перечисленных случаях граница Пуассона тривиальна, что доказано, например, в [17]. В работе [16] эти результаты обобщаются на случай Р1А Гармонические функции для блужданий на нильпотентных группах исследованы в [9]. Граница Мартина для случайных блужданий на свободных группах была определена в [3] и позже изучалась в [24].

Отметим также, что в некоторых работах решается обратная задача: нахождение цепи, для которой заданное множество является границей Мартина. Так, например, в [23] определяется цепь, для которой границей Мартина является ковер Серпинского.

В ряде работ компактификация Мартина сравнивается с другими возможными компактификациями пространства. Для случайных блужданий на деревьях вводится компактификацию концов. Пути, имеющие лишь конечное число различных вершин, объявляются эквивалентными. Классы эквивалентности называются концами. Они пополняют пространство вершин в некоторой метрике. В [18, 19, 46] доказывается совпадение компактификации Мартина с компактификацией концов при некоторых наложенных условиях. В [32] рассматриваются гиперболические графы и их возможная компактификация, называемая гиперболической. В [15] доказывается ее совпадение с компактификацией Мартина. Работа [33] посвящена возможным пополнениям симметричных пространств и их взаимосвязи. В ней, в частности, подробно изучается компактификация Мартина для случайных блужданий на симметричных пространствах.

В [47] исследуется граница Мартина декартова произведения двух марковских цепей. Декартово произведение позволяет построить простые примеры, в которых граница Мартина шире минимальной границы, как, например, в [48]

Наконец, необходимо отметить работы [26] и [36], в которых речь идет о связи границы Пуассона с энтропией. В частности, для случайного блуждания на группе с конечной энтропией и неприводимой мерой граница Пуассона тривиальна, если и только если энтропия равна нулю. Этот результат доказан в [5, 25, 36]. Другие критерии тривиальности границы Пуассона и многочисленные примеры приведены в [37].

Мы видим, что в большинстве работ речь идет об исследовании границ для однородных блужданий на группах, деревьях, симметрических пространствах. Мы рассматриваем неоднородные блуждания в кону-

сах решетки. В данной работе найдены границы Пуассона и Мартина для транзиентных случайных блужданий в плоскости в полуплоскости Ъ х Х+ и в четверти плоскости (2+)2. Случайные блуждания удовлетворяют следующему условию однородности: все пространство состояний X может быть разбито на конечное число непересекающихся множеств X = и Бг таких, что для любого г и любых а,(3 £ Бг выполнено равенство переходных вероятностей: = рр,13+(г,з)- Другими словами, скачки одинаковы из всех состояний множества Бг. В соответствии с этим определением, мы разбиваем плоскость 1? на множество Б и набор конечных множеств Б1, Б2,..., Бп) полуплоскость Ъ х — на внутреннюю часть 51 = {(ь^) : ,7 > 1} и границу Б' = {(г,0)}, четверть плоскости (Ъ+)2 — на внутреннюю часть Б = {(г,^) : г,] > 1}, оси Б' = {(¿,0) : г' > 1}, Б" = {(0,^) : з > 1} и {(0,0)}. Предполагается, что векторы среднего скачка за один шаг во внутренней части ненулевые. Эти модели возникают во многих прикладных задачах, в частности, в теории массового обслуживания. Например, простейшая нетривиальная задача массового обслуживания может быть описана как случайное блуждание в четверти плоскости. Анализу этих моделей посвящен ряд работ: в [29] приведена их классификация, даны необходимые и достаточные условия на векторы среднего скачка за один шаг для эргодичности, нулевой возвратности, транзиентности; в [4] решена задача больших уклонений; в [42] найдена существенная скорость сходимости. Во всех перечисленных работах используются вероятностные методый.

Отметим, что для транзиентных блужданий в полуплоскости и в четверти плоскости выделяются качественно различные случаи. Пусть Е = (Ег,Еу), Е' = (Е^,, Еу) и Е" = (Е",Е^') векторы среднего скачка за один шаг из какого-нибудь состояния соответственно во внутренней части, в области Б' и в области Б". Тогда в Ъ х при Еу > 0 [соотв. в (2+)2 при Еж, Еу > 0] почти все траектории уходят на бесконечность по внутренней части, то есть лишь конечное число раз посещая: Б' [соотв. 5' и Б" и (0,0)]. При Е „ < 0, Ех Е'у -ЕУЕ'Х ф Ъ ъ Ъ х почти все траектории уходят в бесконечность по границе, то есть посещают Б' бесконечное число раз. В ^+)2, если Е^ > 0, Еу < 0, Ех Е^ — Е^ Е'х > 0 или Ех < 0, Еу < 0, Ех Е'у -ЕУЕ'Х> 0, Еу Е" - Ех < 0 [соотв. Ех < 0, Еу > 0, Еу - Еж Е;' > 0 или Еж < 0, Е„ < 0, Еу Е" - Ех Е£ > 0, Еж Е'у - Е„ Е^ < 0], почти все траектории посещают бесконечно часто Б' и лишь конечное число раз Б", другими словами, уходят в бесконечность по оси Б' [соотв. 5"']. Наконец, в случае Е^ < 0, Еу < 0, Ех Е^ — Е^ Е^ > 0, Еу Е" — Е^ Еу > 0 уход в бесконечночть возможен по каждой из двух осей с положительной вероятностью. Эти результаты следуют из [29].

Остановимся на однородном блуждании в плоскости. Рассмотрим частный случай, когда 5"1, Я2,..., Бп пусты, то есть скачки одинаковы во всех точках пространства. В этом случае граница Мартина найдена в уже упомянутой работе [44]. В ней рассмотрена асимптотика функции Грина вдоль траекторий, которые стремятся к прямолинейным лучам, выходящим из начала координат. Если направление луча совпадает с направлением вектора среднего скачка, то требуемая асимптотика вычисляется с помощью локальной центральной предельной теоремы. В противном случае делается замена меры так, чтобы заданный луч совпал с направлением вектора среднего скачка в новой мере. (Точно такая же замена меры делается для решения задачи больших уклонений. Однако проблема взаимосвязи границы Мартина и больших уклонений остается открытой.) Тогда, следуя предыдущему случаю, можно найти асимптотику функции Грина в новой мере. Наконец, полная пространственная однородность, позволяет связать простым соотношением функцию Грина в исходной мере с функцией в новой мере. Таким образом, требуемая асимптотика может быть найдена вдоль всех лучей. По результатам легко видеть, что граница Мартина гомеомрофна сфере. Метод, предложенный в [44], применим лишь в случае полной пространственной однородности. Если мы изменим скачки хотя бы в одной точке — этот метод уже не работает, поскольку невозможно связать функцию Грина в старой и новой мере. Тем более, этот метод неприменим для случайных блужданий в полуплоскости и четверти плоскости. В настоящей работе мы также находим асимптотику функции Грина вдоль лучей. Но для этого используем другой подход. Он позволяет вычислить границу Мартина для пространственно однородных случайных блужданий в Ъ2, где скачки в конечном числе точек изменены (б'1,..., 5'п не пусты), а также в Ъ+ х Ъ и Этот подход состоит в комплексном ана-

лизе алгебраической (эллиптической) кривой, задаваемой производящей функцией скачков во внутренней части. Он был разработан Малышевым в [6, 7, 8] для исследования асимптотики стационарных вероятностей эргодического случайного блуждания в (Ъ+)2. Заметим, что мы используем аналитические методы не в полной мере: нам не требуются решения функциональных уравнений в явном виде, а лишь возможность их аналитически продолжить. Граница Мартина в каждом случае го-меоморфна некоторому подмножеству "вещественных" точек эллиптической кривой.

Для нахождения границы Пуассона мы ограничиваемся вероятностными методами. При этом мы опираемся на работу [17], в которой структура инвариантной <т-алгебры марковской цепи описана с помощью почти замкнутых множеств пространства ее состояний. Для выде-

ления почти замкнутых множеств используется метод пробных функций (функций Ляпунова) из [29].

В Разделе 0.1 Введения определены рассматриваемые двумерные случайные блуждания, перечислены все наложенные на них условия.

Глава 1 посвящена границе Пуассона. В Разделе 1.1 дано ее определение и сформулированы необходимые утверждения. В Разделе 1.2 найдена граница Пуассона для двумерных случайных блужданий. Исследованы все качественно различные случаи. В большинстве из них граница Пуассона тривиальна. В четверти плоскости, в случае ухода на бесконечность по каждой из осей с положительной вероятностью, она состоит из двух точек. В Разделе 1.3 приведены некоторые обобщения полученных результатов на случаи большей размерности.

В Главе 2 найдена граница Мартина для случайных блужданий в плоскости, в полуплоскости и четверти плоскости. В Разделе 2.1 дано ее определение и перечислены важнейшие связанные с ней утверждения. В Разделе 2.2 сформулированы полученные результаты. При этом в Разделе 2.2.1 мы приводим все определения и утверждения относительно эллиптической кривой, необходимые для представления результатов. Далее в Разделах 2.2.2-2.2.7 сформулированы теоремы о границе Мартина соответственно для случайных блужданий в 7? с измененными скачками в конечном числе точек, в Z х Z+ с уходом на бесконечность по внутренней части и с уходом на бесконечность по оси, в (2+)2 с уходом на бесконечность по внутренней части, по одной оси и по двум осям. В Разделе 2.3 даны доказательства. В Разделе 2.3.1 описана их общая структура. Кроме того, в Разделе 2.2.2, в качестве примера, проанализирован результат работы [44].

В Главе 3 рассмотрена некоторая бесконечночастичная система на непрерывном пространстве состояний и ее асимптотическое поведение. Основной упор сделан на вычисление скорости сходимости к одной из точек границы Пуассона.

В заключение, отметим, что возможно применение разработанного во второй главе аналитического подхода к случайным блужданиям с более общими условиями на скачки. Граница Мартина снова го-меоморфна некоторому подмножеству соответствующей эллиптической кривой. Этот метод может быть также использован для вычисления границ входа и выхода возвратных цепей, которые определены в [38, 39, 45].

0.1. Случайные блуждания в Ъ\ Ъ х Z+ и (2+)2

В главах 1 и 2 мы будем рассматривать счетные марковские цепи £1, £2 и £3, которые являются однородными случайными блужданиями

в плоскости, полуплоскости и четверти плоскости соответственно. Другими словами, их пространства состояний:

22 = {(»\Л ЬЗ Целые}, х Ъ = {(г,^), целые, 3 > 0}, (г+)2 = {(¿,Я, 1,3 целые, %,з > 0}.

Блуждания максимально пространственно однородны. Это свойство означает, что пространство состояний может быть представлено как объединение конечного числа непересекающихся множеств:

—и^

г

таких, что для любого г и любых состояний а, (3 € 5Г выполнено следующее равенство для переходных вероятностей:

Рр,!3+{%,3) ~ Ра,а+(г,з)-

Вероятности скачков а £ ,5'Г) обозначим через ^р^.

Пространство состояний цепи С\ есть объединение

т=1

где множества

конечны. Переходные вероятности ^р^ обозначим через р^ и ^р^, ^Ргл • • •, ^Рц соответственно.

Пространство состояний цепи £2 есть объединение двух множеств:

Х+хХ = Б и 5',

где

Я =

5" = {(¿,0)}.

Вероятности скачков для множеств 3 и 5'' обозначим через и р'г] соответственно.

Пространство состояний цепи £3 есть объединение четырех множеств:

(2+)2 = 5и5"и5"и{(0,0)},

где

5 = {(г,Я:г",у >0}, 5' = {(г, 0) : г > 0},

5"' = {(0,Я^'>0}.

Вероятности скачков ^р^ обозначим соответственно через рг1, р'- ■, р"

ир?,-.

Предположим, что цепи £1, £2, £з неприводимые и апериодические и их скачки ограничены:

Ра,р ф о, только при - 1 < ((3 - а)к < 1,

где (/? — а)к — к-ая координата вектора (/? — а), А; = 1,2. Кроме того, вероятности рю, Р-нь Рог и ро_1 отличны от нуля для класса Зг = ,5' и все другие вероятности скачков для этого класса равны нулю. Пусть также есть соскок с границ: ]С»Ра > 0, Е^-р'/, > 0.

Зафиксируем начальное состояние всех цепей в (0,0). Введем векторы среднего сноса:

Е = (Ех,Еу) =

Е' = (Е^еу =

1,3

Е" = = (Е^яЕл^).

1,3 1,3

Мы будем рассматривать случай, когда Ех ф 0 и Еу ф 0 для £1, £2 и £3. Это влечет транзиентность цепи £1. Нам интересны только транзиент-ные цепи. В противном случае все гармонические функции постоянны и границы Мартина и Пуассона тривиальны. Приведем необходимые и достаточные условия транзиентности цепей £2 и £3 при этом условии. Они доказаны в [29].

Теорема 0.1. Пусть Ех ф 0, Еу ф 0. Цепь £2 транзиентиа, если и только если выполнено одно из условий

1. Еу > 0;

2. Е*<0, Ех Е'у — ЕуЕ'хф 0.

Теорема 0.2. Пусть Ех ф 0, Еу ф 0. Цепь £3 транзиентиа, если и

только если выполнено

одно

из условии

1. Ех > о, Еу >0;

2. Ех <0, Еу <0, Ех Е;- ЕуЕ^ > 0, Еу Е"- X Ех Е" у <0;

3. Ех <0, Еу <0, Ех е;- ЕуЕ; 1Л Еу Е"- X Ех Е" у >0;

4. Ех >0, Еу <0, Е, к- Е Е' >0;

5. Ех < 0, Еу > о, Еу к- Е Е" Пх '-у >0;

6. Ех < 0, Еу < о, Ех к- Е Е' Ч/ '-а: >0, Еу Е"- X Ех Е" у > 0.

1. Граница Пуассона

1.1. Основные определения

Рассмотрим однородную цепь Маркова С со счетным пространством состояний X, матрицей переходных вероятностей Р — (paß), сх, ß £ X, и некоторым начальным распределением. Обозначим пространство путей цепи Х°° = {(an)£l0, ап ^ и вероятностную меру на нем Р. Будем предполагать, что цепь неприводима и апериодична.

Введем функцию сдвига Т : X00 —> Xе0 на пространстве путей:

T(a0,Q!i,...) = (ах, ск2,...).

Определение 1.1. Множество С С Х°° называется инвариантным, если Т-1 С = С.

Класс инвариантных множеств Q образует и-алгебру.

Определение 1.2. а-алгебра инвариантных множеств Q называется инвариантной сг-алгеброй.

Отметим, что эта <т-алгебра одна и та же для всех цепей с пространством состояний X. Как только введена мера Р на пространстве путей, мы можем рассмотреть счетный набор А = {Со, Сi, С2, •..} непересекающихся инвариантных множеств положительной вероятности, удовлетворяющих условиям:

• все Сi, за исключением быть может одного Со, — атомы, то есть не содержат двух непересекающихся инвариантных подмножеств ненулевой вероятности;

• если присутствует множество Со — не атом, то оно не содержит атомов в качестве подмножеств;

Список литературы диссертационного исследования кандидат физико-математических наук Куркова, Ирина Анатольевна, 1998 год

Литература

[1] В.И. Арнольд (1968) Особенности гладких отображений. Успехи Мат. Наук 23 (1), 3-44.

[2] Е.Б. Дынкнн (1969) Граничная теория марковских процессов (дис-

кретный случай). Успехи Мат. Наук 24 (7), 3-43.

[3] Е.Б. Дынкин и М.В. Малютов (1961) Случайное блуждание на группах с конечным числом образующих. Докл. АН СССР 137 (5), 1041— 1045.

[4] И. А. Игнатюк, В. А. Малышев и В.В. Щербаков (1994) Влияние границ в задачах о больших уклонениях. Успехи Mam. Наук 49 (2), 43-102.

[5] В.А. Каиманович и A.M. Вершик (1979) Случайные блуждания на дискретных группах: граница, энторпия, равномерное распределение. Докл. АН СССР 20, 1170-1173.

[6] В.А. Малышев (1970) Случайные Блуждания. Уравнения Винера-Хопфа б Четверти Плоскости. Автоморфизмы Галуа. Издательство Московского Университета.

[7] В.А. Малышев (1972) Аналитический метод в теории двумерных положительных случайных блужданий. Сиб. Мат. Журнал 13 (б), 1314-1327.

[8] В.А. Малышев (1973) Асимптотическое поведение стационарных вероятностей для двумерных положительных случайных блужданий Сиб. Мат. Журнал 14 (1), 156-169.

[9] Г.А. Маргулис (1966) Положительные гармонические функции на нильпотентных группах. Докл. АН СССР 166 (5), 1054-1057.

[10] Д. Милнор (1965) Теория Морса. Мир, Москва.

[11] Ф. Спицер (1969) Принципы Случайного Блуждания. Пер. с англ., Мир, Москва.

[12] Дж. Спрингер (1960) Введение в Теорию Римановых Поверхностей. Пер. с англ., Изд. иностр. лит.

[13] М.В. Федорюк (1977) Метод перевала. Наука, Москва.

[14] Б.В. Шабат (1969) Введение в комплексный анализ. Москва, Наука.

[15] А. Апсопа (1988) Positive harmonic functions and hyperbolicity. Potential theory, surveys and problems. Lecture Notes in Math. 1344 (ed. J. Krai et al., Springer, Berlin) 1-23.

[16] M. Babillot (1985) Le noyau potentiel des chaînes semi-Markoviennes. Applications a l'étude du renouvellement des marches aléatoires. Thèse du 3ème cycle, Université Paris VII.

[17] D. Blackwell (1955) On transient Markov processes with a countable number of states and stationary transition probabilities. Ann. Math. Statist. 26, 654-658.

[18] P. Cartier (1973) Harmonic Analysis on trees. Proc. Sympos. Pure Math. (Amer. Math. Soc. Providence, RI) 26, 419-424.

[19] D.I. Cartwright and S. Sawyer (1991) The Martin boundary for general isotropic random walks in a tree. J. Theoret. Probab. 4, 111-136.

[20] G. Choquet and J. Deny (1960) Sur l'équation de convolution p, — p,*cr. C. R. Acad. Sci Paris 250 (7), 799-801.

[21] E.G. Coffman and E.N. Gilbert (1987) Polling and greedy servers on the line. Queueing Syst. (2), 115-145.

[22] E.G.Jr. Coffman and A. Stolyar (1993) Continuous polling on graphs. Prob. Eng. Inf. Sci. 7, 209-226.

[23] M. Denker and H. Sato (1994) Martin boudary and Serpinsky gasket. Preprint.

[24] Y. Derriennic (1975) March aléatoire sur le groupe libre et la frontiere de Martin. Wahrscheinlichkeitsh. verw. Geb. 32 (7), 261-276.

[25] y. Derriennic (1980) Quelques applications du théorème ergodique sous-additif. Asterique 74 (7), 183-201.

[26] y. Derriennic (1986) Entropie théorèmes limite et marches aléatoires. Probability measures on groups. VIII, Lectures Notes in Math. 1210 (ed. H. Heyer, Springer, Berlin) 241-284.

[27] J. Doob (1959) Diskrete potential theory and boundaries. J. Math. Mech. 8 (7), 433-458.

[28] J.L. Doob, J.L. Snell and R.F. Williamson (1960) Application of boundary theory to sums of independent random variables. Contributions to probability and statistics. Stanford University Press, Stanford, CA, (7), 182-197.

[29] G. Fayolle, V.A. Malyshev and M.V. Menshikov (1995) Topics in Constructive Theory of Countable Markov Chains. Cambridge University Press.

[30] S. Foss and G. Last (1995) Stability of polling systems with exhaustive service policies and state-dependent routing. Ann. Appl. Probab. 6 (1), 116-137.

[31] H. Furstenberg (1971) Random walks and discrete subgroups of Lie groups. In: Adv. in Probab. Related Topics, P. Ney (ed.), Dekker, New York, 1-63.

[32] M. Gromov (1987) Hyperbolic groups. Essays in group theory. Math. Sei. Res. Inst. Publ. (ed. S.M. Gersten, Springer, New York) 8, 75-263.

[33] Y. Guivarch, L. Ji and J. Taylor (1997) Compactifications of Symmetric Spaces. Progress in Mathematics 156, Springer.

[34] P.L. Hennequin (1963) Processus de Markov en cascade. Ann. Inst. H. Poincare 18 (7), 109-196.

[35] G.A. Hunt (1960) Markov chains and Martin boundaries. Illinois J. Math. 4 (7), 313-340.

[36] V. Kaimanovich and A.M. Vershik (1983) Random walks on discrete groups: boundary and entropy. Ann. Probab. 11, 457-490.

[37] V. Kaimanovich (1992) Measure-theoretic boundaries of Markov chains, 0-2 laws and entropy. In: Harmonic analysis and discrete potential theory, M.A. Picardello (ed.), Plenum, New York, (7), 145-180.

[38] J.G. Kemeny, L.J. Snell and A.W. Knapp (1976) Denumerable Markov Chains. Springer, New York.

[39] J.G. Kemeny, J.L. Snell (1963) Boundary theory for recurrent Markov chains. Trans. Amer. Math. Soc. 106, 495-520.

[40] D.F. Kroese and V.A. Schmidt (1992) A continuous polling system with general service times. Ann. Appl. Probab. (2), 906-927.

[41] V.A. Malyshev (1993) Networks and dynamical systems. Adv. Appl. Prob. 25, 140-175.

[42] V.A. Malyshev and F.M. Spieksma (1995) Intrinsic convergence rate of countable Markov chains. Markov Processes Relat. Fields 1 (2), 203266.

[43] R.S. Martin (1941) Minimal positive harmonic functions. Trans. Amer. Math. Soc. 49, 137-172.

[44] P. Ney and F. Spitzer (1966) The Martin boundary for random walk. Trans. Amer. Math. Soc. 121, 116-132.

[45] S. Orey (1964) Potential kernels for recurrent Markov chains. J. Math. Anal. Appl. 8, 104-132.

[46] M.A. Picardello and W. Woess (1987) Martin boundaries of random walks: ends of trees and groups. Trans. Amer. Math. Soc. 302 (7), 185-205.

[47] M.A. Picardello and W. Woess (1992) Martin boundaries of Cartesian products of Markov chains Nogoya Math. J. 128, 153-169.

[48] M.A. Picardello and W. Woess (1992) The full Martin boundary of the bi-tree. Preprint University of Milan.

[49] D. Revuz (1975) Markov Chains. North Holland.

[50] G.A. Willis (1990) Probability measures on groups and some related ideals in group algebras. J. Func. Anal. 92 (7), 202-263.

[51] W. Woess (1994) Random walks on infinite graphs and groups. A survey of selected topics. Bull. London. Math. Soc. 26, 1-60.