STUDIA UNIV. BABEŞ–BOLYAI, INFORMATICA, Volume ?, Number ?, ????

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION)

ANTAL IVÁNYI

Abstract. A binary matrix B = [B_{ij}]_{m×n}is called good, if it contains at most one 1’s in each column; the matrix is called schedulable, if it can be transformed into a good matrix repeating the following operation: we remove any zero element m_{i,j} = 0, shift the elements m_{i,j+1}, … m_{i,n} to left and add a new element m_{i,n} = 0 to the i-th row of the matrix; the matrix is called safe, if for any k (k = 1, …, n) holds that the first k columns of the matrix contain at most k 1’s.

Let Z = [z_{ij}]_{m×n} be a matrix containing independent random variables having the join distribution P (z_{i,j} = 1) = p and P (z_{i,j} = 0) = 1 − p. In the case m ≥ 1 we give lower and upper bound of the asymptotic probability of the event that a concrete realisation of the matrix Z is schedulable.

Received by the editors: 2005. December 25.

2000 Mathematics Subject Classification. 05A16, 60C05, 68Q25, 82B41.

1998 CR Categories and Descriptors. G.3 [Probability and statistics]:

Queueing theory; F2.2 [Analysis of algorithms and problem complexity]:

Nonnumerical algorithms and problems – Computations on discrete structures.

2 ANTAL IVÁNYI

1. Introduction

Random walks are popular in combinatorics [3, 5, 6, 15, 16] and in physics [1, 7, 12, 13] too.

In this paper we investigate a problem of percolation [5, 6, 12, 13], which is interesting also in scheduling of parallel processes using resourses requireing mutual exclusion.

We estimate the probability of schedulabilty of processes investigating assymetric random wald across an axis.

2. Formulation of the problem

Let m and n be positive integers, let r (0 ≤ r ≤ m) be a real number and let

(1)  Z = ( \begin{matrix}z_{11} & z_{12} & … & z_{1n} \\ z_{21} & z_{22} & … & z_{2n} \\ … \\ z_{m1} & z_{m2} & … & z_{mn} \end{matrix} )

be a matrix of independent random variables with the common distribution (2)

P (z_{ij} = k) = \{ \begin{matrix}p, & if k = 1 and 1 ≤ i ≤ m, 1 ≤ j ≤ n, \\ q = 1 − p, & if k = 0 and 1 ≤ i ≤ m, 1 ≤ j ≤ n. \end{matrix}

Let

(3)  A = ( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ a_{21} & a_{22} & … & a_{2n} \\ … \\ a_{m1} & a_{m2} & … & a_{mn} \end{matrix} )

be a concrete realization of Z.

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 3

The good, safe and schedulable matrices are defined as follows.

Matrix A is called r-good, if the number of the 1’s is at most r in all columns. The number of different r-good matrices of size m × n is denoted by G_{r}(m, n) and the probability that Z is good is denoted by g_{r}(m, n, p).

Matrix A is called r-safe, if

(4)  ∑_{i=1}^{m} ∑_{j=1}^{k} a_{ij} ≤ kr (k = 1, 2, …, n).

The number of different r-safe matrices of size m × n is denoted by S_{r}(m, n) and the probability that Z is safe, is denoted by s_{r}(m, n, p).

If a_{ij} = 0, then it can be deleted from A. Deletion of a_{ij} means that we decrease the second indices of a_{i,j+1}, …, a_{im} and add a_{im} = 0 to the i-th row of A.

Matrix A is called Winkler r-schedulable (shortly rschedulable or r-compatible) if it can be transformed into a r-good matrix B using deletions. The number of different r-schedulable matrices of size m × n is denoted by W_{r}(m, n) and the probability that Z is r-schedulable is denoted by w_{r}(m, n, p). The function w_{r}(m, n, p) is called r-schedulability function.

The functions g_{r}(m, n, r), w_{r}(m, n, r) and s_{r}(m, n, r) are called the density functions of the corresponding matrices. The asymptotic density of the good, safe and schedulable matrices are defined as

(5)  g_{r}(m, p) = lim_{n→∞} g_{r}(m, n, p),

4 ANTAL IVÁNYI

(6)  s_{r}(m, p) = lim_{n→∞} s_{r}(m, n, p),
(7)  w_{r}(m, p) = lim_{n→∞} w_{r}(m, n, p).

The critical probabilities defined as

(8)  w_{crit,r}(m) = sup{p | w_{r}(m, p) > 0},
(9)  g_{crit,r}(m) = sup{p | g_{r}(m, p) > 0},

and

(10)  s_{crit,r}(m) = sup{p | s_{r}(m, p) > 0}

represent special interest for some applications.

The aim of this paper is to characterize the density, asymptotic density and critical probability of good, schedulable and safe matrices.

Starting point of our research is due to Péter Gács [6] proving that w_{1}(2, p) is positive for p small enough. His proof implies that w_{crit,1}(2) ≥ 10^{−400}.

We remark that some recent papers are closely connected with our efforts: [9] enumerates some r-safe matrices, [10] presents density of 2- and (m/2)-safe matrices and [11] investigates algorithms generating all safe and schedulable matrices.

2.1. Interpretation of the problem. Bár a Winklermodellt a perkoláció leírására javasolták, a problémák egyegy lehetséges informatikai értelmezését mutatjuk be. m folyamatnak időnként ugyanarra az erőforrásra van szüksége, amelyből r/2 egység van. Az i-edik folyamat erőforrásigényét

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 5

az a_{i1}, a_{i2}, …, a_{im} sorozattal adjuk meg. Ha ennek a sorozatnak az a_{ij} eleme egyes, akkor az i-edik folyamat a [j − 1, j) intervallumban igényli az erőforrást. Ha a_{ij} = 0, akkor ugyanabban az intervallumban a folyamat nem igényli az erőforrást, mert későbbre halasztható háttérmunkát végez – ez magyarázza, hogy az ütemezhetőség érdekében a nullák törölhetők.

Az m = 1 és r = 1 speciális eset az ismert jegyváltási probléma [15] és szavazási probléma [4], az m = 2 és r = 2 speciális eset pedig a Winkler-féle perkolációs modell [6, 16].

A jó mátrixok törlés nélkül ütemezhetők. A nem jó mátrixok egy része törlés(ek) segítségével jóvá alakítható, azaz ütemezhető. A biztosság az ütemezhetőség szükséges feltétele. Ezért a jó mátrixok száma alsó korlát, a biztos mátrixok száma pedig felső korlát az ütemezhető mátrixok számára.

Mivel a problémát informatikai problémaként kezeljük, ezért a továbbiakban elsősorban Feller [4] informatikai (tömegkiszolgálási) terminológiáját használjuk.

3. Analysis

Ebben a részben elsősorban azt vizsgáljuk – különböző módszerekkel – hogyan függ a biztos mátrixok aszimptotikus sűrűsége az egyesek előfordulásának p valószínűségétől és a sorok m számától.

A vizsgált g_{r}(m, n, p), w_{r}(m, n, p) és s_{r}(m, n, p) függvények tulajdonságai:

• n ∈ ℕ^{+}, r ∈ ℝ and r ∈ [0, m], p ∈ ℝ and p ∈ [0, 1];

6 ANTAL IVÁNYI

• n szerint monoton csökkenők;

• p szerint monoton csökkenők;

• m szerint monoton csökkenők;

• r szerint monoton növekvők. A továbbiakban mindenütt feltesszük, hogy r = 1, azaz

a jó mátrixok oszlopaiban legfeljebb egy egyes, a biztos mátrixok k hosszúságú prefixeiben pedig legfeljebb k egyes lehet. Mivel r értéke mindenütt ugyanaz, a továbbiakban elhagyjuk az r indexet.

3.1. Preliminary results. A későbbiekben felhasználjuk az alábbi állításokat.

Jelöljük C_{n}-nel (n ∈ ℕ^{+}) azon a_{1}, a_{2}, …, a_{2n} bináris sorozatok számát, amelyekben n darab egyes és n darab nulla van úgy, hogy minden a_{1}, a_{2}, …, a_{k} (1 ≤ k ≤ 2n) kezdősorozatban legfeljebb annyi egyes van, mint nulla.

Lemma 1. If n ≥ 0, then

C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Megjegyezzük, hogy C_{n} az n-edik Catalan-szám, melynek explicit alakja számos tankönyvben és cikkben [2, 15] megtalálható.

Lemma 2. If 0 ≤ x ≤ 1, then (11)

f(x) = x ∑_{k=0}^{∞} \frac{1}{k + 1}\binom{2k}{k}(x(1−x))^{k} = \{ \begin{matrix}\frac{x}{1−x}, & if 0 ≤ x < \frac{1}{2}, \\ 1, & if \frac{1}{2} ≤ x ≤ 1. \end{matrix}

Proof.

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 7

If m ≥ 2, then the columns containing only 0’s are called white (W), the columns containing exactly one 1 are called grey (G) and the remaining columns are called black (B).

Ha m ≥ 2, akkor az A mátrix minden oszlopa q^{m} + mq valószínűséggel lehet fehér vagy szürke, ezért g(m, n, p) = ((q^{m} + mq))^{n} . Ha p > 0, akkor

(12)  g(m, p) = lim_{n→∞} (q^{m} + mq)^{n} = 0,

tehát az oszlopok számának növekedtével a jó mátrixok sűrűsége tart a nullához.

Ha az m = 2 esetben egy jó mátrixból töröljük a fehér oszlopokat, akkor csak szürke oszlopok maradnak, azaz a mátrix két sora egymásnak a komplementere.

Vizsgálataink szempontjából fontos szerepet játszik a következő egyszerű állítás.

Lemma 3. If m ≥ 2, then the good matrices are schedulable, the schedulable matrices are safe.

Proof. Ha az A mátrix minden oszlopában legfeljebb egy egyes van, akkor a mátrix első k oszlopában összesen legfeljebb k egyes van.

Ha van olyan k (1 ≤ k ≤ n), amelyre az A mátrix első k oszlopában több egyes van, mint k, akkor a skatulyaelv szerint az első k oszlop között van olyan, amelyikben legalább két egyes van. Ha az A mátrixból törlünk egy nullát, ezzel az első k oszlopban lévő nullák száma nem csökken – tehát A nem ütemezhető.

Ennek az állításnak hasznos következménye az alábbi.

Corollary 4. If m ≥ 2, then

(13)  g(m, n, p) ≤ w(m, n, p) ≤ s(m, n, p),
(14)  g(m, p) ≤ w(m, p) ≤ s(m, p),
(15)  g_{crit}(m) ≤ w_{crit}(m) ≤ s_{crit}(m).

3.2. Two rows in the matrix. Az egyszerűség kedvéért az s(2, n, p) függvény helyett az u(2, n, p) = 1 − s(2, n, p) függvényt elemezzük. Először megadunk egy zárt képletet u(2, n, p) meghatározására.

Lemma 5. If n ≥ 1, then

(16) u(2, n, p) = ∑_{i=1}^{n} ∑_{j=0}^{⌊(i−1)/2⌋} 2^{i−1−2j}C_{j}\binom{i − 1}{2j}4^{n−i}.

Proof. A lehetséges 2×n méretű, nem biztos mátrixokat osztályozzuk azon oszlopuk szerint, amelyben az egyesek száma először haladta meg a nullák számát (ezt az oszlopot döntő oszlopnak nevezzük).

A döntő oszlop indexe 0, 1, …, n − 1 vagy n. Az egy osztályba került mátrixokat pedig osztályozzuk aszerint, hogy a döntő oszlop előtt hány fekete oszlopuk volt: ez a szám 0, 1, …, ⌊(n − 1)/2⌋ lehet.

A külső összegzés a döntő oszlopokat veszi figyelembe, a belső pedig a döntő oszlop előtti fekete oszlopokat. Az összegben a binomiális együttható azt veszi számba, hányféleképpen helyezhető el a döntő oszlop előtti i−1 oszlopban az összesen 2j fekete és fehér oszlop. A C_{j} Catalán-szám azt adja meg, hány megfelelő sorrendje van a fekete és fehér oszlopoknak.

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 9

A 2 alapú hatvány azt mondja meg, hogy hányféleképpen választhatók meg a szürke oszlopok. Végül a 4 alapú hatványtényező azt veszi figyelembe, hogy a döntő oszlop utáni oszlopok tetszés szerint kitölthetők – a mátrix mindenképpen bizonytalan lesz.

Az u(2, n, p)-re kapott (16) képlet nehezen kezelhetőnek látszik. Ezért bemutatunk egy kombinatorikus és két bolyongásos módszert s(2, p) explicit alakjának levezetésére.

Lemma 6. If 0 ≤ p ≤ 1, then

(17)  u(2, p) = \{ \begin{matrix}\frac{p^{2}}{q^{2}}, & if 0 ≤ p < \frac{1}{2}, \\ 1, & if \frac{1}{2} ≤ p ≤ 1. \end{matrix}

Proof. A bizonytalan mátrixok egy részét az első fekete oszlop teszi bizonytalanná. Ezek általános alakja G^{a}BA^{b}, ahol a + b + 1 = n, továbbá G szürke, B fekete és A tetszőleges oszlopot jelent. Az ilyen oszlopok aszimptotikus részaránya

∑_{a=0}^{∞} C_{0}(2pq)^{a}p^{2} = \frac{p^{2}}{1 − 2pq}C_{0} .

A bizonytalan mátrixok következő csoportjának általános alakja G^{a}BG^{b}W G^{c}BA^{d}, ahol a+b+c+d+3 = n. Az ilyen mátrixok aszimptotikus részaránya

∑_{a=0}^{∞}(2pq)^{a}p^{2} ∑_{b=0}^{∞}(2pq)^{b}q^{2} ∑_{c=0}^{∞}(2pq)^{c}p^{2} = \frac{p^{2}}{1 − 2pq}C_{1} \frac{p^{2}}{1 − 2pq} \frac{q^{2}}{1 − 2pq} .

10 ANTAL IVÁNYI

Általában, ha az (i+1)-edik fekete oszlop a döntő, akkor az ilyen mátrixok aszimptotikus hozzájárulása a bizonytalan mátrixok valószínűségéhez

\frac{p^{2}}{1 − 2pq}C_{i} (\frac{p^{2}}{1 − 2pq} \frac{q^{2}}{1 − 2pq})^{2} ,

és így

u(2, p) = ∑_{i=0}^{∞} \frac{p^{2}}{1 − 2pq}C_{i} (\frac{p^{2}}{1 − 2pq} \frac{q^{2}}{1 − 2pq})^{i} .

A p^{2}/(p^{2} + q^{2}) = x és q^{2}/(p^{2} + q^{2}) = 1 − x helyettesítéssel alkalmazva a 2. lemmát megkapjuk a kívánt képletet.

Mátrixaink vizsgálatának hasznos módszere, ha minden mátrixhoz hozzárendelünk egy – az x-tengelyen való – bolyongást.

A bolyongó pont a k-adik időpontban a P_{k}(b_{k}, 0) pontban van, ahol b_{k} a mátrix első k oszlopában előfordult nullák és egyesek számának különbségét jellemzi.

Ha a bolyongás az origóból indul, akkor

b_{k} = \{ \begin{matrix}−1, & if ∃k with k < ∑_{i=1}^{k}(a_{i1} + a_{i2}), \\ k − ∑_{i=1}^{k}(a_{i1} + a_{i2}) & otherwise. \end{matrix}

Ekkor a 6. lemma egy másik bizonyítása a következő.

Proof. Azt akarjuk meghatározni, hogy az origóból induló pont milyen valószínűséggel nyelődik el a −1 pontban lévő nyelőben. Bár a fehér, illetve fekete oszlop után kettővel változik az addig előfordult nullák és egyesek számának különbsége, az egyszerűség kedvéért azt tételezzük fel, hogy fekete oszlop után p^{2} valószínűséggel lépünk egyet balra,

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 11

fehér oszlop után q^{2} valószínűséggel lépünk egyet jobbra, és szürke oszlop után 2pq valószínűséggel helyben maradunk.

Az u(2, p) = x jelöléssel a teljes valószínűség tétele alapján azt kapjuk, hogy

(18)  x = p^{2} + 2pqx + q^{2}x^{2}.

Ennek az egyenletnek a gyökei (19)

x_{1,2} = \frac{1 − 2pq ± \sqrt{(1 − 2pq)^{2} − 4p^{2}q^{2}}}{2q^{2}} = \frac{p^{2} + q^{2} ± \sqrt{(p^{2} − q^{2})^{2}}}{2q^{2}} ,

ahonnan

(20)  x_{1} = \frac{p^{2}}{q^{2}}, and x_{2} = 1.

Innen s(2, p) = 1−u(2, p) alapján megkapjuk a bizonyítandó képletet.

Mivel bennünket elsősorban az elnyelődés valószínűsége érdekel, egy másik bolyongást is hozzárendelhetünk az Z mátrixhoz úgy, hogy a szürke oszlopoktól eltekintünk – azok ugyanis az elnyelődés határvalószínűségét nem befolyásolják, csak lassítják a konvergenciát.

A 6. lemma egy másik bizonyítása a következő.

Proof. A szürke oszlopok valószínűségét a fekete és fehér oszlopok között a megfelelő arányban elosztva a balra lépés a és a jobbra lépés b valószínűségére azt kapjuk, hogy

(21)  a = \frac{p^{2}}{p^{2} + q^{2}} és b = \frac{q^{2}}{p^{2} + q^{2}}.

Ezekkel a valószínűségekkel a

(22)  x = a + bx^{3}

12 ANTAL IVÁNYI

egyenletet kapjuk. Ennek megoldásaiba (21) szerint visszahelyettesítve a és b helyére a p és q valószínűségeket, itt is megkapjuk a (20) képlet szerinti gyököket.

Végül egy olyan módszert is bemutatunk, amelyet a későbbiekben tetszőleges m ≥ 2 értékre alkalmazni tudunk.

Proof. Jelöljük x_{k}-val (k = −1, 0, 1, 2, …) annak valószínűségét, hogy a k pontból induló bolyongó pont elnyelődik az x = −1 helyen. A két egyest tartalmazó, p^{2} valószínűséggel előforduló oszlopnak feleltessünk meg balra lépést, a 2pq valószínűséggel előforduló vegyes oszlopkhoz tartozzon helybenmaradás és a két nullát tartalmazó, q^{2} valószínűséggel előforduló oszlopoknak feleljen meg jobbra lépés.

Ekkor a következő egyenleteket írhatjuk fel.

(23)  \begin{aligned}x_{0} & = & q^{2}x_{1} & + & 2qpx_{0} & + & p^{2}, \\ x_{1} & = & q^{2}x_{2} & + & 2qpx_{1} & + & p^{2}x_{0}, \\ x_{2} & = & q^{2}x_{3} & + & 2qpx_{2} & + & p^{2}x_{1}, \\ x_{3} & = & q^{2}x_{4} & + & 2qpx_{3} & + & p^{2}x_{2}, \\ ⋯ \end{aligned}

Legyen

(24)  G(z) = ∑_{i=1}^{∞} x_{i}z^{i}

az x_{0}, x_{1}, x_{2}, … sorozat generátorfüggvénye. A (32) egyenletrendszer x_{i}-vel kezdődő egyenleteit rendre z^{i}-vel beszorozva és az egyenleteket összeadva a

(25) G(z) = q\frac{G(z) − x_{0}}{z} + 2pqG(z) + p^{2}(1 + zG(z)).

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 13

Innen G(z) kifejezhető

(26)  G(z) = \frac{P (z)}{Q(z)}

alakban, ahol

(27)  P (z) = q^{2} − p^{2}z

és

(28)  Q(z) = p^{2}z^{2} + 2pq + p^{3} − z.

A Q(z) polinom legfeljebb egy abszolut értékű zérushelyein a Cauchy-Hadamard-tétel szerint a P (z) polinomnak a nulla értéket kell felvennie . A Q(z) = 0 egyenletet

(29)  (pz + q)^{2} = 1

alakban felírva közvetlenül adódik, hogy z = 1 gyöke a Q(z) polinomnak. A P (1) = 0 egyenletből az

(30)  x_{0} = \frac{p^{2}}{q^{2}}

megoldást kapjuk.

A 1. ábra mutatja a [0, 1] intervallumban értelmezett s(2, p) függvény görbéjének a [0, 1/2] intervallumhoz tartozó részét.

A g(2, p) és s(2, p) függvények alapján az m = 2 értékhez tartozó kritikus valószínűségekre fennáll

(31)  0 = g_{crit}(2) ≤ w_{crit}(2) ≤ s_{crit}(2) = \frac{1}{2} .

Emlékeztetünk Gács eredményére, amely szerint w_{crit}(2) ≥ 10^{−400}.

Figure 1. Curve of the schedulability function s(2, p, 1)

A 2. táblázatban megadjuk a jó, ütemezhető és biztos mátrixok számát és részarányát – ami megfelel a p = 0.5 értéknek. A táblázatban jellemzett mátrixok oszlopainak száma 1, 2, …, 15 vagy 16.

Jelöljük a m×n méretű bináris mátrixok számát T (m, n)- nel. Ekkor T (m, n) = 2^{mn}.

Az eddigi eredmények alapján mind a G(m, n)/T (m, n), mind pedig a W (m, n)/T (m, n) és S(m, n)/T (m, n) értékeknek nullához kell tartani n növekedtével.

Nyitott kérdés a W (2, n)/S(2, n) hányados viselkedése.

A 3. táblázat s(2, n, 0.4) oszlopában a számoknak az 5/9 határértékhez kell tartaniuk – ami még messze van.

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 15

\begin{matrix}n & G(2, n) & \frac{G(2,n)}{T (2,n)} & W (2, n) & \frac{W (2,n)}{T (2,n)} & S(2, n) & \frac{S(2,n)}{T (2,n)} & \frac{W (2,n)}{S(2,n)} \\ 1 & 3 & 0.750 & 3 & 0.750 & 3 & 0.750 & 1 \\ 2 & 9 & 0.562 & 10 & 0.625 & 10 & 0.625 & 1 \\ 3 & 27 & 0.452 & 35 & 0.547 & 35 & 0.547 & 1 \\ 4 & 81 & 0.316 & 124 & 0.484 & 126 & 0.492 & 0.984 \\ 5 & 243 & 0.237 & 444 & 0.434 & 462 & 0.451 & 0.961 \\ 6 & 729 & 0.178 & 1592 & 0.389 & 1716 & 0.419 & 0.927 \\ 7 & 2187 & 0.133 & 5731 & 0.350 & 6435 & 0.393 & 0.890 \\ 8 & 6561 & 0.100 & 20671 & 0.315 & 24310 & 0.371 & 0.850 \\ 9 & 19683 & 0.075 & 74722 & 0.285 & 92378 & 0.352 & 0.808 \\ 10 & 59049 & 0.056 & 270521 & 0.258 & 352716 & 0.336 & 0.767 \\ 11 & 177147 & 0.042 & 980751 & 0.234 & 1352078 & 0.322 & 0.725 \\ 12 & 531441 & 0.032 & 3559538 & 0.212 & 5200300 & 0.310 & 0.684 \\ 13 & 1594323 & 0.022 & 12931155 & 0.193 & 20058300 & 0.299 & 0.646 \\ 14 & 4782969 & 0.018 & 47013033 & 0.175 & 77558760 & 0.289 & 0.606 \\ 15 & 14348907 & 0.013 & 171036244 & 0.159 & 300540195 & 0.280 & 0.568 \end{matrix}

Figure 2. Rounded data belonging to p = 1/2

A 5. táblázatban a s(2, n, 0.35) oszlop számainak a 120/169 ∼ 0.7101 határértékhez kell tartaniuk.

3.3. Three rows in the matrix. Az m = 3 esetben 3:0, 2:1, 1:2 és 0:3 lehet a nullák és egyesek aránya. A vizsgált mátrixhoz olyan bolyongást rendelünk, amelyikben a csupa egyes oszlop p^{3} valószínűségével ugrunk balra kettővel, a két egyest tartalmazó oszlop 3p^{2}q valószínűségével lépünk balra, az egy egyest tartalmazó oszlopok 3p^{2} valószínűségével

\begin{matrix}n & T (2, n) & g(2, n, 0.4) & w(2, n, 0.4) & s(2, n, 0.4) & \frac{w(2,n,0.4)}{s(2,n,0.4)} \\ 1 & 4 & 0.8400 & 0.8400 & 0.8400 & 1 \\ 2 & 16 & 0.7056 & 0.7632 & 0.7632 & 1 \\ 3 & 64 & 0.5927 & 0.7171 & 0.7171 & 1 \\ 4 & 256 & 0.4979 & 0.6795 & 0.6862 & 0.9902 \\ 5 & 1024 & 0.4182 & 0.6487 & 0.6639 & 0.9771 \\ 6 & 4096 & 0.3513 & 0.6206 & 0.6470 & 0.9592 \\ 7 & 16384 & 0.2951 & 0.5957 & 0.6339 & 0.9397 \\ 8 & 65536 & 0.2479 & 0.5731 & 0.6234 & 0.9193 \\ 9 & 262144 & 0.2082 & 0.5524 & 0.6149 & 0.8984 \\ 10 & 1048576 & 0.1749 & 0.5332 & 0.6078 & 0.8773 \\ 11 & 4194304 & 0.1469 & 0.5155 & 0.6019 & 0.8565 \\ 12 & 16777216 & 0.1234 & 0.4988 & 0.5967 & 0.8359 \\ 13 & 67108864 & 0.1037 & 0.4832 & 0.5924 & 0.8157 \\ 14 & 268435456 & 0.0871 & 0.4685 & 0.5886 & 0.7960 \\ 15 & 1073741824 & 0.0731 & 0.4545 & 0.5854 & 0.7764 \\ 16 & 4294967296 & 0.0644 & 0.4412 & 0.5825 & 0.7574 \\ 17 & 169779869184 & 0.0516 & 0.4286 & 0.5800 & 0.7390 \end{matrix}

Figure 3. Rounded data belonging to p = 0.4

maradunk helyben és a három nullát tartalmazó oszlop q^{3} valószínűségével lépünk jobbra.

A korábban is használt x_{k} jelölést bevezetve a következő egyenleteket írhatjuk fel:

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 17

\begin{matrix}n & T (2, n) & g(2, 0.35) & w(2, 0.35) & s(2, n, 0.35) & \frac{w(2,0.35)}{s(2,0.35)} \\ 1 & 4 & 0.8775 & 0.8775 & 0.8775 & 1 \\ 2 & 16 & 0.7700 & 0.8218 & 0.8218 & 1 \\ 3 & 64 & 0.6757 & 0.7901 & 0.7901 & 1 \\ 4 & 256 & 0.5929 & 0.7645 & 0.7699 & 0.9930 \\ 5 & 1024 & 0.5203 & 0.7441 & 0.7561 & 0.9841 \\ 6 & 4096 & 0.4565 & 0.7255 & 0.7462 & 0.9723 \\ 7 & 16384 & 0.4006 & 0.7094 & 0.7389 & 0.9601 \\ 8 & 65536 & 0.3515 & 0.6949 & 0.7334 & 0.9475 \\ 9 & 262144 & 0.3085 & 0.6817 & 0.7291 & 0.9350 \\ 10 & 1048576 & 0.2707 & 0.6696 & 0.7258 & 0.9226 \\ 11 & 4194304 & 0.2375 & 0.6585 & 0.7231 & 0.9107 \\ 12 & 16777216 & 0.2084 & 0.6481 & 0.7210 & 0.8989 \\ 13 & 67108864 & 0.1839 & 0.6383 & 0.7192 & 0.8875 \\ 14 & 268435456 & 0.1605 & 0.6291 & 0.7178 & 0.8764 \\ 15 & 1073741824 & 0.1401 & 0.6204 & 0.7166 & 0.8658 \\ 16 & 4294967296 & 0.1236 & 0.6122 & 0.7156 & 0.???? \end{matrix}

Figure 4. Rounded data belonging to p = 0.35

(32) \begin{aligned}x_{0} & = & q^{3}x_{1} & + & 3q^{2}px_{0} & + & 3qp^{2} & + & p^{3}, \\ x_{1} & = & q^{3}x_{2} & + & 3q^{2}px_{1} & + & 3qp^{2}x_{0} & + & p^{3}, \\ x_{2} & = & q^{3}x_{3} & + & 3q^{2}px_{2} & + & 3qp^{2}x_{1} & + & p^{3}x_{0}, \\ x_{3} & = & q^{3}x_{4} & + & 3q^{2}px_{3} & + & 3qp^{2}x_{2} & + & p^{3}x_{1}, \\ ⋯ \end{aligned}

Legyen

(33)  G(z) = ∑_{i=0}^{∞} x_{n}z^{n}

az x_{0}, x_{1}, x_{2}, … sorozat generátorfüggvénye. Akkor a (32) egyenleteket rendre beszorozva z megfelelő hatványával és összeadva őket azt kapjuk, hogy (34)

G(z) = q^{3} \frac{G(z) − x_{0}}{z}+3q^{2}p\frac{G(z)}{z}+3qp^{2}(1+zG(z))+p^{3} (1 + z + z^{2}G(z)) ,

ahonnan G(z) kifejezhető két polinom hányadosaként:

(35)  G(z) = \frac{P (z)}{Q(z)},

ahol

(36)  P (z) = q^{3}x_{0} − 3qp^{2}z − p^{3}(z + z^{2})

és

(37)  Q(z) = p^{3}z^{3} + 3p^{2}qz^{2} + 3pq^{2}z + q^{3} − 1.

A Q(z) = 0 egyenletet

(38)  (q + pz)^{3} = 1

alakra hozhatjuk, ahonnan a z_{1} = 1 gyököt kapjuk. A P (1) = 0 egyenletet q^{3}-nel osztva és a p/q = t helyettesítést bevezetve az

(39)  x_{0} = 3t^{2} + 2t^{3}

egyenletet kapjuk. Az x_{0} = x_{0}(t) függvény értéke a t = 0 helyen nulla, és pozitív t-re monoton nő. A t = p/(1 − p)

\begin{matrix}n & T (3, n) & g(3, n, 0.5) & w(3, n, 0.5) & s(3, n, 0.35) & \frac{w(3,n,0.5)}{s(3,n,0.5)} \\ 1 & 8 & 0.5000 & 0.5000 & 0.5000 & 1 \\ 2 & 64 & 0.2500 & 0.2969 & 0.2969 & 1 \\ 3 & 256 & 0.1250 & 0.1914 & 0.1914 & 1 \\ 4 & 4096 & 0.0625 & 0.??? & 0.??? & ??? \\ 5 & 32768 & 0. & 0. & 0. & 0.???? \end{matrix}

Figure 5. Rounded data belonging to m = 3 and p = 0.5

értéket visszahelyettesítve és (1 − p)^{3}-nel beszorozva a

(40)  \frac{3p^{2}}{(1 − p)^{2}} + \frac{2p^{3}}{(1 − p)^{3}} = 1

egyenletet kapjuk, amelyből rendezés után a p = 1/3 értéket kapjuk, azaz s_{crit}(3) = 1/3.

4. Main result

Az m × n méretű biztos mátrixok elemzését az m ≥ 4 esetben az m = 3 esethez hasonló módon végezhetjük el.

A bolyongó pont a legalább b ≥ 3 egyest tartalmazó oszlop esetén (b − 2)-t ugrik balra, két egyest tartalmazó oszlop esetén egyet lép balra, egy egyest tartalmazó oszlop esetén helyben marad és az m nullát tartalmazó oszlop esetén egyet lép jobbra.

A (b − 2)-vel balra ugrás valószínűsége \binom{m}{b}p^{b−2}q^{n−b+2}, a balra lépésé \binom{m}{2}p^{m−2}q^{2}, a helyben maradásé \binom{m}{1}pq^{m−1} és a jobbra lépésé \binom{m}{0}q^{m}, ezért a következő egyenleteket írhatjuk fel.

(41)

x_{0} = \binom{m}{0}q^{m}x_{1} + \binom{m}{1}pq^{m−1}x_{0} + \binom{m}{2}p^{2}q^{m−2}
+ \binom{m}{3}p^{3}q^{m−3} + … + \binom{m}{m}p^{m},
x_{1} = \binom{m}{0}q^{m}x_{2} + \binom{m}{1}pq^{m−1}x_{1} + \binom{m}{2}p^{2}q^{m−2}x_{0}
+ \binom{m}{3}p^{3}q^{m−3} + … + \binom{m}{m}p^{m},
x_{2} = \binom{m}{0}q^{m}x_{3}x_{3} + \binom{m}{1}pq^{m−1}x_{2} + \binom{m}{2}p^{2}q^{m−2}x_{1}
+ \binom{m}{3}p^{3}q^{m−3}x_{0} + … + \binom{m}{m}p^{m},

⋯

Legyen

(42)  G(z) = ∑_{i=0}^{∞} x_{n}z^{n}

az x_{0}, x_{1}, x_{2}, … sorozat generátorfüggvénye. Akkor a (41) egyenleteket rendre beszorozva z megfelelő hatványával és összeadva őket azt kapjuk, hogy

G(z) = \binom{m}{0}q^{m} \frac{G(z) − x_{0}}{z} + \binom{m}{1}pq^{m−1}G(z)+

\binom{m}{2}p^{2}q^{m−2}(1+zG(z))+\binom{m}{3}p^{3}q^{m−3}(1+zG+z^{2}G(z))+⋯

+\binom{m}{m}q^{m} (1 + z + ⋯ + z^{m−2} + z^{m−1}G(z)) ,

ahonnan G(z) kifejezhető két polinom hányadosaként:

(43)  G(z) = \frac{P (z)}{Q(z)},

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 21

ahol

(44)  P (z) = ∑_{i=0}^{m} \binom{m}{i}p^{i}q^{m−i}z^{i} − z.

és

(45)  Q(z) = \binom{m}{0}q^{m}x_{0} − ∑_{i=0}^{m} \binom{m}{p}^{i}q^{m−i} ∑_{j=0}^{i−2} z^{j}.

Ahol a nevezőnek legfeljebb 1 abszolut értékű gyöke van, ott a számlálónak a nulla értéket kell felvennie.

A Q(z) = 0 egyenletet

(46)  (q + pz)^{m} = 1

alakra hozhatjuk, ahonnan a z_{1} = 1 gyököt kapjuk. A P (1) = 0 egyenletet q^{m}-nel osztva az

(47)  x_{0} = ∑_{i=0}^{m} \binom{m}{0} (\frac{p}{1 − p})^{i} (i − 1)

egyenletet kapjuk. Az x_{0} = x_{0}(p) függvény értéke a p = 0 helyen nulla, és pozitív p-re monoton nő. Az x_{0} = 1 egyenletből a p = 1/m értéket kapjuk.

Az m = 2 és m = 3-ra kapott korábbi eredményeket is figyelembe véve ezzel a következő eredményt kaptuk.

Theorem 7. If m ≥ 2 and 0 ≤ p ≤ 1, then

(48) s(m, p) = 1 − ∑_{i=2}^{m} \binom{m}{i} (\frac{p}{1 − p})^{i} (i − 1)

and

(49)  s_{crit}(m) = \frac{1}{m}.

5. Summary

Az m ≥ 2 sort tartalmazó mátrixokra megadtuk az ütemezhetőségi függvény explicit alakját és meghatároztuk az s_{crit}(m) kritikus valószínűségeket. s_{crit}(2) értéke a több perkolációs modellre jellemző 1/2, a további kritikus valószínűségek értéke m növekedtével csökken.

A szimulációs vizsgálatok szerint a kritikus ütemezhetőségi valószínűségek közel vannak a kapott felső korlátokhoz: a

2. táblázat a p = 0.5, a 3. táblázat a p = 0.4, a 5. táblázat pedig a p = 0.35 valószínűséghez tartozó adatokat mutatja.

A táblázatok adatai azt mutatják, hogy a [6] cikkben szereplő korlátnál jobb is adható: ha p < 0.4, akkor w(2, p) > 0.

A w(m, p)/s(m, p) hányadosok viselkedése még további elemzést kíván.

A cikkben szereplő alsó korlátoknál nagyobbakat is meg tudunk adni, de azokból is csak a természetes nulla alsó korlát adódik. A kritikus valószínűségek pontosabb jellemzéséhez a jó mátrixoknál hasznosabb mátrixokra van szükség.

Acknowledgement. The authors thank Péter Gács (Boston University) for proposing the problem, further János Gonda, Lajos László, Tamás Móri, Péter Simon (all

DENSITY OF SAFE MATRICES (WINKLER MODELL OF PERCOLATION) 23

of Eötvös Loránd University), Zoltán Kása and József Kolumbán (both Babeş-Bolyai University) for their useful remarks and Rudolf Szendrei (Eötvös Loránd University) for the computer experiments.

References

[1] P. Balister, B. Bollobás, M. Walters (2004), Continuum percolation with steps in an annulus. Ann. Appl. Probab. 14/4 1869–1879. http://arxiv.org/find.

[2] A. Bege and Z. Kása (2001), Coding objects related to Catalan numbers, Studia Univ. Babeş-Bolyai, Informatica, Volume XLVI (1), 31–39. http://www.cs.ubbcluj.ro/∼studia-i/contents.php.

[3] B. Bollobas, O. Riordan (2005), A short proof of the Harris-Kesten theorem. Electronic manuscript, http://arxiv.org/find.

[4] W. Feller, (1968), An Introduction to Probability Theory and its Applications. John Wiley and Sons, New York.

[5] P. Gács (2002), Clairvoyant scheduling of random walks (submitted to Electronic Journal of Probability). Short version: Clairvoyant scheduling of random walks. In: Proc. of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 99–108 (electronic), ACM, New York, 2002. http://www.cs.bu.edu/fac/gacs/recent-publ.html.

[6] P. Gács (2004), Compatible sequences and a slow Winkler percolation. Combin. Probab. Comput. 13/6, 815– 856. http://www.cs.bu.edu/fac/gacs/recent-publ.html.

24 ANTAL IVÁNYI

[7] G. R. Grimmett, (1999), Percolation Springer, Berlin, 1999.

[8] T. E. Harris (1960), A lower bound for the critical probability in a certain percolation process. Proc. of the Cambridge Phil. Soc. 56 13–20.

[9] A. Iványi, Cs. Láng, Generalized Catalan numbers (manuscript).

[10] A. Iványi, Density of 2-safe matrices (manuscript).

[11] A. Iványi, R. Szendrei (2005), Párhuzamos folyamatok ütemezése (Scheduling of parallel processes) (manuscript).

[12] H. Kesten (1982), Percolation Theory for Mathematicians. Birkhäuser, Boston.

[13] D. Schauffer (1985), Introduction to Percolation Theory. Taylor & and Francis, London, 1985.

[14] R. P. Stanley (1999), Enumerative Combinatorics, Volume 2. Cambridge Studies in Advanced Mathematics,

62. Cambridge University Press, Cambridge.

[15] N. J. Vilenkin (1972), Combinatorial Mathematics for Recreation. Mir Publisher, Moscow.

[16] P. Winkler (2000), Dependent percolation and colliding random walks, Random Structures & Algorithms 16/1 58–84. http://www.math.dartmouth.edu/∼pw/papers/pubs.html.

Department of Computer Algebra, Eötvös Loránd University, Faculty of Informatics, 1117 Budapest, Pázmány Péter sétány 1/C., Hungary

E-mail address: tony@compalg.inf.elte.hu