Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
18 replies to this topic

#11 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 31 March 2010 - 03:37 PM

Maybe you guys can help me with a stumbling block that always keeps me from trying these types of questions.

What exactly does it mean when it asks for the expected number of iterations to go from one state to another?

Spoiler for Take this problem as an example

The expected number of iterations is the sum of products of the probability of a path with its length. The sum is over all possible paths. The expected length is what we usually call the average length. I hope this helps.
  • 0

#12 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 31 March 2010 - 05:25 PM

Yes, there are some fun problems on here. It's a nice site.

You have a very good, simple solution.

Spoiler for


Nice catch. I didn't see that mistake. Your approach is one that i didn't think of. I solved this problem because I learned about Markov random chains before, so the framework is there. I find your solution to be more impressive since it is a brilliant and original application of probability rules and algebra. Well done.
  • 0

#13 mmiguel1

mmiguel1

    Advanced Member

  • Members
  • PipPipPip
  • 392 posts

Posted 01 April 2010 - 08:23 AM

Maybe you guys can help me with a stumbling block that always keeps me from trying these types of questions.

What exactly does it mean when it asks for the expected number of iterations to go from one state to another?

Spoiler for Take this problem as an example


Here is how I interpret the expected value with regard to this problem.

Let's define a complete game as one where we start at the initial conditions of the game, and perform iterations until we reach the ending conditions.
The number of iterations is a random number it may be the answer that bushindo gave, or possibly 3 more than that or 3 less, or even 100 more (with very small probability).

Let's play one complete game and record the number of iterations.
We can then play another complete game and get a different number of iterations (which is random with the same probability distribution).
If we play N different complete games we can get an average iteration number by summing all of the random values we got and dividing by N.
Let's call the sum of all the values S.
Average = S/N

Here is the key step. Assuming that the iteration number has the same probability distribution in each complete game (i.e. the likelihood of outcomes don't change if you play the game again), then the limit of S/N as N approaches infinity (if we play an infinite number of complete games) will approach the expected value of the iteration number.

So think about the expected value as the average result if you perform the random process an infinite number of times.

This isn't strictly, the defining expression for the expected value, but it is true under the conditions I stated.
There is a theorem that states this called the Law of Large Numbers (funny name).

The definition of expected value for discrete variables is the weighted sum of each value the number can take where each value is weighted by the probability of getting that value.

Hope that helps.
  • 0

#14 mmiguel1

mmiguel1

    Advanced Member

  • Members
  • PipPipPip
  • 392 posts

Posted 01 April 2010 - 08:27 AM

Nice catch. I didn't see that mistake. Your approach is one that i didn't think of. I solved this problem because I learned about Markov random chains before, so the framework is there. I find your solution to be more impressive since it is a brilliant and original application of probability rules and algebra. Well done.


Thanks, I appreciate that, but the method I used cannot match the efficiency and usefulness of the one you used.

I read a quote today that this reminds me of.

"Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it."
-Alan J. Perlis, "Epigrams in Programming"
  • 0

#15 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 01 April 2010 - 10:12 AM



Spoiler for How about this approach

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#16 Tuckleton

Tuckleton

    Advanced Member

  • Members
  • PipPipPip
  • 201 posts

Posted 01 April 2010 - 10:28 AM

Phew! That's kind of intimidating isn't it? Thanks a bunch for the info you two! :)
  • 0

#17 mmiguel1

mmiguel1

    Advanced Member

  • Members
  • PipPipPip
  • 392 posts

Posted 01 April 2010 - 04:34 PM



Spoiler for How about this approach

Does that give the expected value in general or is it just coincidence here?
Not to say it isn't true, it just seems too easy to believe to me, and I don't have time at this moment to work it out in a general case.
I will try later if no one else argues about it.
  • 0

#18 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 01 April 2010 - 05:20 PM



Spoiler for How about this approach


It seems to be a coincidence.

Spoiler for because

  • 0

#19 mmiguel1

mmiguel1

    Advanced Member

  • Members
  • PipPipPip
  • 392 posts

Posted 02 April 2010 - 12:15 AM

It seems to be a coincidence.

Spoiler for because


Makes sense to me.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users