Randomly partitioning a 30 second time interval

Forums: Software, Mathematics, Probability, Algorithms, Probablity
Email this Topic • Print this Page

Here's the scenario:

On a computer I am randomly playing a collection of audio clips of durations from 1 second to 30 seconds in length, such that the total of all clips played within any 30 second window must exactly equal 30 seconds (clips are grouped in one second intervals by duration - e.g. a group of 1 second clips, a group of 2 second clips... up to a group of 30 second clips).

Theoretically it would be possible to play a clip of a particular length multiple times within a 30 second window (e.g. (30 - 1 second clips) or (2 - 15 second clips) or (3 - 10 second clips) or (3 - 4 second clips +3 - 2 second clips +1 - 10 second clip + 2 - 1 second clips) or any of a myriad of other permutations that add up to exactly 30 seconds)

Simply using a random function where a clip duration's chance to be played is one out of the number of remaining seconds in the window has a strong bias towards short clips (for instance 1 second clips have 30 chances to be randomly selected whereas 30 second clips only have 1 chance of being randomly selected).

My goal is to give an equal chance to pick any particular duration during a given 30 second window. So my program needs to weight clips to that they get picked with an equal chance.

I started to work out by exhaustive example the permuations of each clip being played so I could count them and then produce weights that would smooth probability curve- this quickly proved to be unworkable...

Is there a technique that I could use to come up with my weights?

Any help would be appreciated! Thanks

Topic Stats
Top Replies
Link to this Topic

Type: Question • Score: 0 • Views: 3,502 • Replies: 21

No top replies

@Neoheurist,

Am I right in thinking that you do not want clips to span two 30-second windows?

For example, you don't want to start a 15-second clip at the 20-second mark in a window.

2 Replies

@DrewDad,

No - just one 30 second window. In reality the first half of the minute has 5 seconds at the beginining of the minute reserved to announce the time and there's always a beep at 30 seconds through the minute - so there's a 25 second window and a 30 second window - but I want to treat these independently

1 Reply

@Neoheurist,

There is no way to do this. Consider the 29 second interval. For every 29 second clip picked, there must be a one second clip chosen, so if you want the incidence of 29 second clips to match the incidence of one second clips, one second clips can only be chosen with 29 second clips and that is clearly not going to happen.

1 Reply

@DrewDad,

OK.

Check my thinking: You have two variables you're trying to balance. One is the number of clips, and for each clip there is are only a certain number of timeslots where the clip can be started.

And if you play continuously for, say, a month, you want each clip to play the same number of times. (approximately)

1 Reply

@DrewDad,

That would be an excellent way to describe want I want to achieve

1 Reply

@engineer,

good point... nonetheless I want to skew the probablity of the 29 second clip being picked so that it gets promoted in the rotation - basically how close to a flat distribution curve can I get.

2 Replies

@Neoheurist,

OK. I'll have to ponder it some, and see if anything lights up.

0 Replies

@Neoheurist,

as you can see I'm having a hard time even formulating the problem... I guess a way to express the goal is to reduce the amount of clip repetition... I'm inclined toward simply creating many many more 1 second clips since the algorithm is automatically skewed toward smaller clips... and if I'm going to take this approach it would be nice to know how many clips of each duration would be required to acheive a balanced variety of clips being played.

0 Replies

@Neoheurist,

The first thing to do is ask yourself who gives a flying whether or not your music compilations are evenly distributed?

The next thing to do is pair a 1 second and a 29 second clip. Then pair a 2 second and a 28 second clip. Keep repairing until you finally match a 29 second clip with a 1 second clip. Toss in 2 of your 30 second clips.

You now have 29 pairs and 2 singles which tally 30 seconds with each time length having a probability of 2 chances in 31 of being selected randomly.

1 Reply

@solipsister,

The goal is to stream the clips for long periods without a lot of repetition - and the content is probably 50/50 music and spoken word... additionally I'm not looking to just partition the 30 second window into 2 partitions, but instead a random number of partitions... presently the next clip is selected based upon the amount of time remaining in the current window. This can result in the window being broken up into clips like this: 4 sec, 7 sec, 2 sec, 5 sec, 1 sec, 2 sec, 9 sec. When this happens the tendency favors lots of small clips and as a result a tendency to be repetitious (this can be combated by adding more content on the small clips size, but I would find it more pleasing to my ear to work out a methodology that smooths the distribution of clip lengths... (call it an emotional desire for smoothness)

2 Replies

@Neoheurist,

Engineer identified a possible problem, but I don't think that it's unsolvable.

Take a special case where there is one one-second clip and another 29-second clip. It would always play the two clips equally, as long as the algorithm had memory. (In this case, the gambler's fallacy would be true.)

0 Replies

@Neoheurist,

You asked for an even distribution of clips with lengths from 1 second to 30 seconds.

I gave you the answer.

0 Replies

@Neoheurist,

What distribution curve do you want to flatten?

For instance, let's simplify the problem and reduce the length of the interval to 4. There are 5 unordered partitions of 4 (30 has 5604):
4
3, 1
2, 2
2, 1, 1
1, 1, 1, 1
Some of these can be permuted to obtain these 8 ordered subintervals (30 has 2^29):
4
3, 1
2, 2
2, 1, 1
1, 3
1, 2, 1
1, 1, 2
1, 1, 1, 1
Do you want to flatten the distribution curve of these 8 ordered subintervals such that the probability of hearing a 4-second clip is the same as the probability of hearing a 1-2-1 sequence? If so, I suggest you first randomly select one of the 8, then randomly select clips of the proper length. How many do you need of each length? Well that depends on your tolerance for repetition. In this example, on average, for each 4-second clip you have, you'd need 2 3-second clips, 5 2-second clips, and 12 1-second clips.

Perhaps you'd rather flatten the distribution curve of the 5 unordered subintervals (listed above) and permute afterward. That means you'd get one of 2-1-1, 1-2-1, or 1-1-2 as frequently as you'd get 4. In this case, for each 4-second clip you have, you'd need 1 3-second clip, 3 2-second clips, and 7 1-second clips.

0 Replies

If you want my best shot at evening out the distribution and you understand that it is impossible, the way I would do it is to weight each segment according to -2^(int(30/n)) where n is the segment length. This means that 16-30 all have the same weight, 11-15 all have the same weight (half of 16-30), 8-10 have the same weight, etc. with one being nearly impossible. Here is what a run of 5000 trials looked like.

1 1319
2 896
3 695
4 734
5 518
6 463
7 517
8 605
9 428
10 333
11 462
12 399
13 297
14 251
15 197
16 374
17 348
18 334
19 364
20 287
21 283
22 295
23 307
24 284
25 274
26 292
27 246
28 265
29 263
30 255

1 Reply

@engineer,

I had second thoughts about putting the int function in there. Taking it out I get the following test results. Not much different.

1 1243
2 878
3 791
4 644
5 565
6 538
7 465
8 420
9 416
10 370
11 348
12 322
13 305
14 275
15 261
16 279
17 267
18 272
19 238
20 280
21 296
22 260
23 316
24 273
25 285
26 321
27 326
28 326
29 310
30 345

1 Reply

@engineer,

90%+ of these have a clip that consumes at least half the interval. That's understandable given the goal. That's why I'm wondering if (s)he'd really prefer to even out the frequencies of the partitions - not the frequencies of the clip lengths.

1 Reply

@markr,

The idea behind the approach I landed upon was to improve the likelihood of longer clips by giving them more chances to be selected - using jagged arrays - in the arrays I placed "lots" that represented the length of the clip to be played - in the selection array that represents 30 seconds remaining in the segment 300 lots are created for a 30 second clip to be chosen tapering down to 10 lots for a 1 second clip.

In VB I wrote a function to create weights for each clip length:

Code:

    Private Sub SetClipWeights(WeightedClipLengths()() As Integer)

        Dim w, x, y, z As Integer

        For w = WeightedClipLengths.Count - 1 To 0 Step -1

            y = 0

            For x = w To 0 Step -1

                For z = CInt((WeightedClipLengths.Count * 10) / (WeightedClipLengths.Count - x)) To 1 Step -1

                    ReDim Preserve WeightedClipLengths(w)(y)

                    WeightedClipLengths(w)(y) = x + 1

                    y += 1

                Next

            Next

        Next

    End Sub

I wrote the following generalized function to show the number of times a particular clip length was randomly selected:

Code:

    Private Sub TestClipWeights(WeightedClipLengths()() As Integer)

        Dim SegmentLength = WeightedClipLengths.Count

        Dim ClipFrequency(SegmentLength - 1) As Integer

        Dim RemainingSegmentLength As Integer = SegmentLength

        For x = 0 To 999999

            Dim ClipLength As Integer = WeightedClipLengths(RemainingSegmentLength - 1)(Math.Floor(Rnd() * WeightedClipLengths(RemainingSegmentLength - 1).Count))

            ClipFrequency(ClipLength - 1) += 1

            RemainingSegmentLength -= ClipLength

            If RemainingSegmentLength = 0 Then

                RemainingSegmentLength = SegmentLength

            End If

        Next

    End Sub

Called by the follow snippet:

Code:



    Private WeightedClipLengthsSegment As Integer()() = New Integer(30)() {}

...

    SetClipWeights(WeightedClipLengthsSegment)



    TestClipWeights(WeightedClipLengthsSegmentA)

The frequencies of the longest clips were significantly boosted:

Secs Hit Frequency
(1) 268390
(2) 107179
(3) 65726
(4) 42842
(5) 33157
(6) 25085
(7) 19389
(8) 17001
(9) 15711
(10) 13101
(11) 12198
(12) 11474
(13) 11053
(14) 10705
(15) 10438
(16) 10033
(17) 9744
(18) 10282
(19) 10395
(20) 10766
(21) 11477
(22) 12282
(23) 13574
(24) 14890
(25) 17049
(26) 19825
(27) 24186
(28) 31733
(29) 46625
(30) 93690

As compared to a simple random partitioning where a random amount of the remaining segment is chosen:

Secs Hit Frequency
(1) 250855
(2) 125268
(3) 83563
(4) 62320
(5) 49822
(6) 41695
(7) 35686
(8) 31159
(9) 27695
(10) 24780
(11) 22866
(12) 20805
(13) 19459
(14) 17991
(15) 16757
(16) 15738
(17) 14634
(18) 13964
(19) 13197
(20) 12562
(21) 11898
(22) 11460
(23) 10907
(24) 10406
(25) 9999
(26) 9548
(27) 9310
(28) 8765
(29) 8618
(30) 8273

To my ear it's a much more pleasant distribution....

2 Replies

@Neoheurist,

I also realized that if I were to change the requirement to always just partition a 30 second segment into 2 clips the distribution would automatically be flat.

Paired as follows:
30,0
29,1
28,2
27,3
26,4
25,5
24,6
23,7
22,8
21,9
20,10
19,11
18,12
17,13
16,14
15,15
14,16
13,17
12,18
11,19
10,20
9,21
8,22
7,23
6,24
5,25
4,26
3,27
2,28
1,29

As I mentioned earlier - actually formulating the problem was part of my problem... And it also goes to show that flexibility in thinking and the ability to challenge requirements is often a path to the better solution.

I appreciate the contributions of all Thanks!

0 Replies

@Neoheurist,

Looks similar to engineer's distribution. If that's the distribution you want, then that tells you the relative number of clips of each length you need.

1 Reply

Randomly partitioning a 30 second time interval

Related Topics

Quick Links

My Account

able2know