Austrian Journal of Statistics
June 2019, Volume 48, 11–16.
http://www.ajs.or.at/AJS

doi:10.17713/ajs.v48i5.858

A p-Laplacian Random Walk: Application to VideoGames
Nicolas Wicker

Canh Hao Nguyen

Hiroshi Mamitsuka

Dépt. de Mathématiques
University of Lille

Bioinformatics Center
Inst. for Chemical Research
Kyoto University

Bioinformatics Center
Inst. for Chemical Research
Kyoto University

Abstract
A graph random walk is presented. It is derived from the p-Laplacian similarly tothe derivation of the canonical random walk from the Laplacian. This variant enables
quicker exploration while still sticking to the connection constraints given by the graph.
A potential application is shown for video games.

Keywords: graph Laplacian, p-Laplacian, random walk, video games.

1. Random walks on a graph and Laplacian
Random walk on graphs are a classical subject in probability (Grimmet and Stirzaker 2004) ,statistics (von Luxburg, Radl, and Hein 2014) and algebra (Żuk and Pak 2002). The standard
random walk is defined as a Markov chain where the first order transition probability fromone vertex to another is given by 1/d where d is the degree of the first vertex.
PThe stationary
1
distribution of this Markov chain is given by π = m(d1 , . . . , dn ) where m = ni=1 di . In somecases, as video games it may be desirable to have a random walk starting at some vertex.
Some variants of it would be to explore more quickly the graph. Let’s say there is a monster
exploring rooms in a dungeon where rooms are connected to each other. At each step, amonster can only move to a neighbour room. So, to accelerate its visits, one way would
be to count more iterations but this would have the drawback of making the monster jump
between rooms. Consequently, here we propose an alternative way consisting in going backto the definition of the canonical random walk through its associated graph Laplacian andachieving that way our goal.
The idea is to modify slightly the random walk going back to its definition by a Laplacian.
The Laplacian can be considered in two equivalent ways, either as something proportional
to the infinitesimal generator or as an operator to be minimized when going from one time
step to another. Let us recall first the definition of the infinitesimal generator of the Markovchain X where Xxt is the state at time t of the Markov chain starting at x at time 0. The
infinitesimal generator in continuous time for a multivariate diffusion in Rp as the operator

12

A p-Laplacian random walk: application to video games

on a function f : Rp → R is then given by:
E[f (Xxt )] − f (x)t→0t

Af (x) = lim

In can be discretized in many ways, one of them is the following:
Af (i) =Xwijj|j∼i=f (j)− f (i)di1 Xwij [f (j) − f (i)]dij|j∼i=−L2 f (i)diR
The second point of view is related to the minimization of equation: |∇f (x)|p dw, for which
it is well known thatthe minimum is obtained by having ∆p f (x) = 0 for all x. On a graph,
P P
we can minimize i j|j∼i (f (xi ) − f (xj ))p on a graph by equalling to zero the correspondingp-Laplacian.

2. Random walk on a graph and p-LaplacianIn the continuous case, the p-Laplacian is defined as:∆p f =div(|∇f |p−2 .∇f )=|∇f |p−2 ∆f + (p − 2)∆∞ f2

where ∆ is the usual 2−Laplacian and ∆∞ = |∇f |−2 12 h∇f, ∇ ∇f i. Indeed,nX|∇f |p−3 ∂f ∂f∂2f|∇f | ∂xi ∂xj ∂xi ∂xj
i,j=1


2
p−2−2 1h∇f, ∇ ∇f i=|∇f |∆f + |∇f |2∆p f =|∇f |p−2 ∆f + (p − 2)=|∇f |p−2 {∆f + (p − 2)∆∞ f }Then, we can define the discretized version on a graph g as ∆gp f = ∆g f + (p − 2)∆g∞ f or putit in a normalized way:
∆g fp−2 g+∆ f
p−1 p−1 ∞So, now if we want to minimize ∆p f over a graph we just need to take discrete versions of ∆and ∆∞ . The first one is well known and given by:
X wik∆gp f (i) =(f (k) − f (i))
dik|k∼it is the probability of arriving at j in t
The usual random walk on graph is such that if Rij
t+1
time steps starting from i, for all i 6= j Rijverifies:

X wik
k|k∼i

dit+1t(Rkj− Rij)=0

so thatt+1
Rij=X wikk|k∼i

ditRkjAustrian Journal of Statistics

13About, the infinity Laplacian, one of its discrete expressions is:
1
∆g∞ f (u) =max f (v) + min f (v) − 2f (u)v∼u2 v∼u
as given in Elmoataz, Desquesnes, and Lézoray (2012), this can be obtained by considering
the infinity Laplacian as the second derivative along the steepest direction.
So now, similarly we can aim at minimizing:
X wik|P t − Pijt+1 |pdi kjk|∼ikeeping a P t+1 a probability transition matrix.
Without the need of having a probability transition matrix, we could use directly the discretep-Laplacian and have:
1 X wik t
1 t
1 t
p−2
t+1
t+1
max Q + min Q − Qij=0(Qkj − Qij ) +p−1
dip − 1 k|k∼i 2 kj k|k∼i 2 kj
k|k∼i

leading to:
Qt+1
ij =

p−2
1 t
1 t
1 X wik t
Q +max Q + min Q
p−1
di kj p − 1 k|k∼i 2 kj k|k∼i 2 kj

(1)

k|k∼i

The problem with this expression is that we could have, due to the second term,
different from 1.

Pt+1
j Qij

Therefore to define a probability transition matrix Pijt+1 for time t we can modify slightly theprevious equation by writing:
1 X wik t
p−2
Pkj + αitmax P tp−1
dip − 1 k|k∼i kj

Pijt+1 =(2)

k|k∼i

Pnt+1
= 1.
j=1 Pij

where αit are such that
αit is given by :nX
1− Xn
1 X wik t
p−2t
P/max Pp−1
di kj
p − 1 k|k∼i kj
j=1
j=1
k|k∼i
X
nt=1/max Pkj

αit =j=1k|k∼i

Lemma 1. ∀i, t we have 0 ≤ αit ≤ 1.
Proof. Positivity of αit is obvious by construction. Concerning, the other inequality we cansum Pijt+1 to prove it, indeed:nX

Pijt+1 =j=1

⇒1≥

nX
j=1n

X p−2
1 X wik t
Pkj +αitmax P t using equation 2
p−1
dip − 1 k|k∼i kj

1p−2+ αitmax
p−1
p − 1 k|k∼i⇒ 1 ≥ αit

j=1k|k∼inX
j=1t
Pkj
exchanging the max and sum terms

14

A p-Laplacian random walk: application to video games

Lemma 2. P t → 1v | for some vector v.
Proof. ∀j, let us consider i∗ = arg maxi Pijt . Then,Pijt+1 =p−2
1 X wik t
Pkj + αitmax P tp−1
dip − 1 k|k∼i kjk|k∼i≤1 X wik t
p−2 t
Pi∗ j + αit
P∗p−1
dip−1 i jk|k∼i≤Pit∗ j as αit ≤ 1
This means that for all j the maximum values of Pijt are not increasing. Besides, at one stepfor a given j either Pit1 j = Pit2 j for all i1 , i2 or there exists i∗ such that for all its neighbours i,Pit∗ j ≥ Pijt and there exists i− among its neighbours such that Pit∗ j > Pit− j so that we obtainat next step:
Pit+1∗j =X wi∗ k
p−2
1tt
Pkj+ αit∗max Pkj
∗
∗
p−1
dp−1
k|k∼ii∗k|k∼i<X wi∗ k1
p−2 tPit∗ j + αit∗P∗∗
p−1
dp−1 i ji∗
k|k∼i<Pit∗ j as αit∗ ≤ 1This shows that the maximum values of Pijt are all strictly decreasing for all j. Consequently,
as they are bounded below by 0 we obtain then convergence.
In general with our setting it is difficult to guess what the stationary distribution is, contrary
to what happens with the canonical random walk. However, in next lemma we show that fora d-regular graph the stationary distribution is known.
Lemma 3. For a d-regular graph, the stationary distribution is given by n1 1.
Proof. Indeed, if ∀i, j Pijt = n1 , we obtain:
Pijt+1 =1 X 1 t
p−2
Pkj + αitmax P tp−1
dp − 1 k|k∼i kj
k|k∼i

1 X 11p−2
1=+ αitmax
p−1
dnp − 1 k|k∼i nk|k∼i=1 1p−21+ αit
p−1n
p−1n

Obviously, in that case αit = 1 so that: Pijt+1 = n1 concluding thus the proof.
Thus, our proposed random walk shares the same stationary distribution with the canonicalrandom walk if the graph is regular.

3. Application to video games
10 after 10 steps for state
If we consider the graph on figure 1, the transition probabilities P1i
1 are represented in tables 1 and 2 for p = 2 and p = 3 respectively. We observe that themixing occurs more quickly for p = 3. That is, for the same number of steps, vertices 11 to 20
are more easily reached with the modified random walk than with the canonical one (p = 2).
Afterwards, we have compared the convergence speed for the random walks on two differents
random graphs. The first type is a set of random barbell graphs where in both cliques of size

Austrian Journal of Statistics

15100, edges are randomly deleted with probability 0.5. The second type is a set of random
3-regular graphs of size 200 vertices. Convergence is assessed by computing the mean squareerror among columns of P 10 . Results in table 3 show that in both cases convergence occurs
more quickly for p = 3.

Figure 1: Small graph example drawn using R (R Development Core Team 2008) packageigraph (Csardi and Nepusz 2006)

Table 1: Transition probabilities of state 0 after 10 steps for p = 2.
StateProba.
State
Proba.

10.04
110.0320.10
120.0230.03
130.02

4
0.10
14
0.02

50.15
15
0.01

60.08
16
0.02

70.05
17
0.02

80.07
18
0.03

90.11
19
0.02

100.0720
0.02

Table 2: Transition probabilities of state 0 after 10 steps for p = 3.
StateProba.
StateProba.

10.04
110.0420.06
120.0430.03
130.0540.06
140.0450.09
150.0460.06
160.0470.05
170.0480.06
180.0590.08
190.05100.0520
0.04

4. Conclusion
We have defined a new random walk, derived from the p-Laplacian similary to what is done
for the canonical random walk derived from the 2-Laplacian. It is proven to have a stationary
distribution which is the same as for the canonical random walk in the case of regular graphs.
Experiments demonstrates quicker convergence. Natural perspectives would be to study theconvergence speed and also understand what happens between two time steps as what ispresented is not a Markov chain.

16A p-Laplacian random walk: application to video games

Table 3: Experimental comparison of convergence speeds between 2-Laplacian and 3Laplacian random walks after 10 steps.

Laplacian
3-Laplacian

Random barbell graphs
Mean
Sd
2.5 ∗ 10−5 4.4 ∗ 10−8
1.5 ∗ 10−6 1.1 ∗ 10−7

3-Regular graph
Mean
Sd
3.1 ∗ 10−7 8.6 ∗ 10−81.1 ∗ 10−7 2.6 ∗ 10−8

Acknowledgements
Part of this work was done between April and July 2017, when N. Wicker was invited professor
at the Kyoto University Bioinformatics Center (Institute for Chemical Research).

References
Csardi G, Nepusz T (2006). “The Igraph Software Package for Complex Network Research.”
InterJournal, Complex Systems, p. 1695. URL http://igraph.org.
Elmoataz A, Desquesnes X, Lézoray O (2012). “Non-Local Morphological PDEs and pLaplacian Equation on Graphs with Applications in Image Processing and Machine Learning.” IEEE Journal of Selected Topics in Signal Processing, IEEE, 6(7), 764–779.
Grimmet GR, Stirzaker DR (2004). Probability and Random Processes. Oxford Press.
R Development Core Team (2008). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0, URL
http://www.R-project.org.
Żuk A, Pak I (2002). “On Kazhdan Constants and Mixing of Random Walks.” International
Mathematical Research Notes, 36, 1891–1905.
von Luxburg U, Radl A, Hein M (2014). “Hitting and Commute Times in Large Random
Neighborhood Graphs.” Journal of Machine Learning Research, 15, 1751–1798.

Affiliation:Nicolas Wicker
Département de mathématiques
Université de Lille, Cité Scientifique
59655 Villeneuve d’Ascq, France
E-mail: nicolas.wicker@univ-lille.fr
URL: http://labomath.univ-lille1.fr/~wicker/

Austrian Journal of Statistics
published by the Austrian Society of Statistics
Volume 48
June 2019http://www.ajs.or.at/
http://www.osg.or.at/
Submitted: 2018-08-18
Accepted: 2019-01-25