Longsoran menyukai proses stokastik

Pertimbangkan proses berikut:

Ada $n$ nampan yang disusun dari atas ke bawah. Awalnya, setiap nampan berisi satu bola. Di setiap langkah, kita

1. pilih bola $b$ secara acak dan seragam
2. pindahkan semua bola dari tempat sampah yang berisi $b$ ke nampan di bawahnya. Jika sudah menjadi nampan terendah, kami menghapus bola dari proses.

Berapa banyak langkah yang dibutuhkan dalam ekspektasi sampai proses berakhir, yaitu, sampai semua $n$ bola telah dihapus dari proses? Apakah ini sudah dipelajari sebelumnya? Apakah jawabannya mengikuti dengan mudah dari teknik yang dikenal?

Dalam kasus terbaik, proses dapat selesai setelah $n$ langkah. Dalam kasus terburuk dapat mengambil langkah $\Theta(n^2)$ . Kedua kasus seharusnya sangat tidak mungkin. Dugaan saya adalah bahwa ia membutuhkan langkah $\Theta(n\log n)$ dan saya melakukan beberapa percobaan yang sepertinya mengkonfirmasi hal ini.

(Perhatikan bahwa memilih nampan secara seragam secara acak adalah proses yang sangat berbeda yang jelas akan mengambil $\Theta(n^2)$ langkah untuk menyelesaikannya.)

Bukan benar-benar jawaban, tetapi komentar panjang tentang jawaban András.

Jawaban András berisi intuisi yang bagus, meskipun saya tidak percaya ini adalah perhitungan ketat dari jumlah langkah yang diharapkan. Saya pikir ini mungkin perkiraan yang baik untuk sebuah jawaban, tetapi tampaknya tidak menangani kasus-kasus di mana nampan di bawah nampan terisi tertinggi menjadi kosong sebelum nampan atas dikosongkan ke bawah. Namun, ini mungkin perkiraan yang masuk akal untuk dibuat (saya tidak yakin).

Perhitungannya mengandung kesalahan yang mempengaruhi penskalaan. Saya akan mengambil titik awal yang sama persis, dan mengulang dan memperluas perhitungan.

Itu merindukan faktor p di dalam penjumlahan, karena probabilitas untuk secara acak memilih bin yang benar adalah daripada$\frac{p}{n}$ . Hasilnya kami punya$\frac{1}{n}$

$\begin{eqnarray*} n + \sum_{p=1}^n \sum_{k=0}^{\infty} (k+1) \frac{p}{n} \left(\frac{n-p}{n}\right)^k & = & n + \sum_{p=1}^{n} \frac{p}{n} \sum_{k=0}^{\infty} (k+1) \left(\frac{n-p}{n}\right)^k \\\\& = & n + \sum_{p=1}^{n} \frac{p}{n} \cdot \frac{n^2}{p^2} \\\\& = & n + n\sum_{p=1}^{n} 1/p \\\\& = & n (1+H_n) \end{eqnarray*}$

dengan adalah bilangan harmonik ke-n . Untuk memperkirakan H n, kita cukup mengganti penjumlahan dengan integral: H n ≈ ∫ n + 1 1$H_n = \sum_{p=1}^{n} 1/p$$H_n$. Jadi penskalaannya adalahn(1+log(n+1))atau sekitarnlog(n+1). Meskipun penskalaan ini tidak cocok dengan penskalaan masalah secara tepat (lihat simulasi di bawah), namun hampir sama dengan faktorlog(2).$H_n \approx \int_{1}^{n+1} \frac{1}{x} dx = \log(n+1)$$n (1+\log(n+1))$$n \log(n+1)$$\log(2)$

Lingkaran merah: Poin data dari simulasi proses yang dirata-rata lebih dari 10k berjalan. Hijau: . Biru: n log ( n + 1 ) .$n \log_2(n+1)$$n \log(n+1)$

Sunting: Saya meninggalkan jawaban ini sebagaimana adanya (untuk saat ini) untuk menggambarkan proses berantakan dari pembuktian teorema, sesuatu yang ditinggalkan dari makalah yang diterbitkan. Intuisi inti di sini adalah cukup fokus pada bola atas, karena menyapu semua di bawahnya. Silakan lihat komentar (khususnya @Michael menunjukkan bahwa celah dapat terjadi) dan @ Joe nanti menjawab bagaimana kesalahan diidentifikasi dan diperbaiki. Saya terutama suka menggunakan eksperimen Joe untuk memeriksa ulang apakah formula itu masuk akal.

Batas bawah adalah $n$ seperti yang Anda tunjukkan, tetapi agak mengejutkan tampaknya ada batas atas $(1 + \pi^2/6)n$ untuk jumlah langkah yang diharapkan.

To derive this, note that a sequence of balls will clear all the bins precisely if it contains a subsequence $b_1b_2\cdots b_n$ such that $b_1 = n$, $b_2 \ge n-1$, $\dots$, $b_i \ge n-i+1$. Kondisi tambahan diperlukan pada urutan untuk menghindari bola yang dipilih yang tidak lagi ada dalam sistem, tetapi untuk tujuan batas atas, anggaplah bahwa ada urutan menurun yang tak terbatas dari tempat sampah (sehingga bola tidak hilang ketika meninggalkan tempat sampah). 1, tetapi dipindahkan ke bin 0, kemudian bin -1, dan seterusnya). Maka jumlah langkah yang diharapkan agar terlihat berikutnya adalah jumlah langkah yang diharapkan sebelumnya$b_1$ terlihat, ditambah jumlah langkah yang diharapkan sebelumnya $b_2$ terlihat, dan seterusnya (turun ke 1, sejak $b_n$ dapat berupa angka apa saja $1,2,\ldots,n$). Ini dapat dilihat sebagai peristiwa yang terpisah, satu demi satu. Jumlah langkah yang diharapkan saat itu

$\begin{eqnarray*}n + \sum_{p=1}^n \sum_{k=0}^{\infty} \frac{k+1}{n} \left(\frac{n-p}{n}\right)^k & = & n + \sum_{p=1}^{n-1} \frac{1}{n-p} \sum_{k=1}^{\infty} k\left(\frac{n-p}{n}\right)^k \\& = & n + \sum_{p=1}^{n-1} \frac{1}{n-p} n(n-p)/p^2 \\& = & n + n\sum_{p=1}^{n-1} 1/p^2 \\& \le & (1 + \pi^2/6)n. \end{eqnarray*}$