\documentclass[11pt]{amsart}
\usepackage{studia}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[dvips]{graphicx}

\newcounter{algorithm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\setcounter{page}{1} % to be added afterwards
\coordinates{?}{?}{????} % to be added afterwards

\title{Density of safe matrices 
(Winkler modell of percolation)}
\author{Antal Iványi}
\address{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}
\email{tony@compalg.inf.elte.hu}
\date{2005. December 25} % submission date

\subjclass[2000]{05A16, 60C05, 68Q25, 82B41} % AMS Subject Classification (2000)
\subjclassCR{
G.3 [\textbf{Probability and statistics}]: Queueing theory; 
F2.2 [\textbf{Analysis of algorithms and problem complexity}]: 
Nonnumerical algorithms and problems -- \textit{Computations 
on discrete structures}} % ACM Computing Classification System (1998)

\begin{document}

\begin{abstract}\large
A binary matrix $B = [B_{ij}]_{m \times n}$is called \textit{good}, 
if it contains at most one 1's in each column; 
the matrix is called \textit{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},$ $\ldots 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 \textit{safe,} if for any $k \ (k = 1, \ldots, n)$ holds that the first $k$ columns of the 
matrix contain at most $k$ 1's.

Let $\mathbf{Z} = [z_{ij}]_{m\times 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 \geq 1$ we give 
lower and upper bound of the asymptotic probability of the event that a concrete realisation of the matrix $Z$ 
is schedulable. 




 
\end{abstract}

\maketitle
\section{Introduction}
Random walks are popular in combinatorics \cite{BolRio05,Gacs02,Gacs04,Vilenkin72,Winkler00} and in physics  
\cite{BalBol04,Grimmett99,Kesten82,Schauffer85} too.

In this paper we investigate a problem of percolation \cite{Gacs02,Gacs04,Kesten82,Schauffer85}, 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. 


\section{Formulation of the problem}
Let $m$ and $n$ be positive integers, let $r \ (0 \leq r \leq m)$ be a real number and let 
\begin{equation}
\mathbf{Z} = \left(
\begin{array}{cccc}
z_{11} & z_{12} & \ldots & z_{1n} \\
z_{21} & z_{22} & \ldots & z_{2n} \\
\ldots &       &         & \\
z_{m1} & z_{m2}  & \ldots  & z_{mn}
\end{array}
\right)
\end{equation}
be a matrix of independent random variables with the common distribution
\begin{equation}
P(z_{ij} = k) = \left \{
\begin{array}{cc}
p,         & \mbox{ if } k = 1 \mbox{ and } 1 \leq i \leq m, \ 1 \leq j \leq n, \\
q = 1 - p, & \mbox{ if } k = 0 \mbox{ and } 1 \leq i \leq m, \ 1 \leq j \leq n. 
\end{array}
\right .
\end{equation}

Let
\begin{equation}
\mathbf{A} = \left(
\begin{array}{cccc}
a_{11} & a_{12} & \ldots & a_{1n} \\
a_{21} & a_{22} & \ldots & a_{2n} \\
\ldots &       &         & \\
a_{m1} & a_{m2}  & \ldots  & a_{mn}
\end{array}
\right)
\end{equation}
be a concrete realization of $\mathbf{Z}.$

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

Matrix $A$ is called \textit{\textbf{r}}\textbf{-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 \times n$ 
is denoted by $G_r(m,n)$ and the probability that $\mathbf{Z}$ is good is denoted by $g_r(m,n,p).$

Matrix $A$ is called \textit{\textbf{r}}\textbf{-safe}, if 
\begin{equation}
\sum_{i=1}^m \sum_{j=1}^k a_{ij} \leq kr \quad (k =1, 2, \ldots, n).\label{eq:safe}
\end{equation}

The number of different $r$-safe matrices of size $m \times n$ 
is denoted by $S_r(m,n)$ and the probability that $\mathbf{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},\ldots,a_{im}$ and add $a_{im} = 0$ to the $i$-th row of $A.$

Matrix $A$ is called \textbf{Winkler \textit{r}-schedulable} (shortly \textbf{$r$-schedulable} 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 \times n$ is denoted by $W_r(m,n)$ and the probability 
that $\mathbf{Z}$ is $r$-schedulable is denoted by $w_r(m,n,p).$ The function $w_r(m,n,p)$ is called 
\textbf{\textit{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 \textbf{asymptotic density} of the good, safe and schedulable 
matrices are defined as  
\begin{equation}
g_r(m,p) = \lim_{n\rightarrow \infty} g_r(m,n,p),
\end{equation} 
\begin{equation}
s_r(m,p) = \lim_{n\rightarrow \infty} s_r(m,n,p), 
\end{equation}
\begin{equation}
w_r(m,p) = \lim_{n\rightarrow \infty} w_r(m,n,p).
\end{equation}

\textbf{The critical probabilities} defined as
\begin{equation}
w_{\textit{crit,r}}(m) = \sup \{ p \ | \ w_r(m,p) > 0 \},
\end{equation}
\begin{equation}
g_{\textit{crit,r}}(m) = \sup \{ p \ | \ g_r(m,p) > 0 \},
\end{equation}
and
\begin{equation}
s_{\textit{crit,r}}(m) = \sup \{ p \ | \ s_r(m,p) > 0 \}
\end{equation}
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 \cite{Gacs04} proving that $w_1(2,p)$ is positive 
for $p$ small enough. His proof implies that $w_{\textit{crit},1}(2) \geq 10^{-400}.$ 

We remark that some recent papers are closely connected with our efforts: \cite{IvaLan05} enumerates 
some $r$-safe matrices, \cite{Iva05} presents density of $2$- and $(m/2)$-safe matrices and \cite{IvaSze05} 
investigates algorithms generating all safe and schedulable matrices.

\subsection{Interpretation of the problem}
Bár a Winkler-modellt a perkoláció leírására javasolták, 
a problémák egy-egy 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 az  
$a_{i1},a_{i2},\ldots,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 \cite{Vilenkin72} 
és szavazási probléma \cite{Feller68}, az $m = 2$ és $r = 2$ speciális eset pedig a 
Winkler-féle perkolációs modell \cite{Gacs04,Winkler00}.  

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 \cite{Feller68} informatikai 
(tömegkiszolgálási) terminológiáját használjuk.



\section{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:

\begin{itemize}
\item
$n \in \mathbb{N}^+, \ r \in \mathbb{R}$ and $r \in [0,m],$ 
$p \in \mathbb{R}$ and $p \in [0,1];$
\item
$n$ szerint monoton csökkenők;
\item
$p$ szerint monoton csökkenők;
\item
$m$ szerint monoton csökkenők;
\item
$r$ szerint monoton növekvők.
\end{itemize}

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.

 
\subsection{Preliminary results}
A későbbiekben felhasználjuk az alábbi állításokat.

Jelöljük $C_n$-nel $(n \in \mathbb{N}^+)$ azon $a_1,a_2,\ldots,a_{2n}$ bináris sorozatok számát, amelyekben  
$n$ darab egyes és $n$ darab nulla van úgy, hogy minden $a_1,a_2,\ldots,a_k \ (1\leq k \leq 2n)$ 
kezdősorozatban legfeljebb annyi egyes van, mint nulla.  

\begin{lemma} If $n \geq 0,$ then
$$C_n = \frac{1}{n + 1} \binom{2n}{n}.$$
\end{lemma}

Megjegyezzük, hogy $C_n$ az $n$-edik Catalan-szám, melynek explicit alakja számos tankönyvben és cikkben   
\cite{BegeKasa01,Vilenkin72} megtalálható. 

\begin{lemma} If $0 \leq x \leq 1,$ then\label{lemma:fx}
\begin{equation} 
f(x) = x \sum_{k=0}^\infty \frac{1}{k + 1}\binom{2k}{k}(x(1 - x))^k = 
\left \{
\begin{array}{cc}
\frac{x}{1 - x}, & \mbox{ if } 0 \leq x < \frac{1}{2}, \\
1,               & \mbox{ if } \frac{1}{2} \leq x \leq 1.\\
\end{array}
\right.
\end{equation}
\end{lemma}
\begin{proof}
\end{proof}

If $m \geq 2,$ then the columns containing only 0's are called \textbf{white} (W), 
the columns containing exactly one 1 are called \textbf{grey} (G)
and the remaining columns are called \textbf{black} (B).  
 
Ha $m \geq 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) = 
\left ((q^m + mq) \right) ^n.$ Ha $p > 0,$ akkor 
\begin{equation}
g(m,p) = \lim_{n \rightarrow \infty} \left (q^m + mq \right)^n = 0,
\end{equation}
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 \textit{komplementere.}

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

\begin{lemma} If $m \geq 2,$ then the good matrices are schedulable,  
the schedulable matrices are safe.
\end{lemma}
\begin{proof} Ha az $\mathbf{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 \leq k \leq n),$ amelyre az
$\mathbf{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 $\textbf{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 $\textbf{A}$ nem ütemezhető. 
\end{proof}

Ennek az állításnak hasznos következménye az alábbi.
\begin{corollary} If $m \geq 2,$ then 
\begin{equation}
g(m,n,p) \leq w(m,n,p) \leq s(m,n,p),
\end{equation}
\begin{equation}
g(m,p) \leq w(m,p) \leq s(m,p),
\end{equation}
\begin{equation}
g_{\textit{crit}}(m) \leq w_{\textit{crit}}(m) \leq s_{\textit{crit}}(m).
\end{equation}
\end{corollary}


\subsection{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.
\begin{lemma} If $n \geq 1,$ then
\begin{equation}
u(2,n,p) = \sum_{i=1}^n \sum_{j = 0}^{\lfloor (i-1)/2 \rfloor} 2^{i-1-2j} C_j \binom{i -1}{2j} 4^{n-i} .\label{eq:U2n}
\end{equation}
\end{lemma}
\begin{proof}
A lehetséges $2 \times 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 \textit{döntő oszlopnak} nevezzük). 

A döntő oszlop indexe  $0, 1, \ldots, 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, \ldots, \ \lfloor (n -1)/2 \rfloor$ 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. 
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.
\end{proof}

Az $u(2,n,p)$-re kapott (\ref{eq:U2n}) 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. 


\begin{lemma} If $0 \leq p \leq 1,$ then \label{lemma:s2p}
\begin{equation}
u(2,p) = \left \{
\begin{array}{cc}
\frac{p^2}{q^2},     & \quad \mbox{if } 0 \leq p < \frac{1}{2}, \\
1,                   & \quad \mbox{if } \frac{1}{2} \leq p \leq 1.
\end{array}
\right.
\end{equation} 
\end{lemma}
\begin{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
$$
\sum _{a=0}^\infty  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}WG^{c}BA^{d},$ 
ahol $a+b+c+d+3 = n.$ Az ilyen mátrixok aszimptotikus részaránya 
$$\sum _{a=0}^\infty (2pq)^{a} p^2 \sum _{b=0}^\infty (2pq)^{b} 
q^2 \sum _{c=0}^\infty (2pq)^{c} p^2 = \frac{p^2}{1-2pq} C_1 \frac{p^2}{1-2pq} \frac{q^2}{1-2pq} \ .$$

Á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 \left (\frac{p^2}{1-2pq} \frac{q^2}{1-2pq}\right )^2,
$$
és így
$$
u(2,p)=\sum_{i=0}^\infty \frac{p^2}{1-2pq} C_i \left (\frac{p^2}{1-2pq} \frac{q^2}{1-2pq}\right )^i.
$$
A $p^2/(p^2+q^2)=x$ és $q^2/(p^2+q^2)=1-x$ helyettesítéssel alkalmazva a \ref{lemma:fx}. lemmát megkapjuk a 
kívánt képletet.
\end{proof}

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 = \left \{ 
\begin{array}{ll}
-1,                                & \mbox{ if } \exists k \mbox{ with } k < \sum_{i=1}^k (a_{i1} + a_{i2}), \\
k - \sum_{i=1}^k (a_{i1} + a_{i2}) & \mbox{otherwise.}
\end{array}
\right.
$$
 
Ekkor a \ref{lemma:s2p}. lemma egy másik bizonyítása a következő. 


\begin{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, 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
\begin{equation}
x = p^2 + 2pqx + q^2x^2.
\end{equation}

Ennek az egyenletnek a gyökei
\begin{equation}
x_{1,2} = \frac{1 - 2pq \pm \sqrt{(1 - 2pq)^2 - 4p^2q^2}}{2q^2} = \frac{p^2 + q^2 \pm \sqrt{(p^2 - q^2)^2}}{2q^2} \ ,
\end{equation}
ahonnan
\begin{equation}
x_1 = \frac{p^2}{q^2}, \mbox{ and } x_2 = 1.\label{eq:tworowsroots}
\end{equation} 
Innen $s(2,p)=1-u(2,p)$ alapján megkapjuk a bizonyítandó képletet. 
\end{proof}

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 
$\mathbf{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 \ref{lemma:s2p}. lemma egy másik bizonyítása a következő.

\begin{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  
\begin{equation}
a = \frac{p^2}{p^2 + q^2} \quad \mbox{és} \quad b = \frac{q^2}{p^2 + q^2}.\label{eq:ab}
\end{equation}
Ezekkel a valószínűségekkel a 
\begin{equation} 
x = a + bx^3
\end{equation}
egyenletet kapjuk. Ennek  megoldásaiba (\ref{eq:ab}) szerint visszahelyettesítve $a$ és $b$ helyére a 
$p$ és $q$ valószínűségeket, itt is megkapjuk a (\ref{eq:tworowsroots}) képlet szerinti gyököket.
\end{proof}

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

\begin{proof}
Jelöljük $x_k$-val $(k = -1, 0, 1, 2, \ldots)$ 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.
\begin{equation}
\begin{array}{ccccccc}
x_0 & = & q^2x_1  & + & 2qpx_0  & + & p^2, \\
x_1 & = & q^2x_2  & + & 2qpx_1  & + & p^2x_0, \\ \label{eq:threerows}
x_2 & = & q^2x_3  & + & 2qpx_2  & + & p^2x_1, \\
x_3 & = & q^2x_4  & + & 2qpx_3  & + & p^2x_2, \\
\cdots \\
\end{array}
\end{equation} 

Legyen 
\begin{equation}
G(z) = \sum_{i=1}^\infty x_iz^i
\end{equation}
az $x_0,x_1,x_2,\ldots$ sorozat generátorfüggvénye. A (\ref{eq:threerows}) egyenletrendszer  
$x_i$-vel kezdődő egyenleteit rendre $z^i$-vel beszorozva és az egyenleteket összeadva a 
\begin{equation}
G(z) = q \frac{G(z)-x_0}{z} + 2pqG(z)+p^2(1+zG(z)).
\end{equation}

Innen $G(z)$ kifejezhető
\begin{equation}
G(z) = \frac{P(z)}{Q(z)}
\end{equation}
alakban, ahol
\begin{equation}
P(z) = q^2 - p^2z
\end{equation}
és
\begin{equation}
Q(z) = p^2z^2 + 2pq + p^3 - z.
\end{equation}
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
\begin{equation}
(pz + q)^2 = 1
\end{equation}
alakban felírva közvetlenül adódik, hogy $z = 1$ gyöke a $Q(z)$ polinomnak. A $P(1) = 0$ egyenletből 
az 
\begin{equation}
x_0 = \frac{p^2}{q^2}
\end{equation}
megoldást kapjuk.
\end{proof}

A \ref{figure:abra201}. á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.

\begin{figure}[!ht]
\begin{center}
\resizebox{80mm}{!}{
\includegraphics{abra201.eps}}
\caption{Curve of the schedulability function $s(2,p,1)$\label{figure:abra201}}
\end{center}
\end{figure}


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
\begin{equation}
0 = g_{\textit{crit}}(2) \leq w_{\textit{crit}}(2) \leq s_{\textit{crit}}(2) = \frac{1}{2} \ .
\end{equation}


Emlékeztetünk Gács eredményére, amely szerint $w_{\textit{crit}}(2) \geq 10^{-400}.$

A \ref{table:p50}. 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, \ldots, 15 vagy 16.  

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

\begin{center}
\begin{figure}[!t]
\begin{tabular}{|r|r|r|r|r|r|r|r|}  \hline \hline
$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)}$ \\ \hline \hline
1   &3       & 0.750                 & 3      & 0.750                  &  3      
             & 0.750                 & 1           \\ \hline
2   & 9      & 0.562                 & 10     & 0.625                  &  10 
             & 0.625                 & 1        \\ \hline
3   & 27     & 0.452                 & 35     & 0.547                  & 35 
             & 0.547  & 1              \\ \hline
4   & 81     & 0.316                 &  124   & 0.484                  & 126 
             & 0.492  & 0.984             \\ \hline
5   & 243    & 0.237                 &  444   & 0.434                  & 462 
             & 0.451  & 0.961      \\ \hline
6   & 729    & 0.178                 &  1592  & 0.389                  & 1716 
             & 0.419  & 0.927        \\ \hline
7   & 2187   & 0.133                 &  5731  & 0.350                  & 6435 
             & 0.393  & 0.890         \\ \hline
8   & 6561   & 0.100                 &  20671 & 0.315                  & 24310 
             & 0.371  & 0.850       \\ \hline
9   & 19683  & 0.075                 & 74722  & 0.285                  & 92378 
             & 0.352  & 0.808            \\ \hline
10  & 59049  & 0.056                 & 270521 & 0.258                  & 352716 
             & 0.336  & 0.767           \\ \hline 
11  & 177147 & 0.042                 & 980751 & 0.234                  & 1352078 
             & 0.322  & 0.725            \\ \hline 
12  & 531441 & 0.032                 & 3559538& 0.212                  & 5200300 
             & 0.310  & 0.684             \\ \hline 
13  &1594323 & 0.022                 &12931155& 0.193                  & 20058300 
             & 0.299  & 0.646              \\ \hline 
14  &4782969 & 0.018                 &47013033 &0.175                  &77558760 
             & 0.289  &0.606             \\ \hline
15  &14348907&0.013                  &171036244 &0.159                 &300540195
             & 0.280  &0.568             \\ \hline \hline
\end{tabular}
\caption{Rounded data belonging to $p =1/2$\label{table:p50}}
\end{figure}
\end{center}

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.


\begin{center}
\begin{figure}[!t]
\begin{tabular}{|r|r|r|r|r|r|}  \hline \hline
$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)}$ \\ \hline \hline
1   &  4        &  0.8400   & 0.8400                 &  0.8400 & 1           \\ \hline
2   &  16       &  0.7056   & 0.7632                 &  0.7632 & 1         \\ \hline
3   &  64       &  0.5927   & 0.7171                 &  0.7171 & 1           \\ \hline
4   &  256      &  0.4979   & 0.6795                 &  0.6862 & 0.9902        \\ \hline
5   &  1024      & 0.4182   & 0.6487                 &  0.6639 & 0.9771   \\ \hline
6   &  4096      & 0.3513   & 0.6206                 &  0.6470 & 0.9592        \\ \hline
7   &  16384     & 0.2951   & 0.5957                 &  0.6339 & 0.9397        \\ \hline
8   &  65536     & 0.2479   & 0.5731                 &  0.6234 & 0.9193     \\ \hline
9   &  262144    & 0.2082   & 0.5524                 &  0.6149 & 0.8984     \\ \hline 
10  &  1048576   & 0.1749   & 0.5332                 &  0.6078 & 0.8773     \\ \hline 
11   & 4194304   & 0.1469   & 0.5155                 &  0.6019 & 0.8565     \\ \hline 
12   & 16777216  & 0.1234   & 0.4988                 &  0.5967 & 0.8359    \\ \hline 
13   & 67108864  & 0.1037   & 0.4832                 &  0.5924 & 0.8157    \\ \hline 
14  & 268435456  & 0.0871   & 0.4685                 &  0.5886 & 0.7960   \\ \hline 
15  & 1073741824 & 0.0731   & 0.4545                 &  0.5854 & 0.7764    \\ \hline 
16  & 4294967296 & 0.0644   & 0.4412                 &  0.5825 & 0.7574    \\ \hline 
17  &169779869184& 0.0516   & 0.4286                 &  0.5800 & 0.7390    \\ \hline \hline
\end{tabular}
\caption{Rounded data belonging to $p = 0.4$\label{table:p40}}
\end{figure}
\end{center}

A \ref{table:p40}. 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.

\begin{center}
\begin{figure}[!t]
\begin{tabular}{|r|r|r|r|r|r|}  \hline \hline
$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)}$  \\ \hline \hline
1   &  4        &  0.8775   & 0.8775                 &  0.8775 & 1           \\ \hline
2   &  16       &  0.7700   & 0.8218                 &  0.8218 & 1         \\ \hline
3   &  64       &  0.6757   & 0.7901                 &  0.7901 & 1           \\ \hline
4   &  256      &  0.5929   & 0.7645                 &  0.7699 & 0.9930        \\ \hline
5   &  1024      & 0.5203   & 0.7441                 &  0.7561 & 0.9841   \\ \hline
6   &  4096      & 0.4565   & 0.7255                 &  0.7462 & 0.9723        \\ \hline
7   &  16384     & 0.4006   & 0.7094                 &  0.7389 & 0.9601       \\ \hline
8   &  65536     & 0.3515   & 0.6949                 &  0.7334 & 0.9475    \\ \hline
9   &  262144    & 0.3085   & 0.6817                 &  0.7291 & 0.9350    \\ \hline 
10  &  1048576   & 0.2707   & 0.6696                 &  0.7258 & 0.9226     \\ \hline 
11   & 4194304   & 0.2375   & 0.6585                 &  0.7231 & 0.9107     \\ \hline 
12   & 16777216  & 0.2084   & 0.6481                 &  0.7210 & 0.8989     \\ \hline 
13   & 67108864  & 0.1839   & 0.6383                 &  0.7192 & 0.8875   \\ \hline 
14  & 268435456  & 0.1605   & 0.6291                 &  0.7178 & 0.8764    \\ \hline 
15  & 1073741824 & 0.1401   & 0.6204                 &  0.7166 & 0.8658    \\ \hline
16  & 4294967296 & 0.1236   & 0.6122                 &  0.7156 & 0.????    \\ \hline \hline
\end{tabular}
\caption{Rounded data belonging to $p = 0.35$\label{table:p35}}
\end{figure}
\end{center}

A \ref{table:p35}. táblázatban a $s(2,n,0.35)$ oszlop számainak 
a $120/169 \sim 0.7101$ határértékhez kell tartaniuk.




\subsection{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^2q$ 
valószínűségével lépünk balra, az egy egyest tartalmazó oszlopok $3p^2$ valószínűségével 
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: 

\begin{equation}
\begin{array}{ccccccccc}
x_0 & = & q^3x_1  & + & 3q^2px_0 & + & 3qp^2    & + & p^3, \\
x_1 & = & q^3x_2  & + & 3q^2px_1 & + & 3qp^2x_0 & + & p^3, \\ \label{eq:threerows}
x_2 & = & q^3x_3  & + & 3q^2px_2 & + & 3qp^2x_1 & + & p^3x_0, \\
x_3 & = & q^3x_4  & + & 3q^2px_3 & + & 3qp^2x_2 & + & p^3x_1, \\
\cdots \\
\end{array}
\end{equation}

Legyen
\begin{equation}
G(z) = \sum_{i=0}^{\infty} x_n z^n
\end{equation}
az $x_0,x_1,x_2,\ldots$ sorozat generátorfüggvénye. Akkor a (\ref{eq:threerows}) egyenleteket rendre beszorozva 
$z$ megfelelő hatványával és összeadva őket azt kapjuk, hogy
\begin{equation}
G(z) = q^3\frac{G(z)-x_0}{z} + 3q^2p\frac{G(z)}{z} +
 3qp^2(1 + zG(z)) + p^3 \left(1+z+z^2G(z) \right ),
\end{equation}
ahonnan
$G(z)$ kifejezhető két polinom hányadosaként:
\begin{equation}
G(z) = \frac{P(z)}{Q(z)},
\end{equation}
ahol
\begin{equation}
P(z) = q^3x_0 - 3qp^2z - p^3(z + z^2) 
\end{equation}
és
\begin{equation}
Q(z) = p^3z^3 + 3p^2qz^2 + 3pq^2z + q^3 - 1.
\end{equation}

A $Q(z) = 0$ egyenletet 
\begin{equation}
(q + pz)^3 = 1
\end{equation}
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
\begin{equation}
x_0 = 3t^2 + 2t^3
\end{equation}
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)$ értéket visszahelyettesítve és $(1-p)^3$-nel beszorozva a
\begin{equation}
\frac{3p^2}{(1-p)^2} + \frac{2p^3}{(1-p)^3} = 1
\end{equation}
egyenletet kapjuk, amelyből rendezés után a $p = 1/3$ értéket kapjuk, azaz $s_{\textit{crit}}(3) = 1/3.$ 

\begin{center}
\begin{figure}[!t]
\begin{tabular}{|r|r|r|r|r|r|}  \hline \hline
$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)}$ \\ \hline \hline
1   &  8        &  0.5000   & 0.5000                 &  0.5000 & 1           \\ \hline
2   &  64       &  0.2500   & 0.2969                 &  0.2969 & 1         \\ \hline
3   &  256      &  0.1250   & 0.1914                 &  0.1914 & 1           \\ \hline
4   &  4096     &  0.0625   & 0.???                 &  0.??? & ???        \\ \hline
5   &  32768    &  0. & 0.                 &  0. & 0.????    \\ \hline \hline
\end{tabular}
\caption{Rounded data belonging to $m = 3$ and  $p = 0.5$\label{table:p35}}
\end{figure}
\end{center}



\section{Main result}
Az $m \times n$ méretű biztos mátrixok elemzését az $m \geq 4$ esetben az $m = 3$ 
esethez hasonló módon végezhetjük el. 

A bolyongó pont a legalább $b \geq 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. 

\begin{equation}
\begin{array}{ccccccccccc}
x_0 & = & \binom{m}{0}q^mx_1     & + & \binom{m}{1}pq^{m-1}x_0 & + & \binom{m}{2}p^2q^{m-2}  \\
    & + & \binom{m}{3}p^3q^{m-3} & + & \ldots                  & + & \binom{m}{m}p^{m}, \\
x_1 & = & \binom{m}{0}q^mx_2     & + & \binom{m}{1}pq^{m-1}x_1 & + & \binom{m}{2}p^2q^{m-2}x_0  \\ 
    & + & \binom{m}{3}p^3q^{m-3} & + & \ldots                  & + & \binom{m}{m}p^{m}, \\ \label{eq:fourr}
x_2 & = & \binom{m}{0}q^mx_3x_3  & + & \binom{m}{1}pq^{m-1}x_2 & + & \binom{m}{2}p^2q^{m-2}x_1 \\
    & + & \binom{m}{3}p^3q^{m-3}x_0&+& \ldots                  & + & \binom{m}{m}p^{m}, \\
\cdots \\
\end{array}
\end{equation}

Legyen
\begin{equation}
G(z) = \sum_{i=0}^{\infty} x_n z^n
\end{equation}
az $x_0,x_1,x_2,\ldots$ sorozat generátorfüggvénye. Akkor a (\ref{eq:fourr}) 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^2q^{m-2}(1 + zG(z)) 
+ \binom{m}{3}p^3q^{m-3}(1 + zG+z^2G(z)) + \cdots $$
$$+ \binom{m}{m}q^m \left(1+z+\cdots + z^{m-2}+z^{m-1}G(z) \right ),$$
ahonnan
$G(z)$ kifejezhető két polinom hányadosaként:
\begin{equation}
G(z) = \frac{P(z)}{Q(z)},
\end{equation}
ahol
\begin{equation}
P(z) = \sum_{i=0}^m    \binom{m}{i} p^iq^{m-i}z^i - z. 
\end{equation}
és
\begin{equation}
Q(z) = \binom{m}{0} q^mx_0 - \sum_{i=0}^m \binom{m}p^iq^{m-i}\sum_{j=0}^{i-2} z^j.
\end{equation}


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 
\begin{equation}
(q + pz)^m = 1
\end{equation}
alakra hozhatjuk, ahonnan a $z_1 = 1$ gyököt kapjuk. A $P(1) = 0$ egyenletet 
$q^m$-nel osztva az
\begin{equation}
x_0 = \sum_{i=0}^m \binom{m}{0}\left ( \frac{p}{1-p} \right )^i (i - 1)
\end{equation}
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.

\begin{theorem} If $m \geq 2$ and $0 \leq p \leq 1,$ then
\begin{equation}
s(m,p) = 1 - \sum_{i=2}^m \binom{m}{i} \left ( \frac{p}{1-p} \right )^i (i - 1)
\end{equation}
and
\begin{equation}
s_{\textit{crit}}(m) = \frac{1}{m}.
\end{equation}
\end{theorem}

\section{Summary}
Az $m \geq 2$ sort tartalmazó mátrixokra megadtuk az ütemezhetőségi függvény explicit alakját 
és meghatároztuk az $s_{\textit{crit}}(m)$ kritikus valószínűségeket. $s_{\textit{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 \ref{table:p50}. táblázat a $p=0.5,$ a \ref{table:p40}. táblázat a $p=0.4,$  a 
\ref{table:p35}. 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 
\cite{Gacs04} 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.


\bigskip
\textbf{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 of Eötvös Loránd University), Zoltán Kása and József Kolumbán 
(both Babe\c s-Bolyai University) for their useful remarks and Rudolf Szendrei 
(Eötvös Loránd University) for the computer experiments.  


\begin{thebibliography}{9}
\large
\bibitem{BalBol04} P. Balister, B. Bollobás, M. Walters (2004),  
\textit{Continuum percolation with steps in an annulus.} 
\textit{Ann. Appl. Probab.} \textbf{14/4} 1869--1879. 
http://arxiv.org/find.

\bibitem{BegeKasa01} A. Bege and Z. Kása (2001), \emph{Coding objects related to Catalan numbers},  
Studia Univ. Babe\c s-Bolyai, Informatica, Volume XLVI (1), 31--39.
http://www.cs.ubbcluj.ro/$\sim$studia-i/contents.php.

\bibitem{BolRio05} B. Bollobas, O. Riordan (2005), \emph{A short proof of the Harris-Kesten theorem}. 
Electronic manuscript, http://arxiv.org/find. 

\bibitem{Feller68} W. Feller, (1968), \emph{An Introduction to Probability Theory and its Applications.}
John Wiley and Sons, New York. 

\bibitem{Gacs02} P. Gács (2002), \emph{Clairvoyant scheduling of random walks} 
(submitted to Electronic Journal of Probability). 
Short version:  \textit{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.

\bibitem{Gacs04} P. Gács (2004), \emph{Compatible sequences and a slow Winkler percolation}. 
Combin. Probab. Comput. \textbf{13/6}, 815--856. http://www.cs.bu.edu/fac/gacs/recent-publ.html.

\bibitem{Grimmett99} G. R. Grimmett, (1999), \emph{Percolation.} Springer, Berlin, 1999. 

\bibitem{Harris60} T. E. Harris (1960), \emph{A lower bound for the critical probability in a certain 
percolation process}. Proc. of the Cambridge Phil. Soc. \textbf{56} 13--20.

\bibitem{Kesten82} H. Kesten (1982), \emph{Percolation Theory for Mathematicians.} Birkhäuser, Boston.


\bibitem{Schauffer85} D. Schauffer (1985), \textit{Introduction to Percolation Theory.} 
Taylor \& and Francis, London, 1985.

\bibitem{Stanley99} R. P. Stanley (1999), \emph{Enumerative Combinatorics, Volume 2.} Cambridge Studies 
in Advanced Mathematics, 62. Cambridge University Press, Cambridge.


\bibitem{Vilenkin72} N. J. Vilenkin (1972), \emph{Combinatorial Mathematics for Recreation}. Mir Publisher, Moscow. 

\bibitem{Winkler00} P. Winkler (2000), \emph{Dependent percolation and colliding random walks,} 
Random Structures \& Algorithms \textbf{16/1} 58--84. http://www.math.dartmouth.edu/$\sim$pw/papers/pubs.html.

\end{thebibliography}
\end{document}
