<< Chapter < Page Chapter >> Page >

The probability distribution on the yd's

Each YD, λ , such that λ λ 0 λ 1 corresponds to two SYD's: ( λ - λ 0 ) and ( λ - λ 1 ) . These two SYD's are given π ( λ - λ 0 ) q | λ | - | λ 0 | and π ( λ - λ 1 ) q | λ | - | λ 1 | . Thus we define

λ such that λ λ 0 λ 1 , π ( λ ) q | λ | - | λ 0 | + q | λ | - | λ 1 | .

Each YD, λ , such that λ λ 0 but λ λ 1 has only one corresponding SYD: ( λ - λ 0 ) . Thus, we define

λ such that λ λ 0 , λ λ 1 , π ( λ ) q | λ | - | λ 0 | .

Similarly, we define

λ such that λ λ 0 , λ λ 1 , π ( λ ) q | λ | - | λ 1 | .

Also,

λ such that λ λ 0 , λ λ 1 , π ( λ ) = 0 .

Tripling from the past

The first method we devised for sampling SYD's according to the probability distribution in formula [link] was simply to “triple” the young diagrams λ 0 , λ 1 , and λ full , and then remove the boxes in either λ 0 or λ 1 based on the conditional probabilities based on q | λ s | . Unfortunately, we found a simple counterexample that proved that this method does not work because the partial ordering of YD's is not preserved due to the monotonicity of our probability distribution on YD's as stated in "The Probability Distribution on the YD's" breaking in some places (see [link] for the counterexample).

Counterexample showing semi-monotonicity does not preserve partial ordering of YD's

The “black box" approach

The Black Box Approach

Since the method of tripling from the past did not work, we devised another method which we call the black box approach. With this approach, we change the probability distribution by giving positive probability proportional to X ( λ ) to young diagrams λ such that λ λ 0 , λ λ 1 , and λ λ 0 λ 1 . Then we sample according to this new distribution, and if the sampled YD λ temp satisfies all of the following:

λ temp λ 0 ,
λ temp λ 1 ,
λ temp λ 0 λ 1 ,

discard λ temp and sample another YD according to the new distribution until the sampled YD λ temp satisfies: λ temp at least one of λ 0 , λ 1 . When we sample a λ temp such that λ temp at least one of λ 0 , λ 1 , then we output λ temp and rename it λ . It is easily seen that the output, λ , has been sampled according to the probability distribution stated in "The Probability Distribution on the YD's" . See [link] for a schematic of the Black Box Approach.

Theorem: The following values of X give a monotonic distribution for sampling:

X ( λ ) = q | λ | q | λ 0 | + q | λ 1 | .

We will begin by numbering the possible categories of σ and τ as follows:

``1'' represents young diagrams λ λ 0 λ 1
``2'' represents young diagrams λ λ 0 , λ λ 1
``3'' represents young diagrams λ λ 0 , λ λ 1
``4'' represents young diagrams λ λ 0 λ 1

We will label σ i first, σ i second, τ i third, and τ i fourth. For example, 1234 represents the situation where σ i belongs to category 1, σ i belongs to category 2, τ i belongs to category 3, and τ i belongs to category 4.

The possible situations for σ i and σ i are the following: 11, 12, 13, 14, 22, 24, 33, 34, and 44. The values of π ( σ i ) π ( σ i ) for each situation are the following:

11 : 1 q

12 : ( 1 q ) ( 1 1 + q | λ 1 | - | λ 0 | )

13 : ( 1 q ) ( 1 1 + q | λ 0 | - | λ 1 | )

14 : ( 1 q ) ( q | λ 1 | - | λ 0 | + 2 + q | λ 0 | - | λ 1 | ) - 1

22 : 1 q

24 : ( 1 q ) ( 1 1 + q | λ 0 | - | λ 1 | )

33 : 1 q

34 : ( 1 q ) ( 1 1 + q | λ 1 | - | λ 0 | )

44 : 1 q

The possible situations for τ i and τ i are the same situations for σ i and σ i . Also, the values of π ( τ i ) π ( τ i ) are the same values for π ( σ i ) π ( σ i ) for each situation.

In order to prove monotonicity, we need to show that for all possible combinations of σ i , σ i , τ i , and τ i , the inequality from formula [link] holds. In all of the following cases, we will prove that either the inequality holds or the combinations of σ i , σ i , τ i , and τ i are impossible.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask