On partitions of components for closed random braids

(1)

Random braids K. Ichihara

Introduction Random braid / link Random walk onBn Components of random link

Expected value Most Expected Number Partition of integer for random braid

Partition of integer Partition for random braid

Problems Hyperbolicity Application to Amida-kuji

Probability Space Random walk Randomness of Amida-kuji Proof of Theorem Perron–Frobenius theorem

On partitions of components for closed random braids

Kazuhiro Ichihara

Nihon University

College of Humanities and Sciences

Joint work with

Makoto Mori & Ken-ichi Yoshida (Nihon Univ.) Intelligence of Low-dimensional Topology 2015

May 20, 2015

(2)

Table of contents Introduction

Random braid / link Random walk on

B_n

Components of random link

Expected value

Most Expected Number

Partition of integer for random braid Partition of integer

Partition for random braid Problems

Hyperbolicity

Application to Amida-kuji Probability Space Random walk

Randomness of Amida-kuji

Proof of Theorem

(3)

Random braid / link

Recently, in Knot theory, and larger, in Low-dim.Topology, there have been several studies on random links & manifolds.

For example, in 2013, Jiming Ma introduced

random links

based on random walk on braid group

B_n

.

Random braid / link (rough definition)

We said a braid is a random braid if it is represented by the random variable ω

_n,k

corresponding to the k-step random walk on

B_n

with suﬃciently large k.

The closure of a random braid is called a

random link.

Jiming Ma, Components of random links,

J. Knot Theory Ramifications 22 (2013), 1350043, 11 pp.

(4)

Random braid / link

Recently, in Knot theory, and larger, in Low-dim.Topology, there have been several studies on random links & manifolds.

For example, in 2013, Jiming Ma introduced

random links

based on random walk on braid group

B_n

.

Random braid / link (rough definition)

We said a braid is a random braid if it is represented by the random variable ω

_n,k

corresponding to the k-step random walk on

B_n

with suﬃciently large k.

The closure of a random braid is called a

random link.

Jiming Ma, Components of random links,

J. Knot Theory Ramifications 22 (2013), 1350043, 11 pp.

(5)

Random walk on B

n

A Markov chain on

B_n

with transition probabilities

P

(x, y) = µ(x

⁻¹

y), where µ is a probability measure on

Bn

. We always assume that the starting point at time zero is the identity element in the group.

Assumption on µ:

Let

S_n

be the symmetric group on n letters.

Consider the natural projection π :

Bn→Sn

(n

≥

3). We assume that our probability measure µ on

Bn

generates a uniformly distributed random walk on

S_n

when k

→ ∞

. That is, we are assuming that for any s

∈S_n

P

(ω

_k

= s)

→

1 n! as k

→ ∞

for the probability induced from the random walk ω

k

.

(6)

Random walk on B

n

A Markov chain on

B_n

with transition probabilities

P

(x, y) = µ(x

⁻¹

y), where µ is a probability measure on

Bn

. We always assume that the starting point at time zero is the identity element in the group.

Assumption on µ:

Let

S_n

be the symmetric group on n letters.

Consider the natural projection π :

Bn→Sn

(n

≥

3).

We assume that our probability measure µ on

Bn

generates a uniformly distributed random walk on

S_n

when k

→ ∞

. That is, we are assuming that for any s

∈S_n

P

(ω

_k

= s)

→

1 n! as k

→ ∞

(7)

Random walk on B

n

Jiming Ma (’13)

Let µ be a probability measure on

B_n

, which induces a random walk π(ω

n,k

) on

Sn

.

Suppose that the probability

P

(π(ω

n,1

) = id) is larger than 0, and the support of µ generates

B_n

.

Then µ generates a uniformly distributed random walk on

Sn

when k

→ ∞

.

For example, the probability measure on

Bn

defined by µ

_c

(id.) = µ

_c

(σ

_i

) = µ

_c

(σ

_i⁻¹

) = 1

2n

−

1 for each canonical generator σ

_i∈B_n

(1

≤

i

≤

n

−

1)

satisfies the assumption.

(8)

Table of contents

Introduction

Random braid / link Random walk on

B_n Components of random link

Expected value

Most Expected Number

Partition of integer for random braid Partition of integer

Partition for random braid Problems

Hyperbolicity

Application to Amida-kuji Probability Space Random walk

Randomness of Amida-kuji

Proof of Theorem

(9)

Expected value of the number of components

Theorem [Ma, 2013]

Consider a random link obtained from a k-step random walk on

Bn

. Then, as k

→ ∞

, the expected value of the number of components converges to

1 + 1

2 +

· · ·

+ 1 n

Remark

n

lim

→∞

(

1 + 1

2 +

· · ·

+ 1 n

)

−

log n = γ

where γ = 0.5772

· · ·

is the Euler-Mascheroni’s constant.

Question

What is the

most expected

number of components for a

random link?

(10)

Expected value of the number of components

Theorem [Ma, 2013]

Consider a random link obtained from a k-step random walk on

Bn

. Then, as k

→ ∞

, the expected value of the number of components converges to

1 + 1

2 +

· · ·

+ 1 n

Remark

n

lim

→∞

(

1 + 1

2 +

· · ·

+ 1 n

)

−

log n = γ

where γ = 0.5772

· · ·

is the Euler-Mascheroni’s constant.

Question

What is the

most expected

number of components for a

(11)

Most Expected number of components

Consider a random walk ω

_n,k

on

Bn

, and the probability p

^m_n,k

:=

P

( ω

dn,k

has exactly m components).

The most expected number of components is m

if, for any suﬃciently large k, p

^m_n,k

is maximal for 1

≤

m

≤

n. Proposition

Consider a random link obtained from a k-step random walk on

Bn

. Then the most expected number of components is equal to

K_n

:=

[

log(n+ 1) +γ−1 + ζ(2)−ζ(3)

log(n+ 1) +γ−1.5+ h

(log(n+ 1) +γ−1.5)² ]

with

−

1.1 < h < 1.5. In particular, if n > 188,

[

log n

−

1 2

]

< K

n

< [log n]

(12)

Most Expected number of components

Consider a random walk ω

_n,k

on

Bn

, and the probability p

^m_n,k

:=

P

( ω

dn,k

has exactly m components).

The most expected number of components is m

if, for any suﬃciently large k, p

^m_n,k

is maximal for 1

≤

m

≤

n.

Proposition

Consider a random link obtained from a k-step random walk on

Bn

. Then the most expected number of components is equal to

K_n

:=

[

log(n+ 1) +γ−1 + ζ(2)−ζ(3)

log(n+ 1) +γ−1.5+ h

(log(n+ 1) +γ−1.5)² ]

with

−

1.1 < h < 1.5. In particular, if n > 188,

[

log n

−

1 2

]

< K

n

< [log n]

(13)

Most Expected number of components

Consider a random walk ω

_n,k

on

Bn

, and the probability p

^m_n,k

:=

P

( ω

dn,k

has exactly m components).

The most expected number of components is m

if, for any suﬃciently large k, p

^m_n,k

is maximal for 1

≤

m

≤

n.

Proposition

Consider a random link obtained from a k-step random walk on

Bn

. Then the most expected number of components is equal to

K_n

:=

[

log(n+ 1) +γ−1 + ζ(2)−ζ(3)

log(n+ 1) +γ−1.5+ h

(log(n+ 1) +γ−1.5)² ]

with

−

1.1 < h < 1.5. In particular, if n > 188,

[

log n

−

1 2

]

< K

n

< [log n]

(14)

Proof of Proposition

Key

Given the closure σ

b

of σ

∈Bn

, for π :

Bn→Sn

(n

≥

3), a component of

b

σ

←→

a cycle in π(σ)

∈Sn

Example

σ = σ

₁

σ

₂

σ

₃⁻¹

σ

₂ ∈B₄

⇒

π(σ) = (1 2)(2 3)(3 4)(2 3) = (1 4 2)(3)

Thus the number of components of the link

b

σ is 2.

(15)

Proof of Proposition

Given the closure σ

b

of σ

∈Bn

, for π :

Bn→Sn

(n

≥

3), the number of components of σ

b

= the number of cycles of the decomposition of π(σ)

Since we are assuming that the induced random walk on

Sn

tends to be uniformly distributed, it suﬃces to consider;

let

[n

k ]

be the number of permutations in

S_n

each of which has just k cycles in its cycle decomposition,

then

determine

k for which

[

n

k

]

is maximal for 1

≤

k

≤

n.

(16)

Proof of Proposition

Given the closure σ

b

of σ

∈Bn

, for π :

Bn→Sn

(n

≥

3), the number of components of σ

b

= the number of cycles of the decomposition of π(σ)

Since we are assuming that the induced random walk on

Sn

tends to be uniformly distributed, it suﬃces to consider;

let

[n

k ]

be the number of permutations in

S_n

each of which has just k cycles in its cycle decomposition,

then

determine

k for which

[

n

k

]

is maximal for 1

≤

k

≤

n.

(17)

Stirling Numbers of the First Kind

This number

[

n

k

]

is precisely equal to The Stirling number of the first kind !!

Hammersley, ’51

The maximizing index

Kn

of the Stirling number of the first kind is determined by

[

log(n+ 1) +γ−1 + ζ(2)−ζ(3)

log(n+ 1) +γ−1.5+ h

(log(n+ 1) +γ−1.5)² ]

with

−

1.1 < h < 1.5. Erd¨ os,’53

If n > 188,

[

log n

−

1 2

]

< K

n

< [log n]

(18)

Stirling Numbers of the First Kind

This number

[

n

k

]

is precisely equal to The Stirling number of the first kind !!

Hammersley, ’51

The maximizing index

Kn

of the Stirling number of the first kind is determined by

[

log(n+ 1) +γ−1 + ζ(2)−ζ(3)

log(n+ 1) +γ−1.5+ h

(log(n+ 1) +γ−1.5)² ]

with

−

1.1 < h < 1.5.

Erd¨ os,’53

If n > 188,

[

log n

−

1 2

]

< K

n

< [log n]

(19)

Table of contents

Introduction

Random braid / link Random walk on

B_n

Components of random link

Expected value

Most Expected Number

Partition of integer for random braid

Partition of integer

Partition for random braid Problems

Hyperbolicity

Application to Amida-kuji Probability Space Random walk

Randomness of Amida-kuji

(20)

Partition of integer from braid

As we saw, for example, given σ = σ

1

σ

2

σ

₃⁻¹

σ

2 ∈B4

⇒

π(σ) = (1 2)(2 3)(3 4)(2 3) = (1 4 2)(3)

This implies a partition (3,1) of 4: that is, 4 = 3 + 1 .

From σ

∈Bn

, we have a partition (p

1

,

· · ·

, p

k

) of n. (That is, p

1

+

· · ·

+ p

_k

= n)

Question (refinement)

What is the most expected partition of n for a random n-braid?

Remark

The number of the partition is equal to the number of

components for the closed braid.

(21)

Partition of integer from braid

As we saw, for example, given σ = σ

1

σ

2

σ

₃⁻¹

σ

2 ∈B4

⇒

π(σ) = (1 2)(2 3)(3 4)(2 3) = (1 4 2)(3)

This implies a partition (3,1) of 4: that is, 4 = 3 + 1 .

From σ

∈Bn

, we have a partition (p

1

,

· · ·

, p

k

) of n.

(That is, p

₁

+

· · ·

+ p

_k

= n)

Question (refinement)

What is the most expected partition of n for a random n-braid?

Remark

The number of the partition is equal to the number of

components for the closed braid.

(22)

Partition of integer from braid

As we saw, for example, given σ = σ

1

σ

2

σ

₃⁻¹

σ

2 ∈B4

⇒

π(σ) = (1 2)(2 3)(3 4)(2 3) = (1 4 2)(3)

This implies a partition (3,1) of 4: that is, 4 = 3 + 1 .

From σ

∈Bn

, we have a partition (p

1

,

· · ·

, p

k

) of n.

(That is, p

₁

+

· · ·

+ p

_k

= n)

Question (refinement)

What is the most expected partition of n for a random n-braid?

Remark

The number of the partition is equal to the number of

(23)

Partition of integer for random braid

Theorem

Consider a random braid obtained from a k-step random walk on

Bn

. Then the most expected partition of n for a random n-braid is

((n−1),1).

Our proof is purely algebraic (with elementary group theory). The key is computing the cardinality of the conjugacy class in the symmetry group.

We omit the details, and only show the key lemma. Lemma

In

S_n

(n

≥

3), the conjugacy class of the maximal

cardinality is the one containing the cycle (1

· · ·

n

−

1).

(24)

Partition of integer for random braid

Theorem

Consider a random braid obtained from a k-step random walk on

Bn

. Then the most expected partition of n for a random n-braid is

((n−1),1).

Our proof is purely algebraic (with elementary group theory).

The key is computing the cardinality of the conjugacy class in the symmetry group.

We omit the details, and only show the key lemma.

Lemma

In

S_n

(n

≥

3), the conjugacy class of the maximal

cardinality is the one containing the cycle (1

· · ·

n

−

1).

(25)

Table of contents

Introduction

Random braid / link Random walk on

B_n

Components of random link

Expected value

Most Expected Number

Partition of integer for random braid Partition of integer

Partition for random braid

Problems

Hyperbolicity

Application to Amida-kuji Probability Space Random walk

Randomness of Amida-kuji

(26)

Bridge model

Also Jiming Ma introduced another model of random link.

Again, consider a “random” braid, and take the plat closure.

In other words, in this model, a random link is a link with

random bridge decomposition.

It can be regarded as a link version of random Heegaard splitting of 3-manifolds.

We should consider random walk (not in

B_n

)

in the mapping class group on the 2n-punctured sphere.

(27)

Bridge model

Also Jiming Ma introduced another model of random link.

Again, consider a “random” braid, and take the plat closure.

In other words, in this model, a random link is a link with

It can be regarded as a link version of random Heegaard splitting of 3-manifolds.

We should consider random walk (not in

B_n

)

in the mapping class group on the 2n-punctured sphere.

(28)

Bridge model

Also Jiming Ma introduced another model of random link.

Again, consider a “random” braid, and take the plat closure.

In other words, in this model, a random link is a link with

It can be regarded as a link version of random Heegaard splitting of 3-manifolds.

We should consider random walk (not in

B_n

)

in the mapping class group on the 2n-punctured sphere.

(29)

Bridge model

Also Jiming Ma introduced another model of random link.

Again, consider a “random” braid, and take the plat closure.

In other words, in this model, a random link is a link with

It can be regarded as a link version of random Heegaard splitting of 3-manifolds.

We should consider random walk (not in

B_n

)

in the mapping class group on the 2n-punctured sphere.

(30)

Hyperbolicity

Problem

Does the probability of hyperbolic random links go to 1?

This was already answered by Ma for the random braid model. How about for the bridge model?

I and Jiming Ma are considering this as an ongoing joint work (based on the work of Joseph Maher).

Problem

Does the expected value of the (simplicial or hyperbolic) volume for random link diverge?

If this is true, what is the growth late?

For any fixed V , does the probability of the ones with the

volume at most V go to 0?

(31)

Table of contents

Introduction

Random braid / link Random walk on

B_n

Components of random link

Expected value

Most Expected Number

Partition of integer for random braid Partition of integer

Partition for random braid Problems

Hyperbolicity

Application to Amida-kuji

Probability Space Random walk

Randomness of Amida-kuji

(32)

あみだくじ

Amida-kuji (“Amida lottery”) is a Japanese traditional

method of “lottery”.

(33)

Probability Space of Amida-kuji

Number the vertical lines (

縦棒

) as 1,

· · ·

, n, (called Pole).

Set the position of “leg” (

横棒

) as 1, 2, . . ., (called Step).

Probability Space of Amida-kuji Ω :=

{0,

1, . . . , n

−

1}

^Z

,

µ := (

¹_n

, . . . ,

_n¹

)

^Z

, Bernoulli measure on Ω

We define (Ω, µ) as the Probability Space of Amida-kuji. That is, setting ω = ω

1

ω

2· · · ∈

Ω, for each n,

put a leg between the poles of ω

n

and ω

n+1

at Step n.

Remark that no leg is put at the step n if ω

_n

= 0.

(34)

Probability Space of Amida-kuji

Number the vertical lines (

縦棒

) as 1,

· · ·

, n, (called Pole).

Set the position of “leg” (

横棒

) as 1, 2, . . ., (called Step).

Probability Space of Amida-kuji Ω :=

{0,

1, . . . , n

−

1}

^Z

,

µ := (

¹_n

, . . . ,

_n¹

)

^Z

, Bernoulli measure on Ω

We define (Ω, µ) as the Probability Space of Amida-kuji.

That is, setting ω = ω

1

ω

2· · · ∈

Ω, for each n,

put a leg between the poles of ω

n

and ω

n+1

at Step n.

Remark that no leg is put at the step n if ω

_n

= 0.

(35)

Probability Space of Amida-kuji

Let us include the data of the initial value as follows.

Probability Space of Amida-kuji with initial value ι Let

Ωˆ

:=

{1, . . . , n} ×

Ω, and ι the initial probability distribution at the top of the poles 1, . . . , n.

Set a measure on Ω ˆ as µ

_ι

:= ι

×

µ.

Then we define ( ˆ Ω, µ

ι

) as the Probability Space of

Amida-kuji with initial value ι.

(36)

Random walk

Random walk X

_n^a

(ω) on (Ω, µ)

Set X

₀^a

(ω) = a (ω

∈

Ω). When X

_n^a₋₁

(ω) = i, we define

X

_n^a

(ω) :=







i + 1 ω

_n

= i i

−

1 ω

n

= i

−

1 i otherwise

That is, when one lies on the pole i at Step (n

−

1), if there is a leg at Step n between the poles i & (i + 1), then move to the pole (i + 1),

and if, there is a leg between (i

−

1) & i,

then move to the pole (i

−

1).

(37)

Random walk on Ω ˆ

Setting the initial state ι for X

_n^a

(ω), we can get a Markov chain on Ω ˆ as

X

n

(ˆ ω) := X

_n^ω⁰

(ω) for ω ˆ = (ω

0

, ω)

∈

Ω. ˆ

Based on this, for suﬃciently large k, we define the

random Amida-kuji

as the one corresponds to such a random walk of k steps.

(38)

Random walk on Ω ˆ

Setting the initial state ι for X

_n^a

(ω), we can get a Markov chain on Ω ˆ as

X

n

(ˆ ω) := X

_n^ω⁰

(ω) for ω ˆ = (ω

0

, ω)

∈

Ω. ˆ

Based on this, for suﬃciently large k, we define the

random Amida-kuji

as the one corresponds to such a random walk of k steps.

(39)

Randomness of Amida-kuji

Our

random Amida-kuji

gives actually a “random” lottery, guaranteed by the next theorem.

Theorem (Randomness of Amida-kuji) By using the random Amida-kuji,

▶

when the actors decide the order of them,

the probabilities of each ordering are almost equal.

▶

when the actors draw a prize,

their probabilities to get the prize are almost equal.

In the following, we give a sketch of proof.

(40)

Transition Probability

For X

_n^a

(ω), we see that

p

ij

:=

P(ω ∈Ω : X_n^a(ω) =j|X_n^a₋₁(ω) =i)

=











1

n

j = i + 1, i

̸=

n

1

n

j = i

−

1, i

̸

= 1

n−1

n

j = i = n or j = i = 1

n−2

n

j = i and j

̸= 1, n

0 otherwise

is not depend upon n (Markov property).

(41)

Stochastic matrix

Thus we have the following stochastic matrix P = (p

ij

).

P =







n−1 n

1

n

0 0

· · ·

0

1 n

n−2 n

1

n

0

· · ·

0

¹_n ⁿ⁻_n² _n¹ · · ·

0 .. . .. . . .. ... ... 0 0 0

· · · _n¹ ⁿ⁻_n² _n¹

0 0

· · ·

0

¹_n ⁿ⁻_n¹







Note that this P is a symmetric matrix.

For X

_n

( ω), we set

b

p

^k_i,j

:= P (X

_k

(ˆ ω) = j

|

X

₀

(ˆ ω) = i) , and then, we get the matrix P

_k

:= (p

^k_i,j

).

In this setting, we can see that:

Setting P = P

₁

, P

_k

= P

^k

(k

≥

1) holds.

(42)

Stochastic matrix

Thus we have the following stochastic matrix P = (p

ij

).

P =







n−1 n

1

n

0 0

· · ·

0

1 n

n−2 n

1

n

0

· · ·

0

¹_n ⁿ⁻_n² _n¹ · · ·

0 .. . .. . . .. ... ... 0 0 0

· · · _n¹ ⁿ⁻_n² _n¹

0 0

· · ·

0

¹_n ⁿ⁻_n¹







Note that this P is a symmetric matrix.

For X

_n

( ω), we set

b

p

^k_i,j

:= P (X

_k

(ˆ ω) = j

|

X

₀

(ˆ ω) = i) , and then, we get the matrix P

_k

:= (p

^k_i,j

).

In this setting, we can see that:

(43)

Perron–Frobenius Theorem

When k

≥

n, p

^k_i,j ̸

= 0 (

∀

(i, j))

⇒

P is irreducible.

p

_ii

> 0 (

∀

i)

⇒