重複をゆるす順列の種類数の平均

[Yoshitaka Ikeda]

N種類のデータをk個（重複を許して）並べた場合のデータの種類数の
平均を求めたいと考えています。

たとえば、2種類のデータを3個並べる場合
000
001
010
011
100
101
110
111
の8通りがあり、その中でデータ種類数が1のものが2つ、2のものが6つあります。
すなわち、(1*2+2*6)/8=14/8 となります。

この場合から考えるとデータ種類数がtのものの個数m_tは
m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
と考えられます。
N=2 k=3ならば
m_1={(1^3)*2C1}-0=1*2=2
m_2={(2^3)*2C2}-{(1^3)*2C1}=8*1-1*2=6
となり、前記のものと一致します。
これは、データt種類をk個適当に並べる方法がt^kであり、
そのt種類をN個の中から選ぶ方法が_N C_tであるところから、
きています。(t-1の分を引いてるのはt-1種類しか選んでいないものを排除するため)
Σt*m_t / N^k
が種類数の平均となるはずです。

さて、k=36 N=32でやってみました。するとt=19あたりで、
本来の全数すなわちN^kを超えます。
とすると、上の仮定は間違えていることになります。
どうやって考えればよいのでしょうか。

--
Yoshitaka Ikeda mailto:ik...@4bn.ne.jp

[Tsukamoto Chiaki]

工繊大の塚本と申します.

In article <bv55l2$3lg$1...@caraway.media.kyoto-u.ac.jp>

Yoshitaka Ikeda <ik...@4bn.ne.jp> writes:
> この場合から考えるとデータ種類数がtのものの個数m_tは
> m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
> と考えられます。

これが間違っていることは直ぐに分かります. N = t = 3 とすると,
0, 1, 2 の 3 文字からなる k 字の文字列の個数は 3^k,
そのうち 0, 1 の 2 文字だけからなる文字列が 2^k,
そのうち 0, 2 の 2 文字だけからなる文字列が 2^k,
そのうち 1, 2 の 2 文字だけからなる文字列が 2^k, だが,
3^k - 3 * 2^k とすると,
0 の 1 文字だけからなる文字列 1,
1 の 1 文字だけからなる文字列 1,
2 の 1 文字だけからなる文字列 1,
をそれぞれ二回引いていることになるので, 正しくは
3^k - 3 * 2^k + 3
となる筈.

# k = 1, 2, ... , t - 1 では 0 になる筈でしょう.

> さて、k=36 N=32でやってみました。するとt=19あたりで、
> 本来の全数すなわちN^kを超えます。

これは良く分からない. 何が N^k を超えているのですか.
--
塚本千秋@応用数学.高分子学科.繊維学部.京都工芸繊維大学
Tsukamoto, C. : chi...@ipc.kit.ac.jp

[Yuzuru Hiraga]

Yoshitaka Ikeda wrote:
> N種類のデータをk個（重複を許して）並べた場合のデータの種類数の
> 平均を求めたいと考えています。
...

> この場合から考えるとデータ種類数がtのものの個数m_tは
> m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
> と考えられます。

まず t>k なら m_t は 0 にならなければならないけど、
上の式ではそれが現れていませんよね。

# 以下２項係数 _N C_t は C(N, t) のように書きます。

> これは、データt種類をk個適当に並べる方法がt^kであり、
> そのt種類をN個の中から選ぶ方法が_N C_tであるところから、
> きています。

これがすでに間違っていることは N=3 ぐらいを
見てもわかりますね。（それぐらいチェックしようよ）

これだと３色以下で２個並べる方法は：
　2^2 * C(3, 2) = 12 通り
あることになるけど、実際には 3^2 = 9 通りしかない。
同じものを重複して数えているからです。
具体的には、下のように aa, bb, cc が２度数えられている：
　aa ab ba bb
　bb bc cb cc
　cc ca ac aa

あるいは N=3, k=3 だと、m_3 は 3! = 6 でなければならないのに、
上の式だと 3 になってしまう。今度は重複分の引きすぎですね。

=====
きれいな形で表せるかはまだわからないんだけど、力技でやるなら、
とりあえず漸化式は作れる。

M(t) を、ちょうど t 種類のデータを使って作れる長さ k の
データ列の個数とします（k は文脈で決まる）。
すると池田さんの m_t は：
　m_t = C(N, t)*M(t)
になります。
ここで M(t) は、t 種類（以内）のデータで作れる総数 t^k から
t 種類未満のデータしか使っていないものを引けばいいから：
　M(t) = t^k - C(t, 1)M(t-1) - C(t,2)M(t-2) - ... - C(t,t-1)M(1)
　　　　= t^k - Σ_{i=1...t-1} C(t,i)M(t-i)
　M(1) = 1

これを展開・整理すれば、あるいは全面的に考え直せばもっと
簡単になるかもしれないけど、とりあえず強引にプログラムして
みた限りでは大丈夫そうです。

（平賀＠筑波大）

[Yoshitaka Ikeda]

Yuzuru Hiragaさんの<401643FD...@ulis.ac.jp>から

>
>
>Yoshitaka Ikeda wrote:
>> N種類のデータをk個（重複を許して）並べた場合のデータの種類数の
>> 平均を求めたいと考えています。
> ...
>> この場合から考えるとデータ種類数がtのものの個数m_tは
>> m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
>> と考えられます。
>
>まず t>k なら m_t は 0 にならなければならないけど、
>上の式ではそれが現れていませんよね。

なんか、うまくまとめられるかなと思ってまとめちゃったんですが
まとめる前の式が間違っていたのでした。

># 以下２項係数 _N C_t は C(N, t) のように書きます。
>
>> これは、データt種類をk個適当に並べる方法がt^kであり、
>> そのt種類をN個の中から選ぶ方法が_N C_tであるところから、
>> きています。
>
>これがすでに間違っていることは N=3 ぐらいを
>見てもわかりますね。（それぐらいチェックしようよ）
>
>これだと３色以下で２個並べる方法は：
>　2^2 * C(3, 2) = 12 通り
>あることになるけど、実際には 3^2 = 9 通りしかない。
>同じものを重複して数えているからです。
>具体的には、下のように aa, bb, cc が２度数えられている：
>　aa ab ba bb
>　bb bc cb cc
>　cc ca ac aa

そうですね。1種類しか使っていないものが、3^1とおりと数えてしまったので
すが、ここはC(3,2)*(C2,1)=6と数えるべきだったのでした。

>あるいは N=3, k=3 だと、m_3 は 3! = 6 でなければならないのに、
>上の式だと 3 になってしまう。今度は重複分の引きすぎですね。
>
>=====
>きれいな形で表せるかはまだわからないんだけど、力技でやるなら、
>とりあえず漸化式は作れる。
>
>M(t) を、ちょうど t 種類のデータを使って作れる長さ k の
>データ列の個数とします（k は文脈で決まる）。
>すると池田さんの m_t は：
>　m_t = C(N, t)*M(t)
>になります。
>ここで M(t) は、t 種類（以内）のデータで作れる総数 t^k から
>t 種類未満のデータしか使っていないものを引けばいいから：
>　M(t) = t^k - C(t, 1)M(t-1) - C(t,2)M(t-2) - ... - C(t,t-1)M(1)
>　　　　= t^k - Σ_{i=1...t-1} C(t,i)M(t-i)
>　M(1) = 1
>
>これを展開・整理すれば、あるいは全面的に考え直せばもっと
>簡単になるかもしれないけど、とりあえず強引にプログラムして
>みた限りでは大丈夫そうです。

とりあえず、何かきれいな式を出そうという目的ではなく、確率計算をした
かったので、このとおりにプログラムを作ってみたところ、大きな値でもほぼ
予想通りの矛盾のない結果がでました。
#ちなみに、ほしかったのは、N=32,k=36だったのでした。

[Tsukamoto Chiaki]

工繊大の塚本です. しまった.

In article <04012718431...@ims.ipc.kit.ac.jp>

Tsukamoto Chiaki <chi...@ipc.kit.ac.jp> writes:
> 3^k - 3 * 2^k + 3
> となる筈.

正しくは 3^k - 3 * 2^k + 3 * 1^k - 0^k ですね.

# 本質的には Stirling numbers of the second kind.

[GON]

"Yuzuru Hiraga" <hir...@ulis.ac.jp> wrote in message news:401643FD...@ulis.ac.jp...

> きれいな形で表せるかはまだわからないんだけど、力技でやるなら、
> とりあえず漸化式は作れる。
>
> M(t) を、ちょうど t 種類のデータを使って作れる長さ k の
> データ列の個数とします（k は文脈で決まる）。
> すると池田さんの m_t は：
> 　m_t = C(N, t)*M(t)
> になります。
> ここで M(t) は、t 種類（以内）のデータで作れる総数 t^k から
> t 種類未満のデータしか使っていないものを引けばいいから：
> 　M(t) = t^k - C(t, 1)M(t-1) - C(t,2)M(t-2) - ... - C(t,t-1)M(1)
> 　　　　= t^k - Σ_{i=1...t-1} C(t,i)M(t-i)
> 　M(1) = 1

ここでのM(t)はkにも依存しますからM(t,k)と書いて
もうちょっと簡単にしてみます。

C(t,i)=C(t,t-i)の性質とt-i⇒iの変数変換を行えば

M(t,k) = t^k - Σ_{i=1...t-1} C(t,i)M(i,k)

和を左辺へ移行してC(t,t)=1とM(i,0)=0を使って

Σ_{i=0...t} C(t,i)M(i,k) = t^k

と結構きれいにまとまります。ここに何らかの反転公式か
何かが使えればM(i,k)について解けそうなんですが
私はこれ以上わかりません。

ご存知の方、フォローお願いします。

[GON]

"GON" <g...@mocha.freemail.ne.jp> wrote in message news:bv8ijf$cfu$1...@news511.nifty.com...

> Σ_{i=0...t} C(t,i)M(i,k) = t^k
>
> と結構きれいにまとまります。ここに何らかの反転公式か
> 何かが使えればM(i,k)について解けそうなんですが
> 私はこれ以上わかりません。

反転公式か何かないかと探したらありました。

参考文献：　山本幸一著「順列・組合せと確率」岩波書店p.91-92

これによると、

A(n) = Σ_{k=0...n} C(n,k) a(k)

のときa(n)は

a(n) = Σ_{k=0...n} (-1)^k C(n,k) A(n-k)

と表されるそうです。これを使えばM(n,m)は次のようになります。

M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m

となります。例えば、M(3,k)なら塚本さんの結果がでますし
池田さんの投稿にあるN=32,k=36の場合は

M(32,36) = 32^36 - C(32,1) * 31^36 + C(32,2) * 30^36 - ・・・ - C(32,31) * 1^36 + 0^36

　　　　　　= 1079603166268837867793599865083888926720000000

と計算されます。

＃　Mathmaticaを使って計算しました。

[Tsukamoto Chiaki]

工繊大の塚本です.

In article <bv8o05$llh$1...@news511.nifty.com>

"GON" <g...@mocha.freemail.ne.jp> writes:
> M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m
>
> となります。

これは「包除原理」で出る式ですね. 因みに,

In article <bv8ijf$cfu$1...@news511.nifty.com>
"GON" <g...@mocha.freemail.ne.jp> writes:
% Σ_{i=0...t} C(t,i)M(i,k) = t^k
%
% と結構きれいにまとまります。

これは Σ(t!/(t-i)!)(M(i,k)/i!) = t^k と書き直すと, Stirling numbers
of the second kind (M(i,k)/i!) を使って, ベキ乗を下降ベキ乗で表す式
です. 例えば

t^4 = t(t-1)(t-2)(t-3) + 6t(t-1)(t-2) + 7t(t-1) + t.

[Yuzuru Hiraga]

GON wrote:
> 反転公式か何かないかと探したらありました。
　　　...

>これを使えばM(n,m)は次のようになります。
>
> M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m
>
> となります。例えば、M(3,k)なら塚本さんの結果がでますし

本人からのコメントもありますが、塚本さんは上の一般式
（あるいはそれと同等のもの）も承知していたでしょうね。
# それを直に書かないのが塚本さんらしい。

元の池田さんの問題から言えば、上は n>m の場合には
使えないのですが、これは単純に：
　n>m のときは M(n,m) = C(n,m) * M(m,m)
でいいですね。

（平賀＠筑波大）

[Yuzuru Hiraga]

Yuzuru Hiraga wrote:
> 元の池田さんの問題から言えば、上は n>m の場合には
> 使えないのですが、これは単純に：
> 　n>m のときは M(n,m) = C(n,m) * M(m,m)
> でいいですね。

すみません、どえらい勘違いをしてました。
これは元の式通り 0 でいいですね。
# 別の問題を考えていたもので。

> （平賀＠筑波大）
>

[GON]

"Tsukamoto Chiaki" <chi...@ipc.kit.ac.jp> wrote in message news:0401291225...@ims.ipc.kit.ac.jp...

> 工繊大の塚本です.
>
> In article <bv8o05$llh$1...@news511.nifty.com>
> "GON" <g...@mocha.freemail.ne.jp> writes:
> > M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m
> >
> > となります。
>
> これは「包除原理」で出る式ですね. 因みに,

なるほど、「包除原理」って言うんですか。勉強になります。ｍ（_ _）ｍ

> In article <bv8ijf$cfu$1...@news511.nifty.com>
> "GON" <g...@mocha.freemail.ne.jp> writes:
> % Σ_{i=0...t} C(t,i)M(i,k) = t^k
> %
> % と結構きれいにまとまります。
>
> これは Σ(t!/(t-i)!)(M(i,k)/i!) = t^k と書き直すと, Stirling numbers
> of the second kind (M(i,k)/i!) を使って, ベキ乗を下降ベキ乗で表す式
> です. 例えば
>
> t^4 = t(t-1)(t-2)(t-3) + 6t(t-1)(t-2) + 7t(t-1) + t.

スターリング数ってのは組合せ論によく出てくるようですね。
向学のためもうちょっとここらへんを勉強してみます。

[GON]

重複順列中の平均種類数の応用として、お菓子のおまけの製品入れ替え時期の
計算に使えないかやってみました。

私の世代なら子供のころプロ野球カードとかガチャガチャとか流行ってましたけど
今だと何があるのかなぁ？ビックリマンチョコのおまけとか？（古い？ｗ）

例えば、お菓子会社が５０種類のおまけカードを付録につけて売っていたとします。
そのお菓子を買う子供は市場調査によって１人あたり１ヶ月１５個（２日に１回）
買っているとします。

ここで、その子が５０種類のカードをすべて集めるまでにどのぐらい時間が掛かるか
先に投稿したグラフを参考に概算を出してみます。Ｎ＝５０のグラフを見ると４００個
程度でほぼ５０種類近くに達するようです。すると

４００（個）÷１５（個/月）≒２７ヶ月＝２年３ヶ月

と概算が出ます。従って、そのお菓子のおまけは最大でも２年程度で新しいものに
しないと飽きられてしまう計算になります。

ところが実際は、友達同士でカードの交換したりしてそれより早くすべてのカードを
集めてしまうでしょうから、これより早く製品入れ替えをしないとダメでしょうね。

ただ、友達同士の交換がほとんどありえないような場合ならこの計算でほぼ概算が
出せるでしょう。

製品の製造計画なんかに使えそうな実用的な数学ですね。

では。

[GON]

"Yuzuru Hiraga" <hir...@ulis.ac.jp> wrote in message news:401899A7...@ulis.ac.jp...

>
> GON wrote:
> > 反転公式か何かないかと探したらありました。
> 　　　...
> >これを使えばM(n,m)は次のようになります。
> >
> > M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m
> >
> > となります。例えば、M(3,k)なら塚本さんの結果がでますし
>
> 本人からのコメントもありますが、塚本さんは上の一般式
> （あるいはそれと同等のもの）も承知していたでしょうね。
> # それを直に書かないのが塚本さんらしい。

それを書くのが私らしい。（笑）

塚本さんは数学者ですからそういったことは十分承知していてわざわざ
書かないのでしょうが、私は数学者じゃありませんからそういった公式が
あることすら知りませんし単純に頭の体操としてしか見てません。

私の場合はそれ自体よりもその応用を考えるほうに興味があります。
多分、池田さんは何かこの問題の前に関係した仕事があってそこから
生じた問題を数学的な問題として焼きなおして聞いてるんでしょうね。
むしろ私はその動機のほうに関心があります。

純粋に数学的な問題としては面白くないのかもしれませんが、その結果
どんな応用がありえるのかを考えるのは結構楽しいです。

＃　物理出身だからかもしれませんが・・・

[Tsukamoto Chiaki]

工繊大の塚本です.

In article <bvags7$h5d$1...@news511.nifty.com>

"GON" <g...@mocha.freemail.ne.jp> writes:
> なるほど、「包除原理」って言うんですか。勉強になります。ｍ（_ _）ｍ

ちゃんと書いておきましょうか.

総数 N 個のものの内, 例えば a, b, c, d 全ての条件を満たすものだけの
個数 M を求めようとします. 条件 a を満たさ *ない* ものの個数を N(a),
条件 a も 条件 b も満たさないものの個数を N(ab), etc., と書くことに
すると,

M = N - N(a) - N(b) - N(c) - N(d)
+ N(ab) + N(ac) + N(ad) + N(bc) + N(bd) + N(cd)
- N(abc) - N(abd) - N(acd) - N(bcd)
+ N(abcd)

となる, というのが「包除原理」です. N(ab) = N(ac) = … = N(cd) と
なっていたりするのなら, 組み合わせの数でまとめられます.

# 一般での記述とその証明は省略.

[KUROSAWA Takashi]

Tabby as くろさわ@秩父です。

"GON" <g...@mocha.freemail.ne.jp> wrote in
message <bvah28$hef$1...@news511.nifty.com>:

> ここで、その子が５０種類のカードをすべて集めるまでにどのぐらい時間が掛かるか
> 先に投稿したグラフを参考に概算を出してみます。Ｎ＝５０のグラフを見ると４００個
> 程度でほぼ５０種類近くに達するようです。すると

50 種類を集めるのに掛かる回数は 225 回ではないですか?
サイコロだと 15 回。
　n/n + n/(n-1) + n/(n-2) + … n/1

サイコロで考えると…
　○1 番目の目
　　どれが出てもイイから確率 6/6、出るまでに掛かる回数はその
　　逆数の 6/6 回。
　○2 番目の目
　　最初に出た 1 つを避けるから確率 5/6、出るまでの回数は逆数
　　の 6/5 回。
　～(snip)～
　○6 番目の目
　　既出の 5 つを避けるから確率 1/6、出るまでの回数は逆数の
　　6/1 回。
…という、個々の理想の試行回数を足し合わせて…
　6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1
　　= 147/10
　　= 14.7、切り上げて 15 回
…となります。コンピュータで乱数を廻して検証しました。

　 Tabby as くろさわ
　 ta...@yk.rim.or.jp
　 http://www.yk.rim.or.jp/‾tabby/

[GON]

"KUROSAWA Takashi" <ta...@yk.rim.or.jp> wrote in message news:bvavbu$2mqd$1...@news2.rim.or.jp...

> Tabby as くろさわ@秩父です。
>
> "GON" <g...@mocha.freemail.ne.jp> wrote in
> message <bvah28$hef$1...@news511.nifty.com>:
> > ここで、その子が５０種類のカードをすべて集めるまでにどのぐらい時間が掛かるか
> > 先に投稿したグラフを参考に概算を出してみます。Ｎ＝５０のグラフを見ると４００個
> > 程度でほぼ５０種類近くに達するようです。すると
>
> 50 種類を集めるのに掛かる回数は 225 回ではないですか?
> サイコロだと 15 回。
> 　n/n + n/(n-1) + n/(n-2) + … n/1

どうやらプログラミングミスがあったようです。

ちょっと調べてみます。

では。

[GON]

間違いがわかりました。

"GON" <g...@mocha.freemail.ne.jp> wrote in message news:bv92pt$5to$1...@news511.nifty.com...
> "GON" <g...@mocha.freemail.ne.jp> wrote in message news:bv8o05$llh$1...@news511.nifty.com...

>
> > M(n,m) = Σ_{k=0...n} (-1)^k C(n,k) (n-k)^m
>

> を使って池田さんが求めたかった重複順列中の種数の平均がどんなものか
> グラフで見てみます。
>
> N種類のデータをk個（重複を許して）並べた場合のデータの平均種類数H(N,k)は
>
> H(N,k) = Σ_{n=0...N} n*M(n,k)/N^k

ここでC(N,n)を掛けるのを忘れてました。

正しくは、

H(N,k) = Σ_{n=0...N} n*C(N,n)*M(n,k)/N^k

です。従って、

H(N,k) = {C(N,1)*M(1,k) + 2*C(N,2)*M(2,k) + 3*C(N,3)*M(3,k) + ・・・ + N*C(N,N)*M(N,k)}/N^k

になります。

[GON]

平均種類数の表式が間違ってましたので訂正後の考察をします。

"GON" <g...@mocha.freemail.ne.jp> wrote in message news:bvah28$hef$1...@news511.nifty.com...

> ここで、その子が５０種類のカードをすべて集めるまでにどのぐらい時間が掛かるか
> 先に投稿したグラフを参考に概算を出してみます。Ｎ＝５０のグラフを見ると４００個
> 程度でほぼ５０種類近くに達するようです。すると
>
> ４００（個）÷１５（個/月）≒２７ヶ月＝２年３ヶ月
>
> と概算が出ます。従って、そのお菓子のおまけは最大でも２年程度で新しいものに
> しないと飽きられてしまう計算になります。

これはくろさわさんご指摘のように２２５回になりますから

２２５（個）÷１５（個/月）≒１５ヶ月＝１年３ヶ月

になります。もし、友達同士の交換がなければ１年程度で新しいシリーズを出さないと
飽きられてしまいます。

[Yoshitaka Ikeda]

GONさんの<bvahai$hop$1...@news511.nifty.com>から

えーっと、いろいろと考えたり考えていただいたりしたわけですが、
ちょっと似たような話を昨日、某シンポジウムで聞いちゃったので
書きますね。

あるブロック暗号アルゴリズムがあって、それはテーブルを引く部分をいっぱ
い繰り返すわけです。テーブルのインデックスはある程度限られている　と。
で、自分が制御できないところはランダムな過程を通ると仮定します。

自分が制御できる部分をうまく一致させることができた場合と、一致させない
場合とで、アルゴリズム全体で引かれたテーブルの「ユニークな数」がどれく
らい変わるか。というのが知りたかったわけです。
これが検知可能であれば、自分が制御した部分が一致してるか一致していない
かを決定できるわけです。

というような応用を考えた問題だったのでした。

[Tsukamoto Chiaki]

工繊大の塚本です.

In article <bvavbu$2mqd$1...@news2.rim.or.jp>

KUROSAWA Takashi <ta...@yk.rim.or.jp> writes:
> 50 種類を集めるのに掛かる回数は 225 回ではないですか?
> サイコロだと 15 回。
> 　n/n + n/(n-1) + n/(n-2) + … n/1
>
> サイコロで考えると…
> 　○1 番目の目
> 　　どれが出てもイイから確率 6/6、出るまでに掛かる回数はその
> 　　逆数の 6/6 回。
> 　○2 番目の目
> 　　最初に出た 1 つを避けるから確率 5/6、出るまでの回数は逆数
> 　　の 6/5 回。
> 　～(snip)～
> 　○6 番目の目
> 　　既出の 5 つを避けるから確率 1/6、出るまでの回数は逆数の
> 　　6/1 回。
> …という、個々の理想の試行回数を足し合わせて…
> 　6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1
> 　　= 147/10
> 　　= 14.7、切り上げて 15 回
> …となります。コンピュータで乱数を廻して検証しました。

良い考え方だと思います.

k 種類の文字が random に出現するとき, n 回目にちょうど k 種類出揃う
というのは, n-1 回までが k-1 種類の文字がちょうど現れるような列に
なっていて, n 回目に残りの文字が出るという場合ですから, その確率は

(Σ_{i=0}^{k-1} (-1)^i C(k-1, i) (k-1-i)^{n-1})/k^{n-1}

その回数の期待値 E は

E = Σ_{n=k}^∞ n (Σ_{i=0}^{k-1} (-1)^i C(k-1, i) (k-1-i)^{n-1})/k^{n-1}
= Σ_{i=0}^{k-1} (-1)^i C(k-1, i) Σ_{n=k}^∞ n ((k-1-i)/k)^{n-1}.

ここで S(X) = Σ_{n=k}^∞ n X^{n-1} とおくと,

S(X) = (d/dX) Σ_{n=k}^∞ X^n
= (d/dX) (X^k/(1-X))
= k X^{k-1}/(1-X) + X^k/(1-X)^2.

よって, 1 - (k-1-i)/k = (i+1)/k, C(k-1, i)*(k/(i+1)) = C(k, i+1) ゆえ,

E = Σ_{i=0}^{k-1} (-1)^i C(k-1, i)
(k^2/(i+1) + k(k-1-i)/(i+1)^2)
((k-1-i)/k)^{k-1}.
= Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k + k/(i+1) - 1) ((k-1-i)/k)^{k-1}

さて, m < k なら m 文字の列に k 種類の文字が現れることはないので,

Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k-1-i)^m
= k^m - Σ_{i=0}^k (-1)^i C(k, i) (k-i)^m
= k^m

となることに注意すると,

E = k - 1 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1)) ((k-1-i)/k)^{k-1}
= k - 1 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1) - 1) ((k-1-i)/k)^{k-2}
= k - 2 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1)) ((k-1-i)/k)^{k-2}
= …
= Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1))

です.

Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (1/(i+1))
= Σ_{i=0}^{k-1} (-1)^i C(k, i+1) ∫_0^1 x^i dx
= ∫_0^1 (Σ_{i=0}^{k-1} (-1)^i C(k, i+1) x^i) dx
= ∫_0^1 (1 - (Σ_{i=0}^k (-1)^i C(k, i) x^i))/x dx
= ∫_0^1 (1 - (1-x)^k)/x dx
= ∫_0^1 (1 - t^k)/(1-t) dt
= ∫_0^1 Σ_{i=0}^{k-1} t^i dt
= Σ_{i=0}^{k-1} 1/(i+1)

を代入して,

E = k Σ_{i=0}^{k-1} 1/(i+1)

が直接計算でも分かります. 面白い.

[GON]

"Yoshitaka Ikeda" <ik...@4bn.ne.jp> wrote in message news:bvc3nn$kf9$1...@caraway.media.kyoto-u.ac.jp...
> GONさんの<bvahai$hop$1...@news511.nifty.com>から

> >純粋に数学的な問題としては面白くないのかもしれませんが、その結果
> >どんな応用がありえるのかを考えるのは結構楽しいです。
>
> えーっと、いろいろと考えたり考えていただいたりしたわけですが、
> ちょっと似たような話を昨日、某シンポジウムで聞いちゃったので
> 書きますね。
>
> あるブロック暗号アルゴリズムがあって、それはテーブルを引く部分をいっぱ
> い繰り返すわけです。テーブルのインデックスはある程度限られている　と。
> で、自分が制御できないところはランダムな過程を通ると仮定します。
>
> 自分が制御できる部分をうまく一致させることができた場合と、一致させない
> 場合とで、アルゴリズム全体で引かれたテーブルの「ユニークな数」がどれく
> らい変わるか。というのが知りたかったわけです。
> これが検知可能であれば、自分が制御した部分が一致してるか一致していない
> かを決定できるわけです。
>
>
> というような応用を考えた問題だったのでした。

うわぁ～、えらい難しそうなことに関係してたんですね。（＾＾）

「自分が制御できる・でない」の意味がよくわからないのですが
要は暗号のすべてが１：１にテーブルに対応しているわけでなく
一部にノイズが入っていてそれでもテーブルによって再現できる
部分がどの程度一致できるかを見たいということでよろしいんで
しょうか？

あるいは暗号のノイズに対する復元性や耐性が知りたいとか？

[Yoshitaka Ikeda]

GONさんの<bvd6p2$6h4$1...@news511.nifty.com>から

>"Yoshitaka Ikeda" <ik...@4bn.ne.jp> wrote in message news:bvc3nn$kf9$1...@caraway.media.kyoto-u.ac.jp...

(中略)

>> というような応用を考えた問題だったのでした。
>
>うわぁ～、えらい難しそうなことに関係してたんですね。（＾＾）
>
>「自分が制御できる・でない」の意味がよくわからないのですが
>要は暗号のすべてが１：１にテーブルに対応しているわけでなく
>一部にノイズが入っていてそれでもテーブルによって再現できる
>部分がどの程度一致できるかを見たいということでよろしいんで
>しょうか？
>
>あるいは暗号のノイズに対する復元性や耐性が知りたいとか？

えーっと、そうではないです。ランダムに平文を入力すれば、
テーブルを(複数回)参照するときに、ランダムな参照がされるだろう
という考え方をします。

ところが、入力部分に近いところでは、平文に鍵(の一部)が加算されらもの
が、テーブルに入力されます。そういうものを二つ準備します。
たとえばテーブルをT[] x1~x8を平文 k1~k8を鍵とします。
k1~k8は当然未知です。x1~x8は自由に選択できるとします。
途中にテーブル参照T[x1+k1],T[x2+k2],...,T[x8+k8]とあったとします。
このときに、T[x1+k1]=T[x2+k2]であることがわかれば、
x1-x2=k1-k2
であることがわかります。
鍵サイズが一個当たり8bitであれば、鍵8個を探索するには2^64回の試行が必
要になりますが、k1^k2の値がわかっていれば探索量は2^56回で充分になりま
す。

で、T[x1+k1]=T[x2+k2]がわかれば、と書きましたが、普通はわかりません。
ところが、同じTを2回参照したとき、違うTを参照するよりも高速に参照でき
るとします。(ソフトウェア実装でキャッシュメモリにヒットするなんていう
モデルを考えれば沿うおかしな家庭でないことはわかるでしょう)
そうしたとき、全体の暗号化時間を測定したときに、T[x1+k1]=T[x2+k2]を仮
定して統計量を算出し、ランダムな過程と検定すれば　過程が正しいかどうか
判定可能なわけです。

で、今回知りたかったのは、仮定しない場合と仮定した場合のユニークなテー
ブル参照の数の差を知りたかったわけです。差が小さければ多くの試行をする
必要があるわけです。