Counting minimal puzzles: subsets, supersets, etc.

Everything about Sudoku that doesn't fit in one of the other sections

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 7:49 am

blue wrote:
denis_berthier wrote:- a random variable is defined on some measurable space (here the discrete P(M)) with values in some other space (here R); A is a real random variable on P(M);

Are you suggesting that a random variable is a probablity distribution, and nothing more ?

No sorry, I mixed up all: here, A is a random variable with values in P(M).
In a sense, yes, a rv can be considered as a probability distribution on its space of values. More on this at the end of this post.*

blue wrote:
denis_berthier wrote:
blue wrote:The notation Pr(A=A) is unfamiliar to me.
(...)

(...)
Pr(A=A) is exactly what it reads: the probability that A = A.

The problem I would have with it, is that A is a subset of M, and (bold) A is not -- "how could the two be equal ?"


A random variable X is a function: o in O -> X(o), from some probability space O (representing chance) to some space of values (here P(M)). (Read omega for o and O)
Although it is, mathematically speaking, a function, it is called a random variable and the o variable is generally not written: we write X instead of X(o) - the "chance" variable is implicit.
{A = A} is (by definition) the set of elements o in O such that A(o) = A
and Pr(A = A), a shorthand for Pr({A = A}) is (by definition) the probability of this subset of O.

* When you have a random variable X defined on O, it can be used to transfer the probability on O to a probability on its arrival space, here P(M). So, that's what I meant by saying that a rv is almost the same thing as a probability distribution.


[Edit: in Red Ed's case, it'd be much simpler to start from a probability distribution on P(M)]
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Thu Jun 13, 2013 8:11 am

denis_berthier wrote:[Edit: in Red Ed's case, it'd be much simpler to start from a probability distribution on P(M)]

That's the pdf of A. The form of the distribution doesn't matter for the analysis, except that every m with non-zero value must have a non-zero chance of being picked. I've added a parenthetical remark to that effect.
Last edited by Red Ed on Thu Jun 13, 2013 8:22 am, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 8:22 am

Red Ed wrote:
denis_berthier wrote:[Edit: in Red Ed's case, it'd be much simpler to start from a probability distribution on P(M)]

That's the pdf of A.

Probability distribution is the general concept, the associated pdf is one way of presenting it. Of course, this is equivalent.

Red Ed wrote:The form of the distribution doesn't matter for the analysis, except that every m with non-zero value must have a non-zero chance of being picked.

So, you should write this at the start: "suppose there is on P(M) a probability distribution such that ..."
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Thu Jun 13, 2013 8:36 am

denis_berthier wrote:So, you should write this at the start: "suppose there is on P(M) a probability distribution such that ..."
I think this is a clumsy form of words, but in any case had just a moment before made the edit, "(non-zero)", near the start to rule out pathological cases.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 9:11 am

Red Ed wrote:
denis_berthier wrote:So, you should write this at the start: "suppose there is on P(M) a probability distribution such that ..."
I think this is a clumsy form of words, but in any case had just a moment before made the edit, "(non-zero)", near the start to rule out pathological cases.

If standard probability language is clumsy...

BTW, in this "clumsy" formulation, random variable A is totally useless. V is a random variable on P(M), that's all. You can directly use subsets A of M instead of rv A.
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby blue » Thu Jun 13, 2013 11:47 am

Hi Denis,

I've now read the Wikipedia page about "random variables".
It's probably time for you to look at Ed's examples.

There is an underlying sample space (the upper case omega) that is (solution grid, cell set) pairs with cell sets of a fixed size, from which elements are chosen with uniform probablity. Then there is a function from the sample space to sets of minimal puzzles, which would be the random variable, A.
The probabilities associated with the (solution grid, cell set) pairs are "simple" -- the same probablity is assigned to each pair.
The probablities for the possible A(solution grid, cell set) values (or any member of P(M)), would be easy enough to work out, but the distribution wouldn't be uniform.
Conslusion: In this case at least, using the probablity distribution on P(M) as a starting point, would be extremely awkward.

denis_berthier wrote:BTW, in this "clumsy" formulation, random variable A is totally useless. V is a random variable on P(M), that's all. You can directly use subsets A of M instead of rv A.

You really need to look at the total picture. The objet d'art here, is the way that the various pieces [ Omega (unmentioned), A, and V(A) defined in terms of φ and the Pr(m)'s ] fit together to give the final result,"E(V) = Σm∈M φ(m)".

Regards,
Blue.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 12:28 pm

Hi Blue,

blue wrote:
denis_berthier wrote:We have to guess that the probability of a subset of M is related to its cardinal (or is this also a false assumption?), but this is not written.

It's an unnecessary assumption, and also false for the examples.

blue wrote:There is an underlying sample space (the upper case omega) that is (solution grid, cell set) pairs with cell sets of a fixed size, from which elements are chosen with uniform probablity. Then there is a function from the sample space to sets of minimal puzzles, which would be the random variable, A.

This is a completely new element in the picture and a major contribution to the whole thing. It's more complex than in my vague guesses, but there's nevertheless some well defined uniform probability on some Omega space.
Obviously, the original post needs complete re-writing.
Moreover I still can't digest the "weighted sum of things picked out by A: V = Σm∈A φ(m)/Pr(m)" with a / instead of a *. For me it is a red light indicating that Pr(m) is not defined correctly. (It plays the role of the inverse of a probability, not of a probability).

red Ed wrote:That's the pdf of A. The form of the distribution doesn't matter for the analysis, except that every m with non-zero value must have a non-zero chance of being picked.

Probably a typo also.
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby blue » Thu Jun 13, 2013 2:34 pm

Hi Denis,

denis_berthier wrote:Moreover I still can't digest the "weighted sum of things picked out by A: V = Σm∈A φ(m)/Pr(m)" with a / instead of a *. For me it is a red light indicating that Pr(m) is not defined correctly. (It plays the role of the inverse of a probability, not of a probability).

This is similar to what needs to happen with the controlled-bias samples.
The puzzle collection is biased towards the low clue count end -- low clue count puzzles, have a higher probablity of being generated than the true distribution would dictate. In order to counter that in producing an E(X) value, you need to be dividing the contribution from puzzles with a particular clue count, by a factor representing the relative increase (or decrease) in probability. For low clue counts, it's dividing by a factor larger than one -- or at least larger than what you divide by, for the higher clue counts.

denis_berthier wrote:
red Ed wrote:That's the pdf of A. The form of the distribution doesn't matter for the analysis, except that every m with non-zero value must have a non-zero chance of being picked.

Probably a typo also.

I credit Red Ed for spotting this.
Obviously it wasn't a typo, but an oversight.

Best Regards,
Blue.

Added: I probably could have worded the part about E(X)'s and "controlled bias" samples, a little better. The end result is that there's a correction factor that needs to be applied to the "would be" contribution from puzzles of a given size. As a multiplicand, it's smaller near the low clue count end, where the probability of producing a puzzle with the given clue count, is higher than it would be if the generation was unbiased.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 4:50 pm

blue wrote:
denis_berthier wrote:Moreover I still can't digest the "weighted sum of things picked out by A: V = Σm∈A φ(m)/Pr(m)" with a / instead of a *. For me it is a red light indicating that Pr(m) is not defined correctly. (It plays the role of the inverse of a probability, not of a probability).

This is similar to what needs to happen with the controlled-bias samples.

OK, it's the relative density of two distributions. Pr(m) is a not a good notation for this.
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby blue » Thu Jun 13, 2013 4:59 pm

denis_berthier wrote:OK, it's the relative density of two distributions. Pr(m) is a not a good notation for this.

I'm seeing this, just before I leave for several hours -- sorry to respond so quickly.
When one of the distributions is uniform, (some constant)*Pr(m) or (some constant)/Pr(m) seems obvious.
What's amazing is that the simple (1/Pr(m)) factor, does the trick.

Off 'til later,
Blue.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Thu Jun 13, 2013 5:20 pm

blue wrote:
denis_berthier wrote:OK, it's the relative density of two distributions. Pr(m) is a not a good notation for this.

I'm seeing this, just before I leave for several hours -- sorry to respond so quickly.
When one of the distributions is uniform, (some constant)*Pr(m) or (some constant)/Pr(m) seems obvious.
What's amazing is that the simple (1/Pr(m)) factor, does the trick.

I'm not sure to understand what's amazing. The formula defining "1/Pr(m)" "does the trick" because it is the relative density (see p. 160).

What's more interesting for the controlled-bias generator is, you can get for the #clues distribution a very simple P(n+1)/P(n) formula with almost no computation. You can have something similar here.
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby blue » Fri Jun 14, 2013 4:02 am

denis_berthier wrote:I'm not sure to understand what's amazing. The formula defining "1/Pr(m)" "does the trick" because it is the relative density (see p. 160).

Yes, I suppose "amazing" is a stretch ... esp. in hindsight.
(p. 155 was nice to see).

Best Regards,
Blue.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Fri Jun 14, 2013 6:57 am

What are "p. 155" and "p. 160"? A reference to a book?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby denis_berthier » Fri Jun 14, 2013 9:27 am

Red Ed wrote:What are "p. 155" and "p. 160"? A reference to a book?

My last book
denis_berthier
2010 Supporter
 
Posts: 4235
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Fri Jun 14, 2013 6:43 pm

That's one impressive tome! :shock:
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General