Introduction

Random walks on random graphs arise among others in several models in Network science, Neuroscience and Statistical Mechanics [AF02,Bol01,FK16,New10].

A random walk of length k on a possibly infinite graph G with a root 0 is a stochastic process with random variables X 1 , X 2 , . . . , X k such that X 1 = 0 and X i+1 , is a vertex chosen uniformly at random from the neighbors of X i , i = 1, . . . , k − 1. Then P k v,w (G) is the probability that a random walk of length k starting at v ends at w. In particular, if G is a graph with root 0, P 2k 0,0 (G), is the probability that a 2k-step random walk returns to 0. In the context of Random Graph theory, random walks have been defined as Markov chains and their properties have been studied in details. These include among others, the distribution of first and last hitting times of the random walk, where the first hitting time is given by the first time the random walk steps into a previously visited edge of the graph, and the last hitting time corresponds the first time the random walk cannot perform an additional move without revisiting a previously visited edge, the continuous analogue of the random walk.

A question that can be arisen in real world network phenomena is what if the random selection of a neighbor vertex is varying by the number of the previously visited vertices? The study of such random walks on random graphs can be realized by considering random walks on d-dimensional integer lattices, d ≥ 1, with transition probabilies varying by the number of steps.

In this work, we introduce nearest neighbour random walks on the integers and on the two-dimensional integer lattice with transition probabilities q-varying by the number of steps, 0 < q < 1. These q-random walks are defined as Markov chains discrete time stochastic processes. Our main results characterize under which conditions the considered q-random walks are transient or reccurent. Also, we define the relative continuous time q-random walks stochastic processes. Moreover, we present a q-Brownian motion as a continuous analogue of the q-random walk stochastic process on the integers. The maxima and first hitting time of this q-Brownian motion are studied. Furthermore, we produce simulations in R of all the considered stochastic processes, indicating first hitting times to the origin. As further study, we propose nearest neighbour q-random walks on the three-dimensional integer lattiice. q-Random walks in square or triangular lattices, where a vertex is added to one of the four or six directions respectively, according to edge (transition) probabilities varying by the number of previously visited vertices, can be applied to describe among others several real world phenomena arising in networkscience, neuroscience and statistical mechanics.

Preliminaries, Definitions and Notation

Markov Chains and Classification of States

Let a discrete time stochastic process {X(t), t ∈ T }, where T a countable set. If T is the set of nonnegative integers, then the process is denoted as X n , n = 0, 1, 2, . . . . If X n = i, then the process is said to be in state i at time n. The one-step transition probability from state i to state j, say P i,j , is given by

P i,j = P (X n+1 = j + 1/X n = i, X n−1 = i n−1 , . . . , X 0 = i 0 ) ,(1)

for all states i 0 , i 1 , . . . , i n−1 , i, j, n ≥ 0. This stochastic process is known as a Markov chain.

The n-step transition probability, say P n i,j , is given by

P n i,j = P (X n+m = j + 1/X m = i) , n ≥ 0, i, j ≥ 0. (2)

If P n i,j > 0 for some n ≥ 0, we say that state j is accessible from state i. States i and j communicate if state j is accessible from state i and state i is accessible from state j. The Markov chain is said to be irreducible if all states communicate with each other.

A state i is recurrent if with probability 1, the process will reenter state i. A state i is transient if with probability< 1, the process will reenter state i.

A state i is recurrent if ∞ n=0 P n i,i = ∞. A state i is transient if ∞ n=0 P n i,i < ∞.

If state i is recurrent and state i communicates with state j, the state j is recurrent.

2.2 q-Series Preliminaries, 0 < q < 1 The q-binomial coefficient is defined by

n k q := (q; q) n (q; q) k (q; q) n−k = [n] q ! [k] q ![n − k] q , where [n] q ! = [1] q [2] q . . . [n] q = (q; q) n (1 − q) n = n k=1 (1 − q k ) (1 − q) n

is the q-factorial number of order n with [t] q = 1−q t 1−q . The q-binomial coefficient n k q , for n and k positive integers, equals the k-combinations {m 1 , m 2 , . . . , m k } of the set {1, 2, . . . , n}, weighted by

q m1+m2+•••+m k −( k+1 2 ) , 1≤m1<m2<•••<m k ≤n q m1+m2+•••+m k −( k+1 2 ) = n k q . (3)

Let n be a positive integer and let x, y and q be real numbers, with q = 1. Then, a version of q-Cauchy formula is

x + y n q = n k=0 q k(y−n+k) x k q y n − k q . (4)

The q-multinomial coefficient is defined by

n k 1 , k 2 , . . . , k r−1 q = [n] q ! [k 1 ] q ![k 2 ] q ! • • • [k r−1 ] q ![k r ] q ! ,(5)

where

k r = n − k 1 − k 2 − • • • − k r−1 ,

for k i = 0, 1, 2, . . . , n, i = 1, 2, . . . , r,n = 0, 1, 2, . . . . Kyriakoussis and Vamvakari [KV13], have established the following q-Stirling formula for n → ∞, of the q-factorial number of order n,

[n] q ! ∼ = (2π(1 − q)) 1/2 (q log q −1 ) 1/2 q ( n 2 ) q −n/2 [n] n+1/2 1/q ∞ j=1 (1 + (q −n − 1)q j−1 ) . (6)

Let a sequence of q-Bernoulli trials with varying probability of success at the ith trial,

p i = θq i−1 1 + θq i−1 , i = 1, 2, . . . , 0 < q < 1, 0 < θ < ∞.

Then the probability function (p.f) of the number X of successes at n such trials is given by

f X (x) = P (X = x) = n x q q ( x 2 ) θ x n j=1 (1 + θq j−1 ) , x = 0, 1, . . . , n,(7)

for θ > 0, 0 < q < 1. The distribution of the random variable (r.v.) X is called q-binomial distribution of the first kind, with parameters n, θ and q (see Charalambides [Cha16]).

3 Main Results

q-Random Walks on the Integers

In this section, we introduce a nearest neighbour q-random walk on the integers with transition probabilities q-varying by the number of steps, 0 < q < 1. This random walk is defined as a Markov chain discrete time stochastic process.

Definition 3.1. The Markov chain whose state space is the set of all integers with q-varying transition probabilities, 0 < q < 1, given by

P i,i+1 = θq i−1 1 + θq i−1 = 1 − P i,i−1 , i = 0, ±1, ±2, . . . , 0 < q < 1, 0 < θ < ∞ (8)

is called q-random walk on the integers.

At each state of the q-random walk the chain either increases or dicreases by 1, with respective probabilities P i,i+1 and P i,i−1 , i = 0, 1, 2, . . . , of independent q-Bernoulli trials. Because all states communicates, they are either all transient or recurrent. Therefore, we consider state 0 and determine whether ∞ n=0 P n 0,0 is finite or infinite. Because it is impossible to be back in the initial state after an odd number of transitions, we have that

∞ n=0 P 2n+1 0,0 = 0, n ≥ 0.

But the chain will be back in initial state after 2n transitions if n of them were increases and n of them were decreases. Because each q-Bernoulli trial results in an increased state with probability P i,i+1 , i = 1, 2, . . . , 2n, by the p.f. (7), the desired probability is the q-binomial probability of the first kind

P 2n 0,0 = 2n n q q ( n 2 ) θ n 2n j=1 (1 + θq j−1 ) , θ > 0, 0 < q < 1. (9)

By using q-Stirling formula (6), the next theorem is concluded.

Theorem 3.2. The q-random walk on the integers after 2n steps, starting from the origin 0, for θ constant or for θ = q −αn , 0 < a < 1, n = 0, 1, 2, . . . is recurrent, while for θq n → ∞, as n → ∞, is transient. Next, we present the relative continuous time q-random walk stochastic process. Analytically, consider the time interval (0, t], t > 0, and partition it into parts which are geometrically decreasing with rate q, defined by δ i (n; t) = (n) −1 q q i−1 t, i = 1, 2, . . . , n, n ≥ 1. Also, consider the process generated by making a step of length δ = 1 to the right and a step of length δ = 1 to the left at every time period (n) −1 q q i−1 t, i = 1, 2, . . . , n, with probability of success (right step) and probability of failure (left step) given respectively by

P (X i = δ) = θ(n) −1 q q i−1 t 1 + θ(n) −1 q q i−1 t and P (X i = −δ) = 1 1 + θ(n) −1 q q i−1 t , (10)

where 0 < q < 1, 0 < θ < ∞. Then, at time n i=1 δ i (n; t) = t the position of the process is the r.v. X n,q (t) = n i=1 X i . Definition 3.4. The continuous time stochastic process {X n,q (t), t ≥ 0}, is called q-random walk stochastic process with parameters q, n and θ, if the following properties hold (a) In each of the consecutive mutually disjoint time intervals of length δ i (n; t) = (n) −1 q q i−1 t, i = 1, 2, . . . , n, n ≥ 1, at most one event (right or left step) occurs and

P X n,q 1 − q i 1 − q n t − X n,q 1 − q i−1 1 − q n t = δ = θq i−1 t (n)q 1 + θq i−1 t (n)q , (11) P X n,q 1 − q i 1 − q n t − X n,q 1 − q i−1 1 − q n t = −δ = 1 1 + θq i−1 t (n)q , δ = 1, i = 1, 2, . . . , n, 0 < θ < ∞. (b) The increments X n,q (t i ) − X n,q (t i−1 ), where t i − t i−1 = (n) −1 q q i−1 t, i = 1, 2, . . . , n are independent.

(c) The process starts at time t = 0 with X n,q (0) = 0.

Remark 3.5. 2 The above q-random walk stochastic process, has been recently defined by Vamvakari [Vam17]. This q-random walk stochastic process, has been proved that is approximated, as n → ∞, by a continuous analogue one {Y q (t), t ≥ 0}, where the r.v. Y q (t) is the position after time t with probability density function

f (y, t) = q −7/8 σ(2π) 1/2 q −1 − 1 1/2 (log q −1 ) 1/2 (1 − q) 1/2 q 3/2 • (y − µ t ) σ t + q −1 −1/2 • exp 1 2 log q log 2 q −3/2 (1 − q) 1/2 • (y − µ t ) σ t + q −1 ,(12)y > µ t − σ t q 1/2 (1 − q) −1/2 ,

where the mean value µ and the variance σ 2 of the r.v. Y q (t) are given by

µ t = E(Y q (t)) = ct, σ 2 t = V (Y q (t)) = 1 − q q (ct) 2 + ct. (13)

Definition 3.6. The continuous stochastic process {Y q (t), t ≥ 0}, is called q-Brownian motion with parameters q, µ t and σ 2 t , if the following properties hold (A) The distribution of the increment Y q (t 2 ) − Y q (t 1 ), with t 2 − t 1 = (1 − q)t, t > 0, is the linear transformed standardized Stieltjes-Wigert distribution with p.d.f (12), where

µ t2−t1 = c(1 − q)t and σ 2 t2−t1 = 1−q q (c(1 − q)t) 2 + c(1 − q)t. (B) The increments Y q (t k ) − Y q (t k−1 ), where t k − t k−1 = q k−1 (1 − q)t, k = 1, 2, . . . , are independent.

(C) Y q (0) ≥ 0 and Y q (t) is continuous at t = 0. Using suitably the above properties of the q-Brownian motion, the pdf (12) of the r.v.Y q (t), and its mean value and variance (13), as well as the reflection principle, the following theorem is proved.

Theorem 3.7. Let W q (T ) = max 0≤t≤T Y q (t) the r.v. of the maxima in the q-Brownian motion and T b the first time passage of the process Y q (t) from the point b with b > µ t − σ t q 1/2 (1 − q) −1/2 . Then

P (W q (T ) ≥ b) = q −15/8 (1 − erf (B t )) (14)

and the p.d.f of the first time passage from b is given by

f T b (t) = − dB t d t 2q −15/8 √ π exp −B 2 t ,(15)

where

B t = 1 2logq −1 log q −3/2 (1 − q) 1/2 b − µ t σ t + q −1 + logq 2 . (16)

3.2 q-Random Walks on the Two-Dimensional Integer Lattice

In this section, we introduce a nearest neighbourq-random walk on the two-dimensional integer lattice with transition probabilities q-varying by the number of steps, 0 < q < 1. This random walk is defined as a Markov chain discrete time stochastic process.

Definition 3.8. The Markov chain in which at each transition is likely to take one step to the right, left, up or down in the plane with q-varying transition probabilities given respectively by

P (i,j),(i+1,j) = θ 1 q i−1 (1 + θ 1 q i−1 )(1 + θ 2 q j−1 ) , P (i,j)(i−1,j) = 1 (1 + θ 1 q i−1 )(1 + θ 2 q j−1 ) , P (i,j),(i,j+1) = θ 2 q j−1 (1 + θ 1 q i−1 )(1 + θ 2 q j−1 ) , P (i,j)(i,j−1) = θ 1 q i−1 θ 2 q j−1 (1 + θ 1 q i−1 )(1 + θ 2 q j−1 )

, i, j = 0, ±1, ±2, . . . ,

where 0 < θ 1 < ∞, 0 < θ 2 < ∞, 0 < q < 1, is called q-random walk on the two-dimensional integer lattice.

We now study if this Markov chain is also recurrent as the q-random walk in one-dimension. Because the qrandom walk in two-dimensions is irreducible, it follows that all states are recurrent if state 0= (0, 0) is recurrent. Now after 2n transitions the chain will be back if for some x, x = 0, 1, . . . , n, the 2n steps consist of x steps to the right, x to the left, n − x up, and n − x down. Each step will be independenlty in any of these directions with varying probabilities given respectively by (17).

Let X + be the number of "right steps", X − be the number of "left steps", Y + be the number of "up steps" and Y − be the number of '"down steps" after 2n steps. We need to find the probability function of the 4th-variate random variable (X + , X − , Y + , Y − ).

Let A i be the event of "right step" at the ith step, i = 1, 2, . . . , n, and consider a permutation (i 1 , i 2 , . . . , i x , i x+1 , . . . , i n ) of the n positive integers. Also, let B j be the event of "up step" at the jth step, j = 1, 2, . . . , n with i + j = n, and consider a permutation (j 1 , j 2 , . . . , j n−x , j n−x+1 , . . . , i n ) of the n positive integers. Then using the independence of each step, the q-varying transition probabilities (17), the relations (3),(5) and

n 2 = x 2 + n−x 2 + x(n − x)

, we derive the following lemma.

Lemma 3.9. Let the 4th-variate random variable (X + , X − , Y + , Y − ) , where X + be the number of "right steps", X − be the number of "left steps", Y + be the number of "up steps" and Y − be the number of '"down steps" after 2n steps in the two-dimensional q-random walk starting from the origin 0. Then, it holds that

P n 0,0 = P X + = x, X − = x, Y + = n − x, Y − = n − x = = θ 2n 2 q 2( n 2 ) 2n x,x,n−x q q −x(n−x) θ1 θ2 2x 2n i=1 (1 + θ 1 q i−1 + θ 2 q n−i−1 + θ 1 θ 2 q n−2 ) , x = 0, 1, 2, . . . , n.(18)

By the above lemma 3.9, the q-Cauchy formula (4) and the q-Stirling formula (6), the next theorem is concluded.

Theorem 3.10. Let the q-random walk on the 2D dimensional integer lattice after 2n steps, starting from the origin 0, with θ 1 /θ 2 = q n/2 , n = 0, 1, 2, . . .. Then for θ 2 constant or for θ 2 = q −αn , 0 < a < 1, n = 0, 1, 2, . . . , the 2D q-random walk is recurrent, while for θ 2 q n → ∞, as n → ∞, is transient.

Remark 3.11. 3 Possible realizations of the transience condition considered in the above theorem are among others the next two ones

θ 2 = q −cn , c > 1 or θ 2 = exp(O(n)).

Next, we introduce the relative bivariate q-random walk stochastic process. Analytically, let the time interval (0, t], t > 0, and partition it into parts which are geometrically decreasing with rate q, defined by δ i (n; t) = (n) −1 q q i−1 t, i = 1, 2, . . . , n, n ≥ 1. Also, let the process generated by taking one step, of length δ = 1, to the right, left, up or down in the plane at every time period (n) −1 q q i−1 t, i = 1, 2, . . . , n n ≥ 1, with q-varying transition probabilities

p i,1 = P (X i = δ, Y i = 0) = θ 1 q i−1 t/(n) q (1 + θ 1 q i−1 t/(n) q )(1 + θ 2 q n−i−1 t/(n) q ) , p i,2 = P (X i = −δ, Y i = 0) = 1 (1 + θ 1 q i−1 t/(n) q )(1 + θ 2 q n−i−1 t/(n) q ) , P i,3 = P (X i = 0, Y i = δ) = θ 2 q n−i−1 t/(n) q (1 + θ 1 q i−1 t/(n) q )(1 + θ 2 q n−i−1 t/(n) q ) , P i,4 = P (X i = 0, Y i = −δ) = θ 1 θ 2 q n−2 t 2 /(n) 2 q (1 + θ 1 q i−1 t/(n) q )(1 + θ 2 q n−i−1 t/(n) q ) ,(19)

where

0 < θ 1 < ∞, 0 < θ 2 < ∞, 0 < q < 1 with θ 1 /θ 2 = q n/2 . Then, at time n i=1 δ i (n; t) = t, the position of the process is the bivariate r.v. (X n,q (t), Y n,q (t)) with X n,q (t) = n i=1 X i and Y n,q (t) = n i=1 Y i .

Definition 3.12. The continuous time bivariate stochastic process {(X n,q (t), Y n,q (t)) , t > 0}, is called bivariate q-random walk stochastic process with parameters n, θ 1 , θ 2 and q, 0 < q < 1, if the following properties hold (a) In each of the consecutive mutually disjoint time intervals of length δ i (n; t) = (n) −1 q q i−1 t, i = 1, 2, . . . , n, n ≥ 1, at most one event (right or left or up or down step) occurs and P Xn,q 1 − q i 1 − q n t − Xn,q 1 − q i−1 1 − q n t = δ, Yn,q 1 − q i 1 − q n t − Yn,q

1 − q i−1 1 − q n t = 0 = θ1q i−1 t/(n)q (1 + θ1q i−1 t/(n)q)(1 + θ2q n−i−1 t/(n)q) , P Xn,q 1 − q i 1 − q n t − Xn,q 1 − q i−1 1 − q n t = −δ, Yn,q 1 − q i 1 − q n t − Yn,q 1 − q i−1 1 − q n t = 0 = 1 (1 + θ1q i−1 t/(n)q)(1 + θ2q n−i−1 t/(n)q) , P Xn,q 1 − q i 1 − q n t − Xn,q 1 − q i−1 1 − q n t = 0, Yn,q 1 − q i 1 − q n t − Yn,q 1 − q i−1 1 − q n t = δ = θ2q n−i−1 t/(n)q (1 + θ1q i−1 t/(n)q)(1 + θ2q n−i−1 t/(n)q) , P Xn,q 1 − q i 1 − q n t − Xn,q 1 − q i−1 1 − q n t = 0, Yn,q 1 − q i 1 − q n t − Yn,q 1 − q i−1 1 − q n t = −δ = θ1θ2q n−2 t 2 /(n) 2 q (1 + θ1q i−1 t/(n)q)(1 + θ2q n−i−1 t/(n)q) , δ = 1, i = 1, 2, . . . , n, 0 < θ1, θ2 < ∞, θ1/θ2 = q n/2 .

(b) The bivariate increments (X n,q (t i ) − X n,q (t i−1 ), Y n,q (t i ) − Y n,q (t i−1 )) , where t i − t i−1 = (n) −1 q q i−1 t, i = 1, 2, . . . , n, are independent.

(c) The process starts at time t = 0 with (X n,q (0), Y n,q (0)) = (0, 0).

3.3

q-Random Walks Processes and q-Brownian Simulations in R Using definition 3.4, the q-random walk process has been simulated in R. Figures 1-6 represent the results of these simulations for various values of the parameters q, n, θ and t. There is strong indication, implied by theorem 3.2, that for θ constant or for θ = q −αn , 0 < a < 1, even for small values of n, the 1st return to the origin occurs before or at time t. While, for θ = q −cn , c > 1 or θ = exp(O(n)), there is no return to the origin. Figure 1: Generation of 5, q-Random Walk Processes in R with with q = 0.7, n = 30, θ = q −15 , t = 1.

Figure 2: Generation of 5, q-Random Walks Processes with q = 0.7, n = 30, θ = 1, t = 10.

Figure 3: Generation of 5, q-Random Walks Processes with q = 0.9, n = 30, θ = 1, t = 10. Figure 5: q-Random Walk Process with q = 0.7, n = 30, θ = q −45 , t = 10.

Figure 6: q-Random Walks Process with q = 0.7, n = 30, θ = exp(30), t = 10. Also, q-Brownian motion simulation in R has been produced by definition 3.6. Figures 7-8 represent the results of these simulations for some values of the parameters q and t. : q-Brownian Motion Simulation in R with q = 0.9, t = 1.

Figure 8: q-Brownian Motion Simulation in R with q = 0.9, t = 10 .

Moerover, using definition 3.12 the two-dimensional q-random walk process has been simulated in R-package. Figures 9-14 represent the results of these simulations for various values of the parameters q, n, θ 1 , θ 2 and t. Analogously as in one-dimension, there is strong indication, implied by theorem 3.10, that for θ 2 constant or for θ 2 = q −αn , 0 < a < 1, with θ 1 /θ 2 = q n/2 , even for small values of n, the 1st return to the origin occurs before or at time t. While, for θ 2 = q −cn , c > 1 or θ 2 = exp(O(n)), there is no return to the origin. Note that R-codes are available under request. Figure 9: 2D q-Random Walk Process Simulation in R with q = 0.9, n = 20, θ 2 = q 10 , t = 10.

Figure 10: 2D q-Random Process Simulation in R with q = 0.9, n = 20, θ 2 = q 10 , t = 1.

Figure 11: 2D q-Random Walk Process Simulation in R with q = 0.5, n = 20, θ 2 = q 10 , t = 10. Figure 12: 2D q-Random Walk Process Simulation in R with q = 0.7, n = 20, θ 2 = q −10 , t = 10.

Figure 13: 2D q-Random Walk Process Simulation in R with q = 0.5, n = 20, θ 2 = q −30 , t = 10.

Figure 14: 2D q-Random Walk Process Simulation in R with q = 0.5, n = 20, θ 2 = e 10 , t = 10.

Further Study

q-Random walks in higher than two dimensions can also be defined. For instance, we can introduce a nearest neighbour random walk on the three-dimensional integer lattice with transition probabilities q-varying by the number of steps, 0 < q < 1. This random walk is defined as a Markov chain discrete time stochastic process as follows.

Definition 3.13. The Markov chain in which at each transition is likely to take one step to the six directions to the right, left, up, down, in, or out in the space, with q-varying transition probabilities given respectively by P (i,j,k),(i+1,j,k) = θ1q i−1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , P (i,j,k)(i−1,j,k) = 1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , P (i,j,k),(i,j+1,k) = θ2q j−1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , P (i,j,k)(i,j−1,k) = θ2q i−1 θ3q k−1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , P (i,j,k),(i,j,k+1) = θ3q k−1 + θ1q i−1 θ3q k−1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , P (i,j,k)(i,j,k−1) = θ1q i−1 θ2q j−1 θ3q k−1 (1 + θ1q i−1 )(1 + θ2q j−1 )(1 + θ3q k−1 ) , where i, j, k = 0, ±1, ±2, . . ., 0 < θ1, θ2, θ3 < 1, 0 < q < 1, is called q-random walk in three-dimensional integer lattice.

Starting from this three dimensional q-random walk, it is interestingly to study the transience and recurrency of q-random walks higher than two dimensions. Also, random walks in square or triangular lattices, where a vertex is added to one of the four or six directions respectively, according to edge (transition) probabilities varying by the number of previously visited vertices, can be applied to describe several real world network, neuroscience and statistical physics phenomena.