palkia has asked for the wisdom of the Perl Monks concerning the following question:

Hello

I'm looking for a mathematical formula, that will give the average depth of a of a split recursion process,
where the chance of "going deeper" is constant.
(I know this is more f a mathematical than a perl question, but I need it for practical use in perl so.. ^^)

To simulate this problem I've written the following code: 
print 'num of splits [positive integer]: ';
my $splt = <>;
print 'chance of going deeper [between 0 and 1]: ';
my $chance = <>;

my $avgOf = 1000000;
my $sum = 0;
for(my $n=0;$n<$avgOf:$n++)
{$sum += dep();}
print "avg depth is ".($sum / $avgOf)."\n";
exit;

sub dep
{
  if(rand() < $chance)
  {return 1+max(multiDep())}else
  {return 0;}
}

sub multiDep
{
  my @keep;
  for($i=0;$i<$splt;$i++)
  {$keep[$i] = dep();}
  return @keep;
}

sub max
{
  my $hi = shift;
  for my $v (@_)
  {if($v > $hi){$hi = $v;}}
  return $hi;
}

[download]
I need to be able to tell the average value returned by "dep()" (printed number), as a function of the given value of $chance.
How can I calculate (mathematical function) it when:
'$splt = 1" "$splt = 2" "$splt = 3" "$splt = 4" etc

I figured the question for the "$splt = 1" case, where the desired formula is $chance/(1-$chance).
The solution required knowledge of:
basic statistics, basic geometric series, basic integrals.

I would go by experimenting than graphing and than theorizing, but even when only examining the average of 1000000 tries each time, the result still varies too much to be considered accurate enough for this strategy.

I'm sure if I can understand the solution for "$splt = 2" I'll be able to figure the rest by myself.

Help please ^^
Thx a lot

Replies are listed 'Best First'.
Re: Average random depth formula required
by SuicideJunkie (Vicar) on May 01, 2012 at 21:35 UTC

    Don't bother simulating rolls, just multiply the value of each possibility by the odds of reaching it, and hope you've got a converging series.

    For the simple case of a chance of stopping at each integer, its pretty simple.

    ∑ak = 1 / (1 - a)
    For reasonable values of a, of course.

    Also, ∑k*ak = a / (1 - a)2

    As an example, for a 50/50 flip, you'll average two flips before losing.
    0.5 / (1-0.5)2 = 0.5 / (0.52) = 0.5 / 0.25 = 2
[reply]
      Thx
      This is pretty much how I figured the "$splt = 1" case
      (although ∑a^k is a / (1 - a) not 1 / (1 - a) as k starts at 1 since $chance=0 causes the return of "zero" value !)
      but how can it be implemented to solve for "$splt = 2" ?
      Yeah I know "sum over value times odds" but it seems like that approach goes requires some very complicated combinatorial problem solving.
      if(you see something I'm missing){please share ^^}

      bry: while checking for "$splt=2", I discovered the value of "1" is returned when "$chance" is about 0.35793
      for which I can't find any special properties
      (maybe that exp(0.35793^0.35793) ~ 2, but not counting on it being the actual exact value ^^)
[reply]

        A chance of 0 means your average depth is going to be zero. If you are counting the number of coin flips instead of the number of wins, then you need to add one to the result ;)

        That odd number should probably be 1/e = ~0.367879441

[reply]

Back to Seekers of Perl Wisdom